A星算法求八數(shù)碼問題實(shí)驗(yàn)報告

1、人工智能實(shí)驗(yàn)報告實(shí)驗(yàn)名稱：八數(shù)碼問題姓名： xx學(xué)號： 2012210xxxx 計算機(jī)學(xué)院2014年 1 月 14日一.實(shí)驗(yàn)?zāi)康恼莆誂*的思想，啟發(fā)式搜索，來求解在代價最小的情況下將九宮格從一 個狀態(tài)轉(zhuǎn)為另狀態(tài)的路徑。二.實(shí)驗(yàn)內(nèi)容給定九宮格的初始狀態(tài)，要求在有限步的操作內(nèi)，使其轉(zhuǎn)化為目標(biāo)狀態(tài)，且 所得到的解是代價最小解(即移動的步數(shù)最少)并打印出求解路徑。例如283164705283164705三、A*算法思想：1、思想：A*算法是一種靜態(tài)路網(wǎng)中求解最短路最有效的直接搜索方法。估價值與實(shí)際值越接近，估價函數(shù)取得就越好2、原理：估價函數(shù)公式表示為：f(n)=g(n)+h(n),其中f(n) 是從

2、初始點(diǎn)經(jīng)由節(jié)點(diǎn)n到目標(biāo)點(diǎn)的估價函數(shù)，g(n)是在狀態(tài)空 問中從初始節(jié)點(diǎn)到n節(jié)點(diǎn)的實(shí)際代價，h(n)是從n到目標(biāo)節(jié)點(diǎn)最佳路徑的估計 代價。保證找到最短路徑(最優(yōu)解的)條件，關(guān)鍵在于估價函數(shù)h(n)的選?。汗纼r值h(n)<= n到目標(biāo)節(jié)點(diǎn)的距離實(shí)際值，這種情況下，搜索的點(diǎn)數(shù)多，搜索 范圍大，效率低。但能得到最優(yōu)解。并且如果 h(n尸d(n),即距離估計h(n)等于 最短距離，那么搜索將嚴(yán)格沿著最短路徑進(jìn)行此時的搜索效率是最高的。如果估價值>實(shí)際值，搜索的點(diǎn)數(shù)少，搜索范圍小，效率高，但不能保證得到最優(yōu)解。四、算法流程:Heuristic_Search（啟發(fā)式搜索）While （未拓展表不

3、為空？）i從未拓展表中刪除第一個狀態(tài)nN為目標(biāo)狀態(tài)?是，輸出路徑否，生成n的所有子狀態(tài)Case:此子狀態(tài)不在拓展表和 未拓展表中Case:此子狀態(tài)在未拓展表中Case:此子狀態(tài)在拓展表計算該子狀態(tài)的估價函 數(shù)值；記錄比已有的路徑更短 的路徑記錄比已有的路徑更短 的路徑五、關(guān)鍵技術(shù)：1、使用了CreateChild ()函數(shù)，求得了任意未拓展九宮格的擴(kuò)展結(jié)點(diǎn)，便于拓展子空間，搜索所有情況。關(guān)鍵代碼：bool CreateChild(NOExtend ns,NOExtend ne)int i,j,k=0;for(i=0;i<3;i+)for(j=0;j<3;j+)if(ne.cur_s

4、udoku.numij=0) /尋找九宮格空缺所在的坐標(biāo)if(i-1>=0)/將空格向上移動CopySudoku(nsk.cur_sudoku,ne.cur_sudoku);/ 先把未改變的九宮格復(fù)制給九宮格數(shù)組的某一元素nsk.cur_sudoku.numij=ne.cur_sudoku.numi-1j;/然后僅改變此二維九宮格的兩項(xiàng)值即可nsk.cur_sudoku.numi-1j=0;nsk.dx=1;k+;if(j+1<=2)/將空格向右移動CopySudoku(nsk.cur_sudoku,ne.cur_sudoku);nsk.cur_sudoku.numij=nsk.c

5、ur_sudoku.numij+1;nsk.cur_sudoku.numij+1=0;nsk.dx=1;k+;if(i+1<=2)/將空格向下移動CopySudoku(nsk.cur_sudoku,ne.cur_sudoku);nsk.cur_sudoku.numij=nsk.cur_sudoku.numi+1j;nsk.cur_sudoku.numi+1j=0;nsk.dx=1;k+;if(j-1>=0)/將空格向左移動CopySudoku(nsk.cur_sudoku,ne.cur_sudoku);nsk.cur_sudoku.numij=nsk.cur_sudoku.numi

6、j-1;nsk.cur_sudoku.numij-1=0;nsk.dx=1;k+;return 1;return 0;2、用啟發(fā)式搜索函數(shù)尋找求解路徑，運(yùn)用了最優(yōu)解。關(guān)鍵代碼：bool Heuristic_Search(Sudoku start,Sudoku end)A*算法的思想，能夠更快的求解出int a=0,b=0,c=0;int count=0;NOExtend_Sudoku ns;/Extended_Sudoku es;/Path path;/NOExtend father;/未擴(kuò)展結(jié)點(diǎn)表已擴(kuò)展結(jié)點(diǎn)表求解路徑定義父節(jié)點(diǎn)ns.no_nodea.cur_sudoku=start; /初始

7、化未拓展結(jié)點(diǎn)表ns.no_nodea.dx=0;ns.no_nodea.hx=GetHx(ns.no_nodea.cur_sudoku,end);ns.no_nodea.fx=ns.no_nodea.dx+ns.no_nodea.hx;a+;while(a!=0) / 當(dāng)未拓展結(jié)點(diǎn)表不為空時father=ns.no_node0; /path.pac+=father;/DeleteFirst(ns,a); /a-;if(EqualSudoku(father.cur_sudoku,end) / 求解路徑ShowPath(path,c); return 1; NOExtend child4;/個方向

8、所以拓展出的結(jié)點(diǎn)最多有四個 CreateChild(child,father);/if(!CreateChild(child,father) continue;/環(huán) for(int i=0;i<4;i+) if(childi.dx=1) /父節(jié)點(diǎn)為為拓展表的第一個結(jié)點(diǎn)記錄求解路徑從未拓展表中刪除第一個結(jié)點(diǎn)如果找到了目標(biāo)九宮格則輸出因?yàn)榫艑m格只能拓展上下左右四生成父節(jié)點(diǎn)的擴(kuò)展結(jié)點(diǎn)如果沒有擴(kuò)展結(jié)點(diǎn)就跳出進(jìn)行下一次循對于父節(jié)點(diǎn)可以生成的每個子結(jié)點(diǎn)if(!ExistNOExtend(ns,childi.cur_sudoku)&&!ExistExtended(es,childi.c

9、ur_s udoku)/ 如果未拓展表和已拓展表中都沒有此狀態(tài)，則添加此狀態(tài)到未拓展表中Value(childi,father,end);/獲取此結(jié)點(diǎn)的估價值ns.no_nodea=childi;ns.no_node_fathera=father;a+;continue;if(ExistNOExtend(ns,childi.cur_sudoku)/ 如果未拓展表中有此狀態(tài)，此求得當(dāng)前狀態(tài)的估價值并且與表中存在的此狀態(tài)的估價值比較/ 若估價值大就放棄此結(jié)點(diǎn)，更小，就加入此結(jié)點(diǎn)Value(childi,father,end);if(childi.fx<father.fx)ns.no_node

10、a=childi;ns.no_node_fathera=father;a+;continue;if(ExistExtended(es,childi.cur_sudoku)/ 如果已拓展表中有此狀態(tài)，此求得當(dāng)前狀態(tài)的估價值并且與表中存在的此狀態(tài)的估價值比較/ 若估價值大就放棄此結(jié)點(diǎn)，更小，就加入此結(jié)點(diǎn)Value(childi,father,end);if(childi.fx<es.node0.value)/當(dāng)子狀態(tài)的價值小與已經(jīng)掃描過的狀態(tài)時ns.no_nodea=childi;ns.no_node_fathera=father;a+;/a 為未拓展表中的元素個數(shù) continue;es.nodeb.cur_sudoku=father.cur_sudoku; /將已經(jīng)生成完拓展結(jié)點(diǎn)的父節(jié)點(diǎn)放入已拓展表中es.nodeb.value=father.fx;b+; /b 為已拓展表中的元素個數(shù)SortNoExtend(ns,a); / 根據(jù)估價函數(shù)值，從小到大重新排列未拓展表，每次只搜索估價值最小的結(jié)點(diǎn)的路徑if(count+>MAXPATH)b