1、、實驗內容和要求 八數碼問題：在3X 3的方格棋盤上，擺放著1到8這八個數碼，有1個方格是 空的，其初始狀態如圖1所示，要求對空格執行空格左移、空格右移、空格上移 和空格下移這四個操作使得棋盤從初始狀態到目標狀態。 例如: 2 8 3 1 6 4 7 0 5 (a)初始狀態 1 2 3 8 r 4 目標狀態 (b) 圖1八數碼問題示意圖 請任選一種盲目搜索算法(廣度優先搜索或深度優先搜索) 或任選一種啟發 式搜索方法(全局擇優搜索，加權狀態圖搜索，A算法或A*算法)編程求解 八數碼問題(初始狀態任選)。選擇一個初始狀態，畫出搜索樹，填寫相應的OPEN 表和CLOSE表，給出解路徑，對實驗結果進

2、行分析總結，得出結論。 、實驗目的 1. 熟悉人工智能系統中的問題求解過程； 2. 熟悉狀態空間的盲目搜索和啟發式搜索算法的應用; 3. 熟悉對八數碼問題的建模、求解及編程語言的應用。 三、實驗算法 A*算法是一種常用的啟發式搜索算法 在A*算法中，一個結點位置的好壞用估價函數來對它進行評估。A*算法的估價 函數可表示為： f( n) = g( n) + h( n) 這里，f(n)是估價函數，g(n)是起點到終點的最短路徑值(也稱為最小耗費或 最小代價)，h(n)是n到目標的最短路經的啟發值。由于這個 f(n)其實是無法 預先知道的，所以實際上使用的是下面的估價函數： f(n) = g(n)

3、+ h(n) 其中g(n)是從初始結點到節點n的實際代價，h(n)是從結點n到目標結點的最 佳路徑的估計代價。在這里主要是 h(n)體現了搜索的啟發信息，因為 g(n)是已 知的。用f(n)作為f(n)的近似，也就是用g(n)代替g(n) ，h(n)代替h(n)。 這樣必須滿足兩個條件：(1)g(n)=g(n)(大多數情況下都是滿足的，可以不 用考慮），且f必須保持單調遞增。（2） h必須小于等于實際的從當前節點到達 目標節點的最小耗費h（ n）v=h （n）。第二點特別的重要。可以證明應用這樣的估 價函數是可以找到最短路徑的。 3.A*算法的步驟 A*算法基本上與廣度優先算法相同，但是在擴展

4、出一個結點后，要計算它的估價 函數，并根據估價函數對待擴展的結點排序， 從而保證每次擴展的結點都是估價 函數最小的結點。 A*算法的步驟如下： 1）建立一個隊列，計算初始結點的估價函數f,并將初始結點入隊，設置隊列 頭和尾指針。 2）取出隊列頭（隊列頭指針所指）的結點，如果該結點是目標結點，貝U輸出路 徑，程序結束。否則對結點進行擴展。 3）檢查擴展出的新結點是否與隊列中的結點重復，若與不能再擴展的結點重復 （位于隊列頭指針之前），則將它拋棄；若新結點與待擴展的結點重復（位于隊 列頭指針之后），則比較兩個結點的估價函數中g的大小，保留較小g值的結點。 跳至第五步。 4）如果擴展出的新結點與隊列

5、中的結點不重復，貝U按照它的估價函數 f大小將 它插入隊列中的頭結點后待擴展結點的適當位置， 使它們按從小到大的順序排列， 最后更新隊列尾指針。 5）如果隊列頭的結點還可以擴展，直接返回第二步。否則將隊列頭指針指向下 一結點，再返回第二步。 四、程序框圖 開始 把 S3SAJJ Open中 Cpen裂燉? 取iOpen表申啟發值衆小兩點Cn), A Close A 中 節盧n為冃持結點甘 成功|退出 N 節點n可曠展么? if展節點m格其子節盤1燮從右到左 順序依次枚入Open耒的頭敲. 卄 五、實驗結果及分析 輸入初始狀態：2 8 3 目標狀態：1 2 3 1 6 4 8 0 4 7 0 5

6、 7 6 5 送星UW託拓訓廠丄 const int ROW = 3; const int COL = 3; const int MAXDISTANCE = 10000; const int MAXNUM = 10000; int abs(i nt a) if (a0) retur n a; else return -a; typedef struct _Node int digitROWCOL; int dist; /距離 int dep; / 深度 intin dex; / 索引值 Node; Node src, dest; vector no de_v; / 儲存節點 bool isEm

7、ptyOfOPEN() / 判斷 Open表是否空 for (int i = 0; i no de_v.size(); i+) if (n ode_vi.dist != MAXNUM) return false; return true; bool isEqual(i nt in dex, i nt digitCOL) /判斷節點是否與索引 值指向的節點相同 for (int i = 0; i ROW; i+) for (i nt j = 0; j COL; j+) if (node_vindex.digitij != digitij) return false; return true; o

8、stream i ROW; i+) for (i nt j = 0; j COL; j+) os no de.digitij ; os en dl; return os; void Prin tSteps(i nt in dex, vector in dex = no de_vi ndex.i ndex; while (in dex != 0) rstep_v.push_back (no de_vi ndex); in dex = no de_vi ndex.i ndex; for (int i = rstep_v.size() - 1; i = 0; i-) cout Step rstep_

9、v.size() - i endl rstep_vi en dl; _ void Swap (i nt t = a; a = b; b = t; void Assig n(N ode i ROW; i+) for (i nt j = 0; j COL; j+) no de.digitij = no de_vi ndex.digitij; int GetMi nNode() /獲取啟發值最小的節點 int dist = MAXNUM; in t loc; / the locati on of mini mize node for (int i = 0; i no de_v.size(); i+)

10、 if (n ode_vi.dist = MAXNUM) con ti nue; else if (no de_vi.dist + no de_vi.dep) dist) loc = i; dist = no de_vi.dist + no de_vi.dep; 一 一 return loc; bool isExpa ndable(Node i no de_v.size(); i+) if (isEqual(i, no de.digit) return false; return true; 計算距離 int Distance(Node bool flag = false; for(int i

11、 = 0; i ROW; i+) for (i nt j = 0; j COL; j+) for (int k = 0; k ROW; k+) for (int l = 0; l COL; l+) if (no de.digitij = digitkl) dista nee += abs(i - k) + abs(j - l); flag = true; break; else flag = false; if (flag) break; retur n dista nee; int Mi nDista nce(i nt a, i nt b) /二者取小 return (a b ? a : b

12、); 展開節點 void ProcessNode(i nt in dex) / int x, y; bool flag; for (int i = 0; i ROW; i+) for (int j = 0; j 0) Swap(node_up.digitxy, node_up.digitx - 1y); if (isExpa ndable( no de_up) dist_up = Dista nce( no de_up, dest.digit); no de_up.i ndex = in dex; no de_up.dist = dist_up; no de_up.dep = no de_vi

13、 ndex.dep + 1; no de_v.push_back (no de_up); Node node_down; / 下移操作 Assig n(no de_dow n, in dex); int dist_dow n = MAXDISTANCE; if (x 0) Swap(node_left.digitxy, node_left.digitxy - 1); if (isExpa ndable( no de_left) dist_left = Dista nce( no de_left, dest.digit); no de_left.i ndex = in dex; no de_le

14、ft.dist = dist_left; no de_left.dep = no de_vi ndex.dep + 1; no de_v.push_back (no de_left); 一 Node node_right; /右移操作 Assig n(no de_right, i ndex); int dist_right = MAXDISTANCE; if (y 2) Swap( no de_right.digitxy, no de_right.digitxy + 1); if (isExpa ndable( no de_right) dist_right = Dista nce( no d

15、e_right, dest.digit); no de_right.i ndex = in dex; no de_right.dist = dist_right; no de_right.dep = no de_vi ndex.dep + 1; no de_v.push_back (no de_right); 一一 一 n ode_vi ndex.dist = MAXNUM; _ int mai n() int nu mber; cout 輸入初始狀態: endl; for (int i = 0; i ROW; i+) for (int j = 0; j nu mber; src.digitij = nu mber; src.i ndex = 0; src.dep = 1; cout 輸入目標狀態 endl; for (i nt m = 0; m ROW; m+) for (int n = 0; n nu mber; dest.digitm n = nu mber; no de_v.push_back(src); while (1) if (isEmptyOfOPEN() cout 找不到解! en