人工智能 八數(shù)碼游戲

./實(shí)驗(yàn)一：八數(shù)碼游戲問題一、八數(shù)碼游戲問題簡(jiǎn)介九宮排字問題〔又稱八數(shù)碼問題是人工智能當(dāng)中有名的難題之一。問題是在3×3方格盤上,放有八個(gè)數(shù)碼,剩下第九個(gè)為空,每一空格其上下左右的數(shù)碼可移至空格。問題給定初始位置和目標(biāo)位置,要求通過一系列的數(shù)碼移動(dòng),將初始位置轉(zhuǎn)化為目標(biāo)位置。2831231648475765〔a初始狀態(tài)〔b目標(biāo)狀態(tài)圖八數(shù)碼游戲二、實(shí)驗(yàn)?zāi)康?.熟悉人工智能系統(tǒng)中的問題求解過程；2.熟悉狀態(tài)空間的盲目搜索和啟發(fā)式搜索算法的應(yīng)用；3.熟悉對(duì)八數(shù)碼問題的建模、求解及編程語言的應(yīng)用。三、實(shí)驗(yàn)的思路八數(shù)碼問題：在3×3的方格棋盤上,擺放著1到8這八個(gè)數(shù)碼,有1個(gè)方格是空的,其初始狀態(tài)如圖1所示,要求對(duì)空格執(zhí)行空格左移、空格右移、空格上移和空格下移這四個(gè)操作使得棋盤從初始狀態(tài)到目標(biāo)狀態(tài)。例如：28312316484705765<a>初始狀態(tài)<b>目標(biāo)狀態(tài)圖1八數(shù)碼問題示意圖啟發(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)體typedefstructnode//八數(shù)碼結(jié)構(gòu)體{intform[N][N];//數(shù)碼組intevalue;//評(píng)估值,差距intudirec;//所屏蔽方向,防止往回推到上一狀態(tài),1上2下3左4右structnode*parent;//父節(jié)點(diǎn)}Graph;Graph*Qu[MAX];//隊(duì)列Graph*St[MAX];//堆棧起始起始把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)過程及代碼#include<stdio.h>}//設(shè)計(jì)了搜索深度圍,防止隊(duì)列存越界#include<stdlib.h>#include<time.h>#defineN3//數(shù)碼組大小#defineMax_Step50//最大搜索深度#defineMAX50typedefstructnode//八數(shù)碼結(jié)構(gòu)體{intform[N][N];//數(shù)碼組intevalue;//評(píng)估值intudirect;//所屏蔽方向,防止往回推到上已狀態(tài),1上2下3左4右structnode*parent;//父節(jié)點(diǎn)}Graph;Graph*Qu[MAX];//隊(duì)列Graph*St[MAX];//堆棧/////////打印數(shù)碼組voidPrint<Graph*The_graph>{inti,j;if<The_graph==NULL>printf<"圖為空\(chéng)n">;else{printf<"\n">;for<i=0;i<N;i++>{printf<"|\t">;for<j=0;j<N;j++>{printf<"%d\t",The_graph->form[i][j]>;//遍歷打印}printf<"\t|\n">;}printf<"|\t\t\t差距:%d\t|\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;i<N;i++>{for<j=0;j<N;j++>{if<The_graph->form[i][j]!=End_graph->form[i][j]>{valute++;}}}The_graph->evalue=valute;returnvalute;}/////////移動(dòng)數(shù)碼組Graph*Move<Graph*The_graph,intDirect,intCreatNew_graph>{Graph*New_graph;intHasGetBlank=0;//是否獲取空格位置intAbleMove=1;//是否可移動(dòng)inti,j,t_i,t_j,x,y;for<i=0;i<N;i++>//獲取空格坐標(biāo)i,j{for<j=0;j<N;j++>{if<The_graph->form[i][j]==0>{HasGetBlank=1;break;}}if<HasGetBlank==1>break;}//printf<"空格位置:%d,%d\n",i,j>;t_i=i;t_j=j;//移動(dòng)空格switch<Direct>{case1://上t_i--;if<t_i<0>AbleMove=0;break;case2://下t_i++;if<t_i>=N>AbleMove=0;break;case3://左t_j--;if<t_j<0>AbleMove=0;break;case4://右t_j++;if<t_j>=N>AbleMove=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;x<N;x++>{for<y=0;y<N;y++>{New_graph->form[x][y]=The_graph->form[x][y];//復(fù)制數(shù)碼組}}}else{New_graph=The_graph;}//移動(dòng)后New_graph->form[i][j]=New_graph->form[t_i][t_j];New_graph->form[t_i][t_j]=0;//printf<"移動(dòng)產(chǎn)生的新圖:\n">;//Print<New_graph>;returnNew_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ì)Qu[rear]=Begin;while<rear!=front>//隊(duì)列不空{(diào)front++;//出隊(duì)g1=Qu[front];//printf<"開始第%d個(gè)圖:\n",front>;//Print<g1>;for<i=1;i<=4;i++>//分別從四個(gè)方向推導(dǎo)出新子節(jié)點(diǎn){Direct=i;if<Direct==g1->udirect>//跳過屏蔽方向continue;g2=Move<g1,Direct,1>;//移動(dòng)數(shù)碼組if<g2!=g1>//數(shù)碼組是否可以移動(dòng){//可以移動(dòng)Evaluate<g2,End>;//評(píng)價(jià)新的節(jié)點(diǎn)//printf<"開始產(chǎn)生的第%d個(gè)圖:\n",i>;//Print<g2>;if<g2->evalue<=g1->evalue+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++;Qu[rear]=g2;//存儲(chǔ)節(jié)點(diǎn)到待處理隊(duì)列if<g2->evalue==0>//為0則搜索完成{g=g2;//i=5;break;}}else{free<g2>;//拋棄劣質(zhì)節(jié)點(diǎn)g2=NULL;}}}if<g!=NULL>//為0則搜索完成{if<g->evalue==0>{break;}}Step++;//統(tǒng)計(jì)深度if<Step>Max_Step>{break;}}returng;}intmain<intargc,constchar*argv[]>{//insertcodehere...GraphBegin_graph={{{2,8,3},{1,6,4},{7,0,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};*///目標(biāo)數(shù)碼組GraphEnd_graph={{{1,2,3},{8,0,4},{7,6,5}},0,0,NULL};Evaluate<&Begin_graph,&End_graph>;//對(duì)初始的數(shù)碼組評(píng)價(jià)printf<"初始數(shù)碼組:\n">;