【正文】 決8數(shù)碼問(wèn)題的編程實(shí)現(xiàn) 基于A*算法解決把數(shù)碼問(wèn)題 《人工智能》 專 業(yè)： 信息與計(jì)算科學(xué) 班 級(jí)： 101001 學(xué) 號(hào)： 101001102 姓 名： 陳 斌 指導(dǎo)老師： 時(shí) 華 日 期：2013年10月14日一、問(wèn)題描述8數(shù)碼問(wèn)題又稱9宮問(wèn)題，與游戲“華容道”類似。為方便編程和表示，本文中8個(gè)格子內(nèi)的符號(hào)分別取1—8的8個(gè)數(shù)字表示，空格用0表示。但要在計(jì)算機(jī)上通過(guò)編程解決該問(wèn)題，還應(yīng)當(dāng)解決該問(wèn)題在計(jì)算機(jī)上表示的方式，并設(shè)計(jì)合適的啟發(fā)函數(shù)，以提高搜索效率。如圖3所示，表示問(wèn)題的結(jié)構(gòu)體包括表示當(dāng)前節(jié)點(diǎn)狀態(tài)的DATA和指向open表中下一個(gè)待擴(kuò)展節(jié)點(diǎn)的指針NEXT。根據(jù)A*算法的定義，當(dāng)前節(jié)點(diǎn)的代價(jià)值由估價(jià)函數(shù)給出，即：其中：表示當(dāng)前節(jié)點(diǎn)n在搜索樹中的深度； 是啟發(fā)函數(shù)。圖4 問(wèn)題的狀態(tài)表示②啟發(fā)函數(shù)的設(shè)計(jì)根據(jù)A*算法的定義，啟發(fā)函數(shù)應(yīng)滿足：。顯然，后者的不小于前者，因此本文中采用數(shù)碼“不在位”的距離和作為啟發(fā)函數(shù)。因此移動(dòng)的規(guī)則庫(kù)可以寫成如下形式：左移：if(pj_0=1) //空格所在列號(hào)不小于1,可左移 { temp=pfather。amp。amp。 //新節(jié)點(diǎn)與其祖父節(jié)點(diǎn)相同，無(wú)操作 else //新節(jié)點(diǎn)與其祖父節(jié)點(diǎn)不同，或其父節(jié)點(diǎn)為起始節(jié)點(diǎn) { ……(擴(kuò)展新節(jié)點(diǎn)，并判斷是否加入open表)//詳細(xì)代碼見源程序 } }//end右移上移：if(pi_0=1) //空格所在列號(hào)不小于1,可上移 { temp=pfather。amp。amp。 //新節(jié)點(diǎn)與其祖父節(jié)點(diǎn)相同，無(wú)操作 else //新節(jié)點(diǎn)與其祖父節(jié)點(diǎn)不同，或其父節(jié)點(diǎn)為起始節(jié)點(diǎn) { ……(擴(kuò)展新節(jié)點(diǎn)，并判斷是否加入open表)//詳細(xì)代碼見源程序 } }//end下移④程序流程主程序流程圖：其中，擴(kuò)展節(jié)點(diǎn)n的具體步驟如下：a) 首先判斷其是否在closed表已經(jīng)出現(xiàn)過(guò), 如果出現(xiàn)過(guò)，并且新節(jié)點(diǎn)的代價(jià)值比其小，則應(yīng)將其從closed表刪除，同時(shí)將新節(jié)點(diǎn)加入到open表；如果沒(méi)有出現(xiàn)過(guò)，則轉(zhuǎn)b。void Calculate_f(int deepth,struct node *p)。int Test_A_B(struct node *p1,struct node *p2)。void Print_result(struct node *p)。 //當(dāng)前空格所在列號(hào) int f。 //指向解路徑上該節(jié)點(diǎn)的父節(jié)點(diǎn) struct node *next。 //定義目標(biāo)狀態(tài)struct node *open=NULL。 Copy_node(amp。s)。 //輸出解路徑 else printf(問(wèn)題求解失?。?。 Add_to_open(p)。 open=temp。 //擴(kuò)展節(jié)點(diǎn)n } return NULL。amp。 else //新節(jié)點(diǎn)與其祖父節(jié)點(diǎn)不同，或其父節(jié)點(diǎn)為起始節(jié)點(diǎn) { temp=(struct node *)malloc(sizeof(struct node))。 tempj_0。 //新節(jié)點(diǎn)指向其父節(jié)點(diǎn) if(same=Search_A(closed,temp)) //在closed表中找到與新節(jié)點(diǎn)狀態(tài)相同的節(jié)點(diǎn) { if(tempfsamef) //temp指向的節(jié)點(diǎn),其代價(jià)比closed表中相同狀態(tài)節(jié)點(diǎn)代價(jià)小，加入open表 { Remove_p(closed,same)。 } else if(same=Search_A(open,temp)) //在open表中找到與新節(jié)點(diǎn)狀態(tài)相同的節(jié)點(diǎn) { if(tempfsamef) //temp指向的節(jié)點(diǎn),其代價(jià)比open表中相同狀態(tài)節(jié)點(diǎn)代價(jià)小，加入open表 { Remove_p(open,same)。 } else //新節(jié)點(diǎn)為完全不同的新節(jié)點(diǎn)，加入open表 { Add_to_open(temp)。amp。 else //新節(jié)點(diǎn)與其祖父節(jié)點(diǎn)不同，或其父節(jié)點(diǎn)為起始節(jié)點(diǎn) { temp=(struct node *)malloc(sizeof(struct node))。 tempj_0++。 //新節(jié)點(diǎn)指向其父節(jié)點(diǎn) if(same=Search_A(closed,temp)) //在closed表中找到與新節(jié)點(diǎn)狀態(tài)相同的節(jié)點(diǎn) { if(tempfsamef) //temp指向的節(jié)點(diǎn),其代價(jià)比closed表中相同狀態(tài)節(jié)點(diǎn)代價(jià)小，加入open表 { Remove_p(closed,same)。 } else if(same=Search_A(open,temp)) //在open表中找到與新節(jié)點(diǎn)狀態(tài)相同的節(jié)點(diǎn) { if(tempfsamef) //temp指向的節(jié)點(diǎn),其代價(jià)比open表中相同狀態(tài)節(jié)點(diǎn)代價(jià)小，加入open表 { Remove_p(open,same)。 } else //新節(jié)點(diǎn)為完全不同的新節(jié)點(diǎn)，加入open表 { Add_to_open(temp)。amp。 else //新節(jié)點(diǎn)與其祖父節(jié)點(diǎn)不同，或其父節(jié)點(diǎn)為起始節(jié)點(diǎn) { temp=(struct node *)malloc(sizeof(struct node))。 tempi_0。 //新節(jié)點(diǎn)指向其父節(jié)點(diǎn) if(same=Search_A(closed,temp)) //在closed表中找到與新節(jié)點(diǎn)狀態(tài)相同的節(jié)點(diǎn) { if(tempfsamef) //temp指向的節(jié)點(diǎn),其代價(jià)比closed表中相同狀態(tài)節(jié)點(diǎn)代價(jià)小，加入open表 { Remove_p(closed,same)。 } else if(same=Search_A(open,temp)) //在open表中找到與新節(jié)點(diǎn)狀態(tài)相同的節(jié)點(diǎn) { if(tempfsamef) //temp指向的節(jié)點(diǎn),其代價(jià)比open表中相同狀態(tài)節(jié)點(diǎn)代價(jià)小，加入open表 { Remove_p(open,same)。 } else //新節(jié)點(diǎn)為完全不同的新節(jié)點(diǎn)，加入open表 { Add_to_open(temp)。a