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

1、人工智能實驗報告實驗名稱：八數(shù)碼問題:XX學號：2012210XXXX計算機學院2014年1月14日一實驗目的掌握A*的思想，啟發(fā)式搜索，來求解在代價最小的情況下將九宮格從一個狀態(tài)轉為另狀態(tài)的路徑。二實驗容給定九宮格的初始狀態(tài)，要求在有限步的操作，使其轉化為目標狀態(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到目標點的估價函數(shù) g(n)是在狀態(tài)空 間中從初始節(jié)點到n節(jié)點的實際代價，h(n)是從n到目標節(jié)點最佳路徑的估計 代價。保證找到最短路徑(最優(yōu)解的)條件，關鍵在于估價函數(shù)h(n)的選取： 估價值h(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); / 先把未改變的九宮格復制給九宮格數(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)解。關鍵代碼：bool Houristic.Scarch(Sudoku start, Sudoku end) int a=0, b=0,c=0;int count=0;NOExtend.Sudoku ns;/未擴展結點表ExtendedSudoku es;/ 已擴展結點表Path

5、 path;/求解路徑NOExtend father;定義父節(jié)點ns. no_nodca cur_sudoku二start;/初始化未拓展結點表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) /當未拓展結點表不為空時父節(jié)點為為拓展表的第一個結點 /記錄求解路徑/從未拓展表中刪除第一個結點father=ns noiodc0; path. pac+二father; DeleteFirst(n

6、s, a);a-;if(Equa 1 SudokuCfather, cursudoku, end)如果找到 了 目標九宮格則輸出求解路徑ShowPath(path, c);return 1;NOExtend child4;/因為九宮格只能拓展上下左右四個方向所以拓展出的結點最多有四個CreateChildCchild, father);/生成父節(jié)點的擴展結點if(ICreatcChild(chiId, father)continue;/如果沒有擴展結點就跳出進行下一次循環(huán)for(int i=0;i4;i+)if(childi.dx=l)/對于父節(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);/獲取此結點的估價值 ns. no_nodca=chi1d i;ns. no_node_fathcra二father;a+;continue;if(ExistNOExtendCns, childiJ. cur_sudoku)/如果未拓展表中有此狀態(tài)，此求得當前狀態(tài)的估價值并且與表中存 在的此狀態(tài)的估價值比較/若估價值大就放棄此結點，更小，就加入此

8、結點 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)，此求得當前狀態(tài)的估價值并且與表中存 在的此狀態(tài)的估價值比較/若估價值大就放棄此結點，更小，就加入此結點 Value(childi, father, end);if(childi. fxMAXPATH)break;return 0;六、實驗心得1、學習了新的算法A*算法，結合了偽代碼和網(wǎng)上的一些