實(shí)驗(yàn):八數(shù)碼游戲問題(a)初始狀態(tài)(a)初始狀態(tài)圖(b)目標(biāo)狀態(tài)八數(shù)碼游戲一、八數(shù)碼游戲問題簡(jiǎn)介九宮排字問題(乂稱八數(shù)碼問題)是人工智能當(dāng)中有名的難題之一。問題是在3X3方格盤上，放有八個(gè)數(shù)碼，剩下第九個(gè)為空，每一空格其上下左右的數(shù)碼可移至空格。問題給定初始位置和目標(biāo)位置，要求通過一系列的數(shù)碼移動(dòng)，將初始位置轉(zhuǎn)化為目標(biāo)位置。(a)初始狀態(tài)(a)初始狀態(tài)(b)目標(biāo)狀態(tài)二、實(shí)驗(yàn)?zāi)康?熟悉人工智能系統(tǒng)中的問題求解過程；.熟悉狀態(tài)空間的盲目搜索和啟發(fā)式搜索算法的應(yīng)用；.熟悉對(duì)八數(shù)碼問題的建模、求解及編程語(yǔ)言的應(yīng)用。三、實(shí)驗(yàn)的思路八數(shù)碼問題：在3X3的方格棋盤上，擺放著1到8這八個(gè)數(shù)碼，有1個(gè)方格是空的，其初始狀態(tài)如圖1所示，要求對(duì)空格執(zhí)行空格左移、空格右移、空格上移和空格下移這四個(gè)操作使得棋盤從初始狀態(tài)到目標(biāo)狀態(tài)。例如:圖1八數(shù)碼問題示意圖數(shù)碼結(jié)構(gòu)體數(shù)碼結(jié)構(gòu)體typedefstnictnode(intfonn[N][N];intevalue;intudirec;右stmctnode"parent;}Graph;Graph*Qu[MAX];〃隊(duì)歹ljGraph*St[MAX];〃堆棧.啟發(fā)函數(shù)設(shè)定由八數(shù)碼問題的部分狀態(tài)圖可以看出，從初始節(jié)點(diǎn)開始，在通向目標(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è)信息來擴(kuò)展節(jié)點(diǎn)的選擇，減少搜索范圍，提高搜索速度。.搜索過程：（搜索采用廣度搜索方式，利用待處理隊(duì)列輔助，逐層搜索（跳過劣質(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)估值，為零則表示搜索完成，退出搜索；f、跳到步驟2；四、數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)//八數(shù)碼結(jié)構(gòu)體〃數(shù)碼組〃評(píng)估值，差距〃所屏蔽方向，防止往回推到上一狀態(tài),1上2下3左4〃父節(jié)點(diǎn)起始五、實(shí)驗(yàn)過程及代碼#mclude<stdio.h>} 〃設(shè)計(jì)了搜索深度范闈，防止隊(duì)列內(nèi)存越界#include<stdlib.h>#include<tiine.h>defineN3〃數(shù)碼組大小defineMax_Step50〃最大搜索深度defineMAX50typedefstinctnode//八數(shù)碼結(jié)構(gòu)體(intform[N][N];〃數(shù)碼組intevahie〃評(píng)估值intudirect;〃所屏蔽方向，防止往回推到上已狀態(tài)，1上2下3左4右strnctnode*parent;〃父節(jié)點(diǎn)}Graph;Giaph*Qu[MAX];//隊(duì)歹ijGiaph*St[MAX];〃堆棧〃/〃〃〃打印數(shù)碼組voidPrint(Graph*The_graph)(mtij;if(The_giaph=NULL)printf(“圖為空\(chéng)n");else(pnntfC 3)for(i=0;i<N;i++)(prin—for(j=0;j<N;j++)(piintf("％d\t\The_graph->form國(guó)Ij]);〃遍歷打印}pniitf(n\t|\nH);}pniitf(n|\t\t\t差距:％d\t|\n,The_graph->evalue);//差距顯示pnntfC 3)/〃/〃/〃評(píng)價(jià)函數(shù)mtEvaluate(Graph*The_gi-aph,Graph*End_graph)(intvalute=O;//差E巨數(shù)mtij;fbr(i=O;i<N;i-H-)(for(j=0;j<N;j++)(if(The_graph->fbi-m[i]|j]!=End_gi-apli->fonn[i][j])(valute++;))}The_giaph->evalue=xralute;returnvalute;}〃//〃/〃移動(dòng)數(shù)碼組Giaph*Move(Giaph*Tlie_gi-aph,mtDirect,intCreatNew_graph)(Graph*New_graph;mtHasGetBlank=O;〃是否獲取空格位置intAbleMove=1是否可移動(dòng)intfor(i=0;i<N;i++)〃獲取空格坐標(biāo)ij(for(j=0;j<N;j++)(if(The_graph->fbnn[i][j]=0)(HasGetBlaiik=l;break;))if(HasGetBlank=l)break;}〃printf("空格位S：%d,%d\nH,i,j);t_EU=J；〃移動(dòng)空格switch(Direct)(case1://_Etj-sif(t_i<0)AbleMove=0;break;case2://Ft_i++;if(t_i>=N)AbleMove=0;break;case3://左if(tJ<0)AbleMove=0;break;case4:〃右tj++;if(tj>=N)AbleMove=0;break;)if(AbleMove==0)〃不能移動(dòng)則返回原節(jié)點(diǎn)(returnThe_graph;}if(CreatNew_gi'aph=1)(New_graph=(Graph*)malloc(sizeof(Graph));//生成節(jié)點(diǎn)for(x=0;x<N;x-H-)(fdr(y=O;y<N;y-H-)(New_gi,aph->fbnn[x][y]=The_graph->fonn[x][y]y/fi制數(shù)碼組))}elseNew_graph=Tlie_gi-aph;)〃移動(dòng)后New_graph->fbmi[i][j]=New_gi-aph->fbnn[t_i][tj];New_graph->fdmi[t_i][tJ]=0;//pnntf("移動(dòng)產(chǎn)生的新圖M");〃Print(New_graph);returnNew_graph;)///〃〃〃搜索函數(shù)Gi-aph*Search(Graph*Begm,Graph*End){Graph*gl,*g2,*g;intStep=O〃深度intDirect=O;〃方向inti;intfront,rear;fiont=i-eai--l-J/隊(duì)列初始化g=NULL;rear++;〃入隊(duì)Qu[rear]=Begin;while(rear!=fi*ont)〃隊(duì)列不空{(diào)fh)nt++；//出隊(duì)gl=Qu[front];//printf("開始第％d個(gè)圖M:fixmt);//Pimt(gl);for(i=1;iv=4;i++)〃分別從四個(gè)方向推導(dǎo)出新子節(jié)點(diǎn)(Direct=i;if(Du-ect=g1-Xidirect)〃跳過屏蔽方向continue;g2=Move(gl,Direct,1)；〃移動(dòng)數(shù)碼組if(g2!=gl)〃數(shù)碼組是否可以移動(dòng)(〃可以移動(dòng)Evahiate(g2,End);〃評(píng)價(jià)新的節(jié)點(diǎn)〃prmtf("開始產(chǎn)生的第％d個(gè)圖//Piiiit(g2);if(g2->evalue<=gl->evalue+1)〃是優(yōu)越節(jié)點(diǎn)g2->pai-ent=gl;〃移動(dòng)空格switch(Direct)〃設(shè)置屏蔽方向，防止往回推(case1://Jtg2->udii'ect=2;break;case2:〃下g2->udii'ect=l;break;case3:〃左g2->udiiect=4;break;case4:〃右g2->udii'ect=3;break;)rear4-+;Qu[rear]=g2;〃存儲(chǔ)節(jié)點(diǎn)到待處理隊(duì)列if(g2->evalue==0)〃為0則搜索完成(g=g2；//i=5;break;)}else{fiee(g2);//拋棄劣質(zhì)節(jié)點(diǎn)g2=NULL;})}if(g!=NULL)〃為0則搜索完成(if(g->evalue==O)break;Step++〃統(tǒng)計(jì)深度if(Step>Max_Step)(break;}}retunig;}mtmam(mtargc,constchar*argv口)(//insertcodehere...GraphBegm_graph={{{2,8,3},{1,6,4},{7,0,5}},0ANULL)；/*9GraphBegm_graph={{{2,8,3},{l,0,4},{7,6,5}},0ANULL)；GraphBegm_graph={{{2,0,l},{4,6,5},{3,7,8}},0ANULL)；*/〃目標(biāo)數(shù)碼組GraphEnd_graph={{{1,2,3},{8,O,4},{7,6,5}},OANULL)；Evaluate(&Begin_gi,aph,&End_graph);〃對(duì)初始的數(shù)碼組評(píng)價(jià)pnntf("初始數(shù)碼組:\n”)；Pnnt(&Begm_graph);pnntf("目標(biāo)數(shù)碼組:\n”)；Pnnt(&End_graph);Graph*G?*P:inttop=-l;〃圖搜索G=Search(&Begm_graph,&End_graph);〃打印if(G){〃把路徑倒序P=G;〃壓棧while(P!=NULL)(top++;St[top]=P;P=P->parent;)pnntf(yvvvvvvvvvvvvvv搜索結(jié)^????????\iiH);〃彈棧打印while(top>-l)(P=St[top];top--;Prmt(P);)pniitf(,,<????????^Mc???>?????>\iin);}else{prmtf("搜索不到結(jié)果，深度為％d'uV,Max_Step);〃設(shè)計(jì)搜索深度范圍主要是防止隊(duì)列內(nèi)存越界)retiim0;六、實(shí)驗(yàn)結(jié)果C-O227863860fi3803721721717071f86137342.345差距：4342.345313453434□差距：eex