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

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

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

3、表不為空？）是從未拓展表中刪除第一個(gè)狀態(tài)nn為目標(biāo)狀態(tài)？ 是，輸出路徑否，生成n的所有子狀態(tài)case:此子狀態(tài)在拓展表case:此子狀態(tài)在未拓展表中case:此子狀態(tài)不在拓展表和未拓展表中記錄比已有的路徑更短的路徑記錄比已有的路徑更短的路徑計(jì)算該子狀態(tài)的估價(jià)函數(shù)值；返回5、 關(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

4、_sudoku.numij=0) /尋找九宮格空缺所在的坐標(biāo)if(i-1>=0) /將空格向上移動(dòng)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) /將空格向右移動(dòng)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) /將空格向下移動(dòng)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) /將空格向左移動(dòng)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ù)尋找求解路徑，運(yùn)用了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; /未擴(kuò)展結(jié)點(diǎn)表extended_sudoku es; /已擴(kuò)展結(jié)點(diǎn)表path path; /求解路徑noextend father; /定義父節(jié)點(diǎn)ns.no_nodea.cur_sudoku=s

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

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

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