人工智能A算法九宮格報(bào)告

1、 人工智能原理與方法A*算法實(shí)現(xiàn)八數(shù)碼搜索問題模式識(shí)別與智能系統(tǒng)SY1003113游遵文題目：編程實(shí)現(xiàn)8數(shù)碼問題初始狀態(tài)：38215764目標(biāo)狀態(tài):12384765要求：1、報(bào)告：給出狀態(tài)表示，編碼規(guī)則，搜索算法A*，簡(jiǎn)單程序說(shuō)明，最優(yōu)路徑。2、調(diào)通的程序（語(yǔ)言不限）狀態(tài)表示用一個(gè)3X3的數(shù)組來(lái)表示狀態(tài)，數(shù)組中的各個(gè)元素對(duì)應(yīng)狀態(tài)位置的數(shù)字。其中空格用0表示。編碼規(guī)則在程序?qū)崿F(xiàn)過(guò)程中，只有移動(dòng)0的位置，即可生成新的節(jié)點(diǎn)。規(guī)則庫(kù)設(shè)數(shù)組中0的位置為aij，其中WW,WW。R1：if（三）then上移R1：if（W）then下移R1：if（三）then左移R1：if（W）then右移三、搜索算法A*用

2、于度量節(jié)點(diǎn)的“希望”的量度f(wàn)(n),即用來(lái)衡量到達(dá)目標(biāo)節(jié)點(diǎn)的路徑的可能性大小。A算法：基本思想：定義一個(gè)評(píng)價(jià)函數(shù)，對(duì)當(dāng)前的搜索狀態(tài)進(jìn)行評(píng)估，找出一個(gè)最有希望的節(jié)點(diǎn)進(jìn)行擴(kuò)展：f(n)=g(n)+h(n)，n為被評(píng)價(jià)節(jié)點(diǎn)g*(n)：從s到n的最優(yōu)路徑的實(shí)際代價(jià)h*(n):從n到g的最優(yōu)路徑的實(shí)際代價(jià)f*(n)=g*(n)+h*(n)：從s經(jīng)過(guò)n到g的最優(yōu)路徑的實(shí)際代價(jià)g(n)、h(n)、f(n)分別是g*(n)、h*(n)、f*(n)的估計(jì)值g(n)通常為從S到到n這段路徑的實(shí)際代價(jià)，則有g(shù)(n)三g*(n)h(n):是從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)Sg的最優(yōu)路徑的估計(jì)代價(jià).它的選擇依賴于有關(guān)問題領(lǐng)域的啟發(fā)信

3、息，叫做啟發(fā)函數(shù)A算法：在圖搜索的一般算法中，在搜索的每一步都利用估價(jià)函數(shù)f(n)=g(n)+h(n)對(duì)Open表中的節(jié)點(diǎn)進(jìn)行排序表中的節(jié)點(diǎn)進(jìn)行排序，找出一個(gè)最有希望的節(jié)點(diǎn)作為下一次擴(kuò)展的節(jié)點(diǎn)。在A算法中，如果滿足條件：h(n)Wh*(n)，則A算法稱為A*算法。在本算法中，為實(shí)現(xiàn)八數(shù)碼的搜索問題，定義估價(jià)函數(shù)為：f(n)=g(n)+h(n)，其中g(shù)(n)表示節(jié)點(diǎn)n在搜索樹中的深度；h(n)表示節(jié)點(diǎn)n的各個(gè)數(shù)碼到目標(biāo)位置的曼哈頓距離和。四、程序說(shuō)明1、算法實(shí)現(xiàn)的步驟：把初始節(jié)點(diǎn)SO放入Open表中，置SO的代價(jià)g(S0)=0；如果Open表為空，則問題無(wú)解，失敗退出；把Open表的第一個(gè)節(jié)點(diǎn)取

4、出放入Closed表，并記該節(jié)點(diǎn)為n考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則找到了問題的解，成功退出；若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第(2)步；擴(kuò)展節(jié)點(diǎn)n，生成其子節(jié)點(diǎn)ni,(其中i=1,2,3,)，將這些子節(jié)點(diǎn)放入Open表中，并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針；按公式g(ni)=g(n)+c(n，ni)(i=1，2，)計(jì)算Open表中的各子節(jié)點(diǎn)的代價(jià)，并根據(jù)各節(jié)點(diǎn)的代價(jià)對(duì)Open表中的全部節(jié)點(diǎn)按照從小到大順序重新進(jìn)行排序；然后轉(zhuǎn)第(2)步。2、思路通過(guò)代價(jià)函數(shù)對(duì)Open表中的節(jié)點(diǎn)進(jìn)行排序，代價(jià)小的先擴(kuò)展。 五、搜索算法得出的最優(yōu)路徑如下圖所示，搜索算法從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)經(jīng)歷了18個(gè)狀態(tài)。382105

5、t64Ji=8F=8靜歩382015t?64ti=9=10霰歩082f?64ti=10F=12影歩802315t64Ji=9F=12靜歩81230564ti=8=12興歩812035?64ti=7F=12象歩812r?35064Ji=8F=14靜歩812r?35604ti=9=16靜歩B1t3B4ti=i0靜歩812t?30645Ji=9F=18第10歩ei2t83&45h=8F=18俸“歩612r?43B05h=7F=18fcl2612r?43065h=6F=18fcl3ei2043r?65h=5F=18和歩012843t65h=4F=18希5歩102643t?65h=3F=18fcl612

6、043r?65h=2F=18俸佃歩123840t65h=lF=18律L&歩12304t?65h=0F=18淸按任意鍵繼續(xù)-圖l.VisualC+環(huán)境下運(yùn)行結(jié)果 六、結(jié)論通過(guò)這次的實(shí)驗(yàn)，深入了解了啟發(fā)式搜索算法的內(nèi)涵，尤其是A*算法的優(yōu)越性。然而在實(shí)際工程中，選擇合適、優(yōu)異的估價(jià)函數(shù)存在一定困難，特別要注意其信息量的強(qiáng)度不能超過(guò)其上限值，否則A*算法會(huì)變成A算法；而A算法是非充分的，即可能不在其最優(yōu)路徑上，從而導(dǎo)致不能找到目標(biāo)節(jié)點(diǎn)。同時(shí)，在實(shí)驗(yàn)過(guò)程中，也熟悉了C+編程和VC的開發(fā)環(huán)境；但編程能力還是極其有限，急需提升。附錄：C+源代碼A*算法代碼的核心部分pnodemove(pnodep,int

7、dir)pnodeUnode=(pnode)malloc(sizeof(node);for(inti=0;i=2;i+)for(intj=0;j=2;j+)Unode-aij=p-aij;switch(dir)case1:/upUnode-x=p-xT;Unode_y=p_y;Unode-aUnode-xUnode-y=0;Unode_aUnode_x+lUnode_y=p_aUnode_xUnode_y;break;case2:/downUnode_father=p;Unode_g=p_g+1;/深度增加一層Unode_h=hvalue(Unode_a,final);/更新h函數(shù)值Unode

8、_f=Unode_h+Unode_g;returnUnode;intmain(intargc,char*argv)pnodeA0=(pnode)malloc(sizeof(node);pnodeopen,/open表頭close,/close表頭now,/當(dāng)前節(jié)點(diǎn)Lnode,Rnode,Unode,Dnode,/下一個(gè)左，右，上，下節(jié)點(diǎn)fnode;/終節(jié)點(diǎn) #close表中initial(AO,start);open=A0;close=NULL;while(1)if(open=NULL)fnode=NULL;cout未能找到解return0;if(open-h=0)fnode=open;ope

9、n=open-next;fnode-next=NULL;fnode-clnext=close;close=fnode;break;now=open;intX,Y;X=now-x;Y=now-y;/Open表為空，未找到解，結(jié)束搜索程序/open表中第一個(gè)節(jié)點(diǎn)是解，結(jié)束搜索/把finalnode從open表中拿出，放到 #if(X0)&(now-father=NULL|now-father-x!=XT)Unode=move(now,l);/空格上移，得到新節(jié)點(diǎn)insert(Unode,open);/把新節(jié)點(diǎn)插入open表中if(X0)&(now-father=NULL|now-father-y!=YT)Lnode=move(now,3);insert(Lnode,open);if(Yfather;while(fnode!=NULL)disp(fnode)