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

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

2、n到目標(biāo)點的估價函數(shù) g(n)是在狀態(tài)空 間中從初始節(jié)點到n節(jié)點的實際代價，h(n)是從n到目標(biāo)節(jié)點最佳路徑的估計 代價。保證找到最短路徑(最優(yōu)解的)條件，關(guān)鍵在于估價函數(shù)h(n)的選?。?估價值h(n) 便于拓展子空間，搜索所有情況。關(guān)鎮(zhèn)代碼：bool CreatcChildCNOExtcnd ns, NOExtend nc)int i, j,k=O;for(i=0;i3;i+)for(j=0;j=0)/將空格向上移動CopifSudoku(nsk cursudoku, nc. cursudoku); / 先把未改變的九宮格復(fù)制給九宮格數(shù)組的某一元素nsk cur.sudok u. nuin

3、f i j =nc. cur.sudok u. nun讓 i-l j ;/然后僅改變此二維九宮格的兩項值即可nsk cur.sudok u. nuniF i-l j=0;nskdx=l;k+;if(j+l=2)/將空格向右移動CopySudoku( nsk cur_sudoku, nc cur_sudoku);nsk cur_sudoku. nuinf i j=nsk cursudoku. nuin i j+1; nsk cur_sudoku. numij+1二0;nskdx=l;k+;if(i+l=0)/將空格向左移動Copj*Sudoku(nskj cur_sudoku, nc cur_s

4、udoku);nsk cur_sudoku. nuinf i j=nsk cursudoku. nuin i j-1;nsk cur_sudoku. numij-l=0;nskdx=l;k+;return 1;return 0;word版木2 用啟發(fā)式搜索函數(shù)尋找求解路徑 運用了 A*算法的思想 能夠更快的求解出 最優(yōu)解。關(guān)鍵代碼：bool Houristic.Scarch(Sudoku start, Sudoku end) int a=0, b=0,c=0;int count=0;NOExtend.Sudoku ns;/未擴(kuò)展結(jié)點表ExtendedSudoku es;/ 已擴(kuò)展結(jié)點表Path

5、 path;/求解路徑NOExtend father;定義父節(jié)點ns. no_nodca cur_sudoku二start;/初始化未拓展結(jié)點表ns nonodefadx二0;ns. no.nodefa hx=GctHx(ns nonodea cur.sudoku, end);ns. no_nodca fx二ns no_nodca dx+ns no_nodca hx; a+;whilc(a!=0) /當(dāng)未拓展結(jié)點表不為空時父節(jié)點為為拓展表的第一個結(jié)點 /記錄求解路徑/從未拓展表中刪除第一個結(jié)點father=ns noiodc0; path. pac+二father; DeleteFirst(n

6、s, a);a-;if(Equa 1 SudokuCfather, cursudoku, end)如果找到 了 目標(biāo)九宮格則輸出求解路徑ShowPath(path, c);return 1;NOExtend child4;/因為九宮格只能拓展上下左右四個方向所以拓展出的結(jié)點最多有四個CreateChildCchild, father);/生成父節(jié)點的擴(kuò)展結(jié)點if(ICreatcChild(chiId, father)continue;/如果沒有擴(kuò)展結(jié)點就跳出進(jìn)行下一次循環(huán)for(int i=0;i4;i+)if(childi.dx=l)/對于父節(jié)點可以生成的毎個子結(jié)點if(!ExistNOEx

7、tcnd(ns, chi Id i cur_sudoku)&!ExistExtcndcd(cs, chi Idi cur_s udoku)/如果未拓展表和已拓展表中都沒有此狀態(tài)，則添加此狀態(tài)到未拓展表Valuc(childi, father,end);/獲取此結(jié)點的估價值 ns. no_nodca=chi1d i;ns. no_node_fathcra二father;a+;continue;if(ExistNOExtendCns, childiJ. cur_sudoku)/如果未拓展表中有此狀態(tài)，此求得當(dāng)前狀態(tài)的估價值并且與表中存 在的此狀態(tài)的估價值比較/若估價值大就放棄此結(jié)點，更小，就加入此

8、結(jié)點 Value(childi, father, end);if (ch 訂 d訂.fxfather. fx)ns. no_nodca二childi;ns. no_node-fathcra=fathcr;a+;continue;i f(Ex i stExtended(es, childi cur_sudoku)/如果已拓展表中有此狀態(tài)，此求得當(dāng)前狀態(tài)的估價值并且與表中存 在的此狀態(tài)的估價值比較/若估價值大就放棄此結(jié)點，更小，就加入此結(jié)點 Value(childi, father, end);if(childi. fxMAXPATH)break;return 0;六、實驗心得1、學(xué)習(xí)了新的算法A*算法，結(jié)合了偽代碼和網(wǎng)上的一些