八數(shù)碼問題求解--試驗(yàn)報(bào)告

1、實(shí)驗(yàn)報(bào)告、實(shí)驗(yàn)問題八數(shù)碼問題求解、實(shí)驗(yàn)軟件VC6.0編程語(yǔ)言或其它編程語(yǔ)言三、實(shí)驗(yàn)?zāi)康? .熟悉人工智能系統(tǒng)中的問題求解過程；2 .熟悉狀態(tài)空間的盲目搜索和啟發(fā)式搜索算法的應(yīng)用；3 .熟悉對(duì)八數(shù)碼問題的建模、求解及編程語(yǔ)言的應(yīng)用。四、實(shí)驗(yàn)數(shù)據(jù)及步驟（一、）實(shí)驗(yàn)內(nèi)容八數(shù)碼問題：在3X3的方格棋盤上，擺放著1到8這八個(gè)數(shù)碼，有1個(gè)方格是空的，其初始狀態(tài)如圖1所示，要求對(duì)空格執(zhí)行空格左移、空格右移、空格上移和空格下移這四個(gè)操作使得棋盤從初始狀態(tài)到目標(biāo)狀態(tài)。（a）初始狀態(tài)（b）目標(biāo)狀態(tài)圖1八數(shù)碼問題示意圖（二、）基本數(shù)據(jù)結(jié)構(gòu)分析和實(shí)現(xiàn)1.結(jié)點(diǎn)狀態(tài)我采用了structNode數(shù)據(jù)類型typedefstr

2、uct_NodeintdigitROWCOL;intdist;/distancebetweenonestateandthedestination一個(gè)表和目的表的距離intdep;/thedepthofnode深度/Sothecommentfunction=dist+dep.估價(jià)函數(shù)值intindex;/pointtothelocationofparent父節(jié)點(diǎn)的位置Node;2.發(fā)生器函數(shù)定義的發(fā)生器函數(shù)由以下的四種操作組成：(1)將當(dāng)前狀態(tài)的空格上移Nodenode_up;Assign(node_up,index);/向上擴(kuò)展的節(jié)點(diǎn)intdist_up=MAXDISTANCE;(2)將當(dāng)前狀

3、態(tài)的空格下移Nodenode_down;Assign(node_down,index);/向下擴(kuò)展的節(jié)點(diǎn)intdist_down=MAXDISTANCE;(3)將當(dāng)前病態(tài)的空格左移Nodenode_left;Assign(node_left,index);/向左擴(kuò)展的節(jié)點(diǎn)intdist_left=MAXDISTANCE;(4)將當(dāng)前狀態(tài)的空格右移Nodenode_right;Assign(node_right,index);/向右擴(kuò)展的節(jié)點(diǎn)intdist_right=MAXDISTANCE;通過定義結(jié)點(diǎn)狀態(tài)和發(fā)生器函數(shù)，就解決了8數(shù)碼問題的隱式圖的生成問題。接下來就是搜索了。3.圖的搜索策略經(jīng)

4、過分析，8數(shù)碼問題中可采用的搜速策略共有：1.廣度優(yōu)先搜索、2.深度優(yōu)先搜索、2.有界深度優(yōu)先搜索、4.最好優(yōu)先搜索、5.局部擇優(yōu)搜索，一共五種。其中，廣度優(yōu)先搜索法是可采納的，有界深度優(yōu)先搜索法是不完備的，最好優(yōu)先和局部擇優(yōu)搜索法是啟發(fā)式搜索法。實(shí)驗(yàn)時(shí)，采用了廣度(寬度)優(yōu)先搜索來實(shí)現(xiàn)。(三、)廣度(寬度)優(yōu)先搜索原理1 .狀態(tài)空間盲目搜索一一寬度優(yōu)先搜索其基本思想是，從初始節(jié)點(diǎn)開始，向下逐層對(duì)節(jié)點(diǎn)進(jìn)形依次擴(kuò)展，并考察它是否為目標(biāo)節(jié)點(diǎn)，再對(duì)下層節(jié)點(diǎn)進(jìn)行擴(kuò)展(或搜索)之前，必須完成對(duì)當(dāng)層的所有節(jié)點(diǎn)的擴(kuò)展。再搜索過程中，未擴(kuò)展節(jié)點(diǎn)表OPEN中的節(jié)點(diǎn)排序準(zhǔn)則是:先進(jìn)入的節(jié)點(diǎn)排在前面，后進(jìn)入的節(jié)點(diǎn)排

5、在后面。具搜索過程如圖(1)所示圖2、寬度優(yōu)先搜索示意圖2 .寬度優(yōu)先算法如下：步1把初始結(jié)點(diǎn)S0放入OPE戲中步2若OPENS為空，則搜索失敗，問題無(wú)解步3取OPENft中最前面的結(jié)點(diǎn)N放在CLOSE!中，并冠以順序編號(hào)n步4若目標(biāo)結(jié)點(diǎn)Sg=N則搜索成功，問題有解步5若N無(wú)子結(jié)點(diǎn)，則轉(zhuǎn)步2步6擴(kuò)展結(jié)點(diǎn)N,將其所有子2點(diǎn)配上指向N的放回指針，依次放入OPENg的尾部，轉(zhuǎn)步2.寬度優(yōu)先算法流程圖（按順時(shí)針方向移動(dòng)空格）圖中有26個(gè)節(jié)點(diǎn)，也就是源程序運(yùn)行結(jié)果。圖3、寬度優(yōu)先算法流程圖4.8數(shù)碼難題用寬度優(yōu)先搜索所生成的搜索樹如圖4。搜索樹上的所有節(jié)點(diǎn)都標(biāo)記它們所對(duì)應(yīng)的狀態(tài)描述，每個(gè)節(jié)點(diǎn)旁邊的數(shù)字表

6、示節(jié)點(diǎn)擴(kuò)展的順序圖4.八數(shù)碼題寬度優(yōu)先搜索樹五、實(shí)驗(yàn)結(jié)果及分析上機(jī)試驗(yàn)時(shí)，經(jīng)多次程序調(diào)試，最后得一下結(jié)果。此結(jié)果所得節(jié)點(diǎn)（狀態(tài)圖）很多，可知寬度優(yōu)先搜索的盲目性很大，當(dāng)目標(biāo)節(jié)點(diǎn)距離初始節(jié)點(diǎn)較遠(yuǎn)時(shí),就會(huì)產(chǎn)生大量的無(wú)用節(jié)點(diǎn)，搜索效率低。但是，只要問題有解，用寬度優(yōu)先搜索總可以找到它的解。D:VC6MQ()MyPrqjectszb20110430Debug7VSSjB.exep1np(JLt1np(JLt ourceource：B12345B12345 78Inputdestination123456780Searcli-.78Inputdestination123456780Searcli-.So

7、urceSource+ +012012345345678678Step21423M5678Step21423M56782582580470471361363 3258258P Pe e437437t ts1IB6s1IB6830214765 D:VC6.0S()MyProjectszb20110430DebugVVSS.exeD:VC6.0S()MyProjectszb20110430DebugVVSS.exeStep4142635078Step4142635078Step5142635708Step5142635708Step6142635780Step6142635780Step71426

8、30785Step7142630785Step8142603785Step8142603785 e eDzVC6.0S()MyPrqjectszb20110430DebugVjS?SexeDzVC6.0S()MyPrqjectszb20110430DebugVjS?Sexe045045786786StepStep2020123123405405786786Step21Step21123123458458786786Step22Step22123123卜5656788788Successful?Successful?r r. .lUsinglUsing0seconds.0seconds.iPre

9、ssiPressanykeytocontinueanykeytocontinue圖5.程序運(yùn)行結(jié)果六、結(jié)論人工智能搜索可分為盲目搜索和啟發(fā)式搜索。盲目搜索算法有寬度優(yōu)先算法、深度優(yōu)先算法（有界深度優(yōu)先算法），啟發(fā)式搜索算法有A算法、A*算法。本實(shí)驗(yàn)采用的是寬度優(yōu)先（廣度優(yōu)先）算法，這種算法是按預(yù)定的控制策略進(jìn)行，在搜素的過程中所獲得的信息不用來改進(jìn)控制策略。由于搜索總是按預(yù)定的路線進(jìn)行，沒有考慮問題本身的特性，這種缺乏問題求解的針對(duì)性，需要進(jìn)行全方位的搜索，而沒有選擇最優(yōu)的搜索路徑。 所以圖4寬度優(yōu)先搜索樹及程序運(yùn)行結(jié)果圖5得到的節(jié)點(diǎn) （狀態(tài)圖）很多，而解路徑為1-3-8-16-26,其它節(jié)點(diǎn)

10、是沒有用的節(jié)點(diǎn)，搜索效率很低。通過這次實(shí)驗(yàn)更加熟悉狀態(tài)空間的寬度優(yōu)先搜索、深度優(yōu)先搜索和啟發(fā)式搜索算法及計(jì)算機(jī)語(yǔ)言對(duì)常用數(shù)據(jù)結(jié)構(gòu)如鏈表、隊(duì)列等的描述應(yīng)用。學(xué)到了不少知識(shí)。七、源程序及注釋#include#include#includeusingnamespacestd;constintROW=3;行數(shù)constintCOL=3;列數(shù)constintMAXDISTANCE=10000;/最多可以有的表的數(shù)目constintMAXNUM=10000;typedefstruct_NodeintdigitROWCOL;intdist;/distancebetweenonestateandthedest

11、ination個(gè)表和目的表的距離intdep;/thedepthofnode深度/Sothecommentfunction=dist+dep.估價(jià)函數(shù)值intindex;/pointtothelocationofparent父節(jié)點(diǎn)的位置Node;Nodesrc,dest;/父節(jié)表目的表vectornode_v;/storethenodes存儲(chǔ)節(jié)點(diǎn)boolisEmptyOfOPEN()/open表是否為空for(inti=0;inode_v.size();i+)if(node_vi.dist!=MAXNUM)returnfalse;returntrue;boolisEqual(intindex,

12、intdigit口COL)判斷這個(gè)最優(yōu)的節(jié)點(diǎn)是否和目的節(jié)點(diǎn)一樣(for(inti=0;iROW;i+)for(intj=0;jCOL;j+)if(node_vindex.digitij!=digitij)returnfalse;returntrue;ostream&operator(ostream&os,Node&node)for(inti=0;iROW;i+)for(intj=0;jCOL;j+)osnode.digitij;osendl;returnos;voidPrintSteps(intindex,vector&rstep_v)/輸出每一個(gè)遍歷的節(jié)點(diǎn)深度

13、遍歷rstep_v.push_back(node_vindex);index=node_vindex.index;while(index!=0)rstep_v.push_back(node_vindex);index=node_vindex.index;for(inti=rstep_v.size()-1;i=0;i-)/輸出每一步的探索過程coutSteprstep_v.size()-iendlrstep_viendl;voidSwap(int&a,int&b)intt;t=a;a=b;b=t;voidAssign(Node&node,intindex)(for(int

14、i=0;iROW;i+)for(intj=0;jCOL;j+)node.digitij=node_vindex.digitij;intGetMinNode()/找到最小的節(jié)點(diǎn)的位置即最優(yōu)節(jié)點(diǎn)(intdist=MAXNUM;intloc;/thelocationofminimizenodefor(inti=0;inode_v.size();i+)(if(node_vi.dist=MAXNUM)continue;elseif(node_vi.dist+node_vi.dep)dist)10c=i;dist=node_vi.dist+node_vi.dep;returnloc;boolisExpan

15、dable(Node&node)for(inti=0;inode_v.size();i+)if(isEqual(i,node.digit)returnfalse;returntrue;intDistance(Node&node,intdigitCOL)intdistance=0;boolflag=false;for(inti=0;iROW;i+)for(intj=0;jCOL;j+)for(intk=0;kROW;k+)for(intl=0;lCOL;l+)if(node.digitij=digitkl)distance+=abs(i-k)+abs(j-l);flag=true

16、;break;)elseflag=false;)if(flag)break;)returndistance;)intMinDistance(inta,intb)(return(ab?a:b);)voidProcessNode(intindex)(intx,y;boolflag;for(inti=0;iROW;i+)for(intj=0;j0)Swap(node_up.digitxy,node_up.digitx-1y);if(isExpandable(node_up)dist_up=Distance(node_up,dest.digit);node_up.index=index;node_up

17、.dist=dist_up;node_up.dep=node_vindex.dep+1;node_v.push_back(node_up);)Nodenode_down;Assign(node_down,index);/向下擴(kuò)展的節(jié)點(diǎn)intdist_down=MAXDISTANCE;if(x0)Swap(node_left.digitxy,node_left.digitxy-1);if(isExpandable(node_left)dist_left=Distance(node_left,dest.digit);node_left.index=index;node_left.dist=dist

18、_left;node_left.dep=node_vindex.dep+1;node_v.push_back(node_left);)Nodenode_right;Assign(node_right,index);/向右擴(kuò)展的節(jié)點(diǎn)intdist_right=MAXDISTANCE;if(y2)Swap(node_right.digitxy,node_right.digitxy+1);if(isExpandable(node_right)(dist_right=Distance(node_right,dest.digit);node_right.index=index;node_right.di

19、st=dist_right;node_right.dep=node_vindex.dep+1;node_v.push_back(node_right);node_vindex.dist=MAXNUM;intmain()主函數(shù)(intnumber;coutInputsource:endl;for(inti=0;iROW;i+)/輸入初始的表for(intj=0;jnumber;src.digitij=number;src.index=0;src.dep=1;coutInputdestination:endl;/輸入目的表for(intm=0;mROW;m+)for(intn=0;nnumber;

20、dest.digitmn=number;node_v.push_back(src);/在容器的尾部加一個(gè)數(shù)據(jù)coutSearch.endl;clock_tstart=clock();while(1)if(isEmptyOfOPEN()coutCanntsolvethisstatement!endl;return-1;else(intloc;/thelocationoftheminimizenode最優(yōu)節(jié)點(diǎn)的位置loc=GetMinNode();if(isEqual(loc,dest.digit)(vectorrstep_v;coutSource:endl;coutsrcendl;PrintSt

21、eps(loc,rstep_v);coutSuccessful!endl;coutUsing(clock()-start)/CLOCKS_PER_SECseconds.endl;break;elseProcessNode(loc);return0;十五數(shù)碼問題的截圖(對(duì)行和列數(shù)進(jìn)行修改)：7 7D:VC6.0?|()MyProjectszb20110430DebugVVS(.exe*D:VC6.0?|()MyProjectszb20110430DebugVVS(.exe*I=II=I回JjJjInputsourceInputsource：0001020304050607080910111213

22、1415Inputdestination00010203040506070809101112131415Inputdestination：000002020103050406070809101112131415Search.0103050406070809101112131415Search.SourceSource：0123456?891011121314150123456?89101112131415Step11023456?89101112131415Step11023456?89101112131415Step212034567h91011Step212034567h91011卜213

23stepIstep3k2633k263* * D:VC6.0S()MyProjectszb2011043DDebugVkS(S.exeD:VC6.0S()MyProjectszb2011043DDebugVkS(S.exeB B1213141512131415Step31263Step31263450789101145078910111213141512131415Step41263Step41263405789101140578910111213141512131415Step51063425789101112131415Step51063425789101112131415Step60163Step60163425789101142578910111213141512131415 D:VC6.0?|()MyPrqjectszb20110430DebugVVS(fi.exe*D:VC6.0?|()MyPrqjectszb20110430DebugVVS(fi.exe*巴)一玄二|StepStep7416302578910111213141574163025789101112131415StepStep84