A星算法求八數(shù)碼問題實驗報告教學(xué)知識

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

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

3、表不為空？）是從未拓展表中刪除第一個狀態(tài)nn為目標狀態(tài)？ 是，輸出路徑否，生成n的所有子狀態(tài)case:此子狀態(tài)在拓展表case:此子狀態(tài)在未拓展表中case:此子狀態(tài)不在拓展表和未拓展表中記錄比已有的路徑更短的路徑記錄比已有的路徑更短的路徑計算該子狀態(tài)的估價函數(shù)值；返回5、 關(guān)鍵技術(shù)：1、 使用了createchild（）函數(shù)，求得了任意未拓展九宮格的擴展結(jié)點，便于拓展子空間，搜索所有情況。關(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

4、_sudoku.numij=0) /尋找九宮格空缺所在的坐標if(i-1>=0) /將空格向上移動copysudoku(nsk.cur_sudoku,ne.cur_sudoku);/先把未改變的九宮格復(fù)制給九宮格數(shù)組的某一元素nsk.cur_sudoku.numij=ne.cur_sudoku.numi-1j;/然后僅改變此二維九宮格的兩項值即可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=ns

5、k.cur_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

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

7、tart; /初始化未拓展結(jié)點表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é)點表不為空時 father=ns.no_node0; /父節(jié)點為為拓展表的第一個結(jié)點 path.pac+=father; /記錄求解路徑 deletefirst(ns,a); /從未拓展表中刪除第一個結(jié)點 a-; if(equalsudoku(father.cur_sudoku,end) /如果找

8、到了目標九宮格則輸出求解路徑 showpath(path,c); return 1; noextend child4; /因為九宮格只能拓展上下左右四個方向所以拓展出的結(jié)點最多有四個 createchild(child,father); /生成父節(jié)點的擴展結(jié)點 if(!createchild(child,father) continue; /如果沒有擴展結(jié)點就跳出進行下一次循環(huán) for(int i=0;i<4;i+) if(childi.dx=1) /對于父節(jié)點可以生成的每個子結(jié)點 if(!existnoextend(ns,childi.cur_sudoku)&&!exi

9、stextended(es,childi.cur_sudoku)/如果未拓展表和已拓展表中都沒有此狀態(tài)，則添加此狀態(tài)到未拓展表中 value(childi,father,end);/獲取此結(jié)點的估價值 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é)點，更小，就加入此結(jié)點 value(childi,father,end); if(childi.

10、fx<father.fx) ns.no_nodea=childi; ns.no_node_fathera=father; a+; continue; if(existextended(es,childi.cur_sudoku)/如果已拓展表中有此狀態(tài)，此求得當(dāng)前狀態(tài)的估價值并且與表中存在的此狀態(tài)的估價值比較/若估價值大就放棄此結(jié)點，更小，就加入此結(jié)點 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é)點的父節(jié)點放入已拓展表中 es.nodeb.value=father.fx; b+; /b為已拓展表中的元素個數(shù) sortnoextend(ns,a); /根據(jù)估價函數(shù)值，從小到大重新排列未拓展表，每次只搜索估價值最小的結(jié)點的路徑 if(count+>maxpath) break