人工智能導(dǎo)論：狀態(tài)空間搜索實驗—八數(shù)碼問題求解

1、昆明理工大學(xué)信息工程與自動化學(xué)院學(xué)生實驗報告（ 2014 2015 學(xué)年 第 一 學(xué)期 ）課程名稱：人工智能導(dǎo)論 開課實驗室： 年 月 日年級、專業(yè)、班學(xué)號姓名成績實驗項目名稱狀態(tài)空間搜索實驗八數(shù)碼問題求解指導(dǎo)教師胡蓉教師評語該同學(xué)是否了解實驗原理： A.了解 B.基本了解 C.不了解 該同學(xué)的實驗?zāi)芰Γ?A.強 B.中等 C.差 該同學(xué)的實驗是否達到要求 ： A.達到 B.基本達到 C.未達到實驗報告是否規(guī)范： A.規(guī)范 B.基本規(guī)范 C.不規(guī)范實驗過程是否詳細記錄： A.詳細 B.一般 C.沒有 教師簽名： 年 月 日一、實驗內(nèi)容和要求八數(shù)碼問題：在33的方格棋盤上，擺放著1到8這八個數(shù)碼

2、，有1個方格是空的，其初始狀態(tài)如圖1所示，要求對空格執(zhí)行空格左移、空格右移、空格上移和空格下移這四個操作使得棋盤從初始狀態(tài)到目標狀態(tài)。例如：28312316484705765(a) 初始狀態(tài) (b) 目標狀態(tài)圖1 八數(shù)碼問題示意圖請任選一種盲目搜索算法（廣度優(yōu)先搜索或深度優(yōu)先搜索）或任選一種啟發(fā)式搜索方法（全局擇優(yōu)搜索，加權(quán)狀態(tài)圖搜索，A 算法或 A* 算法）編程求解八數(shù)碼問題（初始狀態(tài)任選）。選擇一個初始狀態(tài)，畫出搜索樹，填寫相應(yīng)的OPEN表和CLOSED表，給出解路徑，對實驗結(jié)果進行分析總結(jié)，得出結(jié)論。實驗報告內(nèi)容格式要求：XXXXXXXXXXXX（中文：宋體，小四；英文：Times Ne

3、w Roman）。二、實驗?zāi)康?. 熟悉人工智能系統(tǒng)中的問題求解過程；2. 熟悉狀態(tài)空間的盲目搜索和啟發(fā)式搜索算法的應(yīng)用；3. 熟悉對八數(shù)碼問題的建模、求解及編程語言的應(yīng)用。三、實驗算法啟發(fā)函數(shù)設(shè)定 由八數(shù)碼問題的部分狀態(tài)圖可以看出，從初始節(jié)點開始，在通向目標節(jié)點的路徑上，各節(jié)點的數(shù)碼格局同目標節(jié)點相比較，其數(shù)碼不同的位置個數(shù)在逐漸減少，最后為零，因此可以把數(shù)碼不同的位置個數(shù)作為標志一個節(jié)點到目標節(jié)點距離遠近的一個啟發(fā)性信息，利用這個信息來擴展節(jié)點的選擇，減少搜索范圍，提高搜索速度。2、數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計數(shù)碼結(jié)構(gòu)體typedef struct node /八數(shù)碼結(jié)構(gòu)體int formNN; /

4、數(shù)碼組int evalue; /評估值，差距int udirec; /所屏蔽方向,防止往回推到上一狀態(tài),1上2下3左4右struct node *parent; /父節(jié)點Graph;Graph *QuMAX;/隊列Graph *StMAX;/堆棧搜索過程：（搜索采用廣度搜索方式，利用待處理隊列輔助，逐層搜索（跳過劣質(zhì)節(jié)點）a、把初始數(shù)碼組壓入隊列；b、從隊列中取出一個數(shù)碼組節(jié)點；c、擴展子節(jié)點，即從上下左右四個方向移動空格，生成相應(yīng)子節(jié)點：d、對子節(jié)點數(shù)碼組作評估，是否為優(yōu)越節(jié)點，即其評估值是否小于等于其父節(jié)點加一，是則將其壓入隊，否則拋棄。 e、判斷壓入隊的子節(jié)點數(shù)碼組（優(yōu)越點）的評估值，為

5、零則表示搜索完成，退出搜索； f、跳到步驟2；四、程序框圖起始把s放入open表失敗成功是否open表為空表？是把open表中的第一個節(jié)點n移入close表否擴展節(jié)點n，把其后裔放入open表的前頭是否有后繼節(jié)點為目標節(jié)點？否是 五、實驗結(jié)果及分析采用深度優(yōu)先搜索方式 并簡化搜索六、結(jié)論813204765 (2)103824765 (3)813024 （0）765813024765 (4)123804765 (5)013824765 (1)Open表 close表01 2 02 3 4 0 12 4 5 6 0 1 3 目標完成七、源程序及注釋#include /設(shè)計了搜索深度范圍，防止隊列內(nèi)

6、存越界#include6、運行結(jié)果#include#defineN3/數(shù)碼組大小#defineMax_Step50/最大搜索深度#defineMAX50typedefstructnode/八數(shù)碼結(jié)構(gòu)體intformNN;/數(shù)碼組intevalue;/評估值intudirect;/所屏蔽方向，防止往回推到上已狀態(tài)，1上2下3左4右structnode*parent;/父節(jié)點/打印數(shù)碼組voidPrint(Graph*The_graph)inti,j;if(The_graph=NULL)printf(圖為空n);elseprintf(-n);for(i=0;iN;i+)printf(|t);for

7、(j=0;jformij);/遍歷打印printf(t|n);printf(|ttt差距:%dt|n,The_graph-evalue);/差距顯示printf(-n);/評價函數(shù)intEvaluate(Graph*The_graph,Graph*End_graph)intvalute=0;/差距數(shù)inti,j;for(i=0;iN;i+)for(j=0;jformij!=End_graph-formij)valute+;The_graph-evalue=valute;returnvalute;/移動數(shù)碼組Graph*Move(Graph*The_graph,intDirect,intCrea

8、tNew_graph)Graph*New_graph;/intHasGetBlank=0;/是否獲取空格位置intAbleMove=1;/是否可移動inti,j,t_i,t_j,x,y;for(i=0;iN;i+)/獲取空格坐標i,jfor(j=0;jformij=0)HasGetBlank=1;break;if(HasGetBlank=1)break;/printf(空格位置:%d,%dn,i,j);t_i=i;t_j=j;/移動空格switch(Direct)case1:/上t_i-;if(t_i=N)AbleMove=0;break;case3:/左t_j-;if(t_j=N)AbleM

9、ove=0;break;if(AbleMove=0)/不能移動則返回原節(jié)點returnThe_graph;if(CreatNew_graph=1)New_graph=(Graph*)malloc(sizeof(Graph);/生成節(jié)點for(x=0;xN;x+)for(y=0;yformxy=The_graph-formxy;/復(fù)制數(shù)碼組elseNew_graph=The_graph;/移動后New_graph-formij=New_graph-formt_it_j;New_graph-formt_it_j=0;/printf(移動產(chǎn)生的新圖:n);/Print(New_graph);retu

10、rnNew_graph;/搜索函數(shù)Graph*Search(Graph*Begin,Graph*End)Graph*g1,*g2,*g;intStep=0;/深度intDirect=0;/方向inti;intfront,rear;front=rear=-1;/隊列初始化g=NULL;rear+;/入隊Qurear=Begin;while(rear!=front)/隊列不空front+;/出隊g1=Qufront;/printf(開始第%d個圖:n,front);/Print(g1);for(i=1;iudirect)/跳過屏蔽方向continue;g2=Move(g1,Direct,1);/移

11、動數(shù)碼組if(g2!=g1)/數(shù)碼組是否可以移動/可以移動Evaluate(g2,End);/評價新的節(jié)點/printf(開始產(chǎn)生的第%d個圖:n,i);/Print(g2);if(g2-evalueevalue+1)/是優(yōu)越節(jié)點g2-parent=g1;/移動空格switch(Direct)/設(shè)置屏蔽方向，防止往回推case1:/上g2-udirect=2;break;case2:/下g2-udirect=1;break;case3:/左g2-udirect=4;break;case4:/右g2-udirect=3;break;rear+;Qurear=g2;/存儲節(jié)點到待處理隊列if(g2

12、-evalue=0)/為0則搜索完成g=g2;/i=5;break;elsefree(g2);/拋棄劣質(zhì)節(jié)點g2=NULL;if(g!=NULL)/為0則搜索完成if(g-evalue=0)break;Step+;/統(tǒng)計深度if(StepMax_Step)break;returng;/初始化一個八數(shù)碼結(jié)構(gòu)體Graph*CR_BeginGraph(Graph*The_graph)srand(unsigned)time(0);intM=10;/隨機移動步數(shù)intDirect;inti,x,y;Graph*New_graph;New_graph=(Graph*)malloc(sizeof(Graph

13、);for(x=0;xN;x+)for(y=0;yformxy=The_graph-formxy;for(i=0;ievalue=0;New_graph-udirect=0;New_graph-parent=NULL;returnNew_graph;intmain(intargc,constchar*argv)/insertcodehere./*GraphBegin_graph=2,8,3,1,6,4,0,7,5,0,0,NULL;GraphBegin_graph=2,8,3,1,0,4,7,6,5,0,0,NULL;GraphBegin_graph=2,0,1,4,6,5,3,7,8,0,0,NULL;*/目標數(shù)碼組GraphEnd_graph=1,2,3,8,0,4,7,6,5,0,0,NULL;/初始數(shù)碼組Graph*Begin_graph;Begin_graph=CR_BeginGraph(&End_graph);/隨機產(chǎn)生初始數(shù)碼組Evaluate(Begin_graph,&End_graph);/對初始的數(shù)碼組評價printf(初始數(shù)碼組:n);Print(Begin_graph);printf(目標數(shù)碼組:n);Print(&End_graph);Graph*G,*P;inttop=-1;