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

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

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

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

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

5、零則表示搜索完成，退出搜索； f、跳到步驟2；四、程序框圖起始把s放入open表失敗成功是否open表為空表？是把open表中的第一個(gè)節(jié)點(diǎn)n移入close表否擴(kuò)展節(jié)點(diǎn)n，把其后裔放入open表的前頭是否有后繼節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)？否是 五、實(shí)驗(yàn)結(jié)果及分析采用深度優(yōu)先搜索方式 并簡(jiǎn)化搜索六、結(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 目標(biāo)完成七、源程序及注釋#include /設(shè)計(jì)了搜索深度范圍，防止隊(duì)列內(nèi)

6、存越界#include6、運(yùn)行結(jié)果#include#defineN3/數(shù)碼組大小#defineMax_Step50/最大搜索深度#defineMAX50typedefstructnode/八數(shù)碼結(jié)構(gòu)體intformNN;/數(shù)碼組intevalue;/評(píng)估值intudirect;/所屏蔽方向，防止往回推到上已狀態(tài)，1上2下3左4右structnode*parent;/父節(jié)點(diǎn)/打印數(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);/評(píng)價(jià)函數(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;/移動(dòng)數(shù)碼組Graph*Move(Graph*The_graph,intDirect,intCrea

8、tNew_graph)Graph*New_graph;/intHasGetBlank=0;/是否獲取空格位置intAbleMove=1;/是否可移動(dòng)inti,j,t_i,t_j,x,y;for(i=0;iN;i+)/獲取空格坐標(biāo)i,jfor(j=0;jformij=0)HasGetBlank=1;break;if(HasGetBlank=1)break;/printf(空格位置:%d,%dn,i,j);t_i=i;t_j=j;/移動(dòng)空格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)/不能移動(dòng)則返回原節(jié)點(diǎn)returnThe_graph;if(CreatNew_graph=1)New_graph=(Graph*)malloc(sizeof(Graph);/生成節(jié)點(diǎn)for(x=0;xN;x+)for(y=0;yformxy=The_graph-formxy;/復(fù)制數(shù)碼組elseNew_graph=The_graph;/移動(dòng)后New_graph-formij=New_graph-formt_it_j;New_graph-formt_it_j=0;/printf(移動(dòng)產(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;/隊(duì)列初始化g=NULL;rear+;/入隊(duì)Qurear=Begin;while(rear!=front)/隊(duì)列不空f(shuō)ront+;/出隊(duì)g1=Qufront;/printf(開(kāi)始第%d個(gè)圖:n,front);/Print(g1);for(i=1;iudirect)/跳過(guò)屏蔽方向continue;g2=Move(g1,Direct,1);/移

11、動(dòng)數(shù)碼組if(g2!=g1)/數(shù)碼組是否可以移動(dòng)/可以移動(dòng)Evaluate(g2,End);/評(píng)價(jià)新的節(jié)點(diǎn)/printf(開(kāi)始產(chǎn)生的第%d個(gè)圖:n,i);/Print(g2);if(g2-evalueevalue+1)/是優(yōu)越節(jié)點(diǎn)g2-parent=g1;/移動(dòng)空格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;/存儲(chǔ)節(jié)點(diǎn)到待處理隊(duì)列if(g2

12、-evalue=0)/為0則搜索完成g=g2;/i=5;break;elsefree(g2);/拋棄劣質(zhì)節(jié)點(diǎn)g2=NULL;if(g!=NULL)/為0則搜索完成if(g-evalue=0)break;Step+;/統(tǒng)計(jì)深度if(StepMax_Step)break;returng;/初始化一個(gè)八數(shù)碼結(jié)構(gòu)體Graph*CR_BeginGraph(Graph*The_graph)srand(unsigned)time(0);intM=10;/隨機(jī)移動(dòng)步數(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

14、,NULL;*/目標(biāo)數(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);/隨機(jī)產(chǎn)生初始數(shù)碼組Evaluate(Begin_graph,&End_graph);/對(duì)初始的數(shù)碼組評(píng)價(jià)printf(初始數(shù)碼組:n);Print(Begin_graph);printf(目標(biāo)數(shù)碼組:n);Print(&End_graph);Graph*G,*P;inttop=-1;/圖搜索G=Search(Begin_graph,&End_graph);/打印

15、if(G)/把路徑倒序P=G;/壓棧while(P!=NULL)top+;Sttop=P;P=P-parent;printf(n);/彈棧打印while(top-1)P=Sttop;top-;Print(P);printf(n);elseprintf(搜索不到結(jié)果，深度為%dn,Max_Step);/設(shè)計(jì)搜索深度范圍主要是防止隊(duì)列內(nèi)存越界return0; 讀書(shū)的好處1、行萬(wàn)里路，讀萬(wàn)卷書(shū)。2、書(shū)山有路勤為徑，學(xué)海無(wú)涯苦作舟。3、讀書(shū)破萬(wàn)卷，下筆如有神。4、我所學(xué)到的任何有價(jià)值的知識(shí)都是由自學(xué)中得來(lái)的。達(dá)爾文5、少壯不努力，老大徒悲傷。6、黑發(fā)不知勤學(xué)早，白首方悔讀書(shū)遲。顏真卿7、寶劍鋒從磨礪出，梅花香自苦寒來(lái)。8、讀書(shū)要三到：心到、眼到、口到9、玉不琢、不成器，人不學(xué)