人工智能-八數(shù)碼游戲問題_第1頁
人工智能-八數(shù)碼游戲問題_第2頁
人工智能-八數(shù)碼游戲問題_第3頁
人工智能-八數(shù)碼游戲問題_第4頁
人工智能-八數(shù)碼游戲問題_第5頁
已閱讀5頁,還剩6頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

1、實驗八數(shù)碼游戲問題一、八數(shù)碼游戲問題簡介九宮排字問題(乂稱八數(shù)碼問題)是人工智能當(dāng)中有名的難題之一。問題是在3X3方格盤上,放有八個數(shù)碼,剩下第九個為空,每一空格其上下左右的數(shù)碼可移至空格。(a)初始狀態(tài)圖(b)(a)初始狀態(tài)圖(b)目標狀態(tài)八數(shù)碼游戲二、實驗?zāi)康?熟悉人工智能系統(tǒng)中的問題求解過程;.熟悉狀態(tài)空間的盲目搜索和啟發(fā)式搜索算法的應(yīng)用;.熟悉對八數(shù)碼問題的建模、求解及編程語言的應(yīng)用。三、實驗的思路八數(shù)碼問題:在3X3的方格棋盤上,擺放著1到8這八個數(shù)碼,有1個方格是空的,其初始狀態(tài)如圖1所示,要求對空格執(zhí)行空格左移、空格右移、空格上移和空格下移這四個操作使得棋盤從初始狀態(tài)到目標狀態(tài)。

2、例如:圖1八數(shù)碼問題示意圖數(shù)碼結(jié)構(gòu)體數(shù)碼結(jié)構(gòu)體typedefstnictnode(intfonnNN;intevalue;intudirec;右stmctnodeparent;Graph;Giaph*QuMAX;隊歹ljGraph*StMAX;堆棧.啟發(fā)函數(shù)設(shè)定由八數(shù)碼問題的部分狀態(tài)圖可以看出,從初始節(jié)點開始,在通向目標節(jié)點的路徑上,各節(jié)點的數(shù)碼格局同目標節(jié)點相比較,其數(shù)碼不同的位置個數(shù)在逐漸減少,最后為零,因此可以把數(shù)碼不同的位置個數(shù)作為標志一個節(jié)點到目標節(jié)點距離遠近的一個啟發(fā)性信息,利用這個信息來擴展節(jié)點的選擇,減少搜索范圍,提高搜索速度。.搜索過程:(搜索采用廣度搜索方式,利用待處理隊列

3、輔助,逐層搜索(跳過劣質(zhì)節(jié)點)a、把初始數(shù)碼組壓入隊列;b、從隊列中取出一個數(shù)碼組節(jié)點;c、擴展子節(jié)點,即從上下左右四個方向移動空格,生成相應(yīng)子節(jié)點:d、對子節(jié)點數(shù)碼組作評估,是否為優(yōu)越節(jié)點,即其評估值是否小于等于其父節(jié)點加一,是則將其壓入隊,否則拋棄。e、判斷壓入隊的子節(jié)點數(shù)碼組(優(yōu)越點)的評估值,為零則表示搜索完成,退出搜索;f、跳到步驟2;四、數(shù)據(jù)結(jié)構(gòu)的設(shè)計/八數(shù)碼結(jié)構(gòu)體數(shù)碼組評估值,差距所屏蔽方向,防止往回推到上一狀態(tài),1上2下3左4父節(jié)點起始)五、實驗過程及代碼#mclude設(shè)計了搜索深度范圍,防止隊列內(nèi)存越界#include#includedefineN3數(shù)碼組大小defineMa

4、x_Step50最大搜索深度defineMAX50typedefstinctnode/八數(shù)碼結(jié)構(gòu)體intformNN;數(shù)碼組intevahie;/評估值intudirect;所屏蔽方向,防止往回推到上已狀態(tài),1上2下3左4右stiuctnode*parent;父節(jié)點Graph;Graph*QuMAX;/隊歹ijGi-aph*StMAX;堆棧/打印數(shù)碼組voidPrint(Graph*The_graph)mtij;if(The_gi-aph=NULL)pnntf(”圖為空n)elsepnntffnM);for(i=0;iN;i+)(pmitf(n|tH);for(j=0;jfbrmij);遍歷打

5、印pinitfC,t|nn);pniitf(n|ttt差距:%dt|ir:The_graph-evahie);/差距顯示pnntffnM);/評價函數(shù)mtEvaluate(Graph*The_giaph,Graph*End_graph)intTalute=O;/差E巨數(shù)mtij;fbr(i=O;iN;i-H-)for(j=0;jfbmii|j!=End_giaph-fonnij)(valute+;The_giaph-evalue=xralute;returnvalute;/移動數(shù)碼組Graph*Move(Graph*Tlie_giaph,mtDirect,intCreatNew_graph)G

6、raph*New_graph;intHasGetBlank=O;是否獲取空格位置intAbleMove=1;是否可移動intfor(i=0;iN;i+)獲取空格坐標ijfor(j=0;jfbimij=0)(HasGetBlaiik=l;break;if(HasGetBlank=l)break;prin氓”空格位置:%d,%dn”,i,j);t戶U=J;移動空格switch(Direct)case1:/_Etj-sif(t_i=N)AbleMove=0;break;case3:/左if(U=N)AbleMove=0;break;if(AbleMove=0)不能移動則返回原節(jié)點returnThe_

7、graph;)if(CreatNew_gi,aph=1)New_graph=(Graph*)malloc(sizeof(Graph);/生成節(jié)點for(x=0;xN;x+)(fbr(yO;yfbnnxy=The_graph-fomixy;/目制數(shù)碼組)elseNew_graph=The_graph;移動后New_graph-fdmiij=New_gi-aph-fbnnt_itj;New_graph-fbnnt_it_j=O;/pnntf(移動產(chǎn)生的新圖:n);/Print(New_graph);retiimNew_graph;/搜索函數(shù)Graph*Search(GraphBegin,Graph

8、*End)Graph*gl,*g2,*g;intStep=O;深度intDirect=O;方向inti;intfront,rear;fiont=i-eai-l-Jf隊列初始化g=NULL;reai+;入隊Qurear=Begin;while(rear!=fixmt)隊列不空fhmHT;出隊gl=Qufront;“printf(開始第d個圖ont);/Pimt(gl);for(i=1;iv=4;i+)分別從四個方向推導(dǎo)出新子節(jié)點(Duect=i;if(Du-ect=g1-udirect)跳過屏蔽方向contmue;g2=Move(gl,Direct,1);移動數(shù)碼組if(g2!=gl)數(shù)碼組是否

9、可以移動(可以移動Evahiate(g2,End);評價新的節(jié)點pnntf(開始產(chǎn)生的第d個圖:/Print(g2);if(g2-evalueevalue+1)是優(yōu)越節(jié)點g2-parent=gl;移動空格switch(Direct)設(shè)置屏蔽方向,防止往回推(case1:/Jtg2-udirect=2;break;case2:下g2-udu,ect=l;break;case3:左g2-udkect=4;break;case4:右g2-udirect=3;break;)rear4-+;Qurear=g2;存儲節(jié)點到待處理隊列if(g2-evalue=0)為0則搜索完成(g=g2;/i=5;brea

10、k;)else(丘ee(g2);拋棄劣質(zhì)節(jié)點g2=NULL;)if(g!=NULL)為0則搜索完成(if(g-evalue=O)break;Step+;統(tǒng)計深度if(StepMax_Step)break;retiinig;mtmam(mtargc?constchar*argv口)/insertcodehere.GraphBegm_graph=2,8,3,1,6,4,7,0,5,0,0,NULL);/*IGraphBegm_graph=2,8,3,1,0,4,7,6,5,0,0,NULL);GraphBegm_graph=2,0,1,4,6,5,3,7,8,0,0,NULL);*/目標數(shù)碼組Gr

11、aphEnd_graph=1,2,3,8,0,4,7,6,5,0,0,NULL);Evaluate(&Begin_gi,aph,&End_graph);/對初始的數(shù)碼組評價pnntf(初始數(shù)碼組:n”);Pnnt(&Begm_graph);pnntf(目標數(shù)碼組An);Pnnt(&End_giaph);Graph*G,*P:inttop=-l;圖搜索G=Search(&Begm_graph,&End_graph);打印if(G)把路徑倒序P=G;壓棧while(P!=NULL)(top+;Sttop=P;P=P-parent;pnntf(yv-l)(P=Sttop;top-;Prmt(P);pniitf(nin);elseprmtf(搜索不到結(jié)果,深度為dW,Max_Step);設(shè)計搜索深度范圍主要是防止隊列內(nèi)存越界)retiim0;六、實驗結(jié)果Cancer./桌面$gcc/I數(shù)碼.碼c:l:21:

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論