八數(shù)碼問題C語言A星算法詳細實驗報告材料含代碼

1、、實驗容和要求八數(shù)碼問題：在3X 3的方格棋盤上，擺放著1到8這八個數(shù)碼，有1個方格是 空的，其初始狀態(tài)如圖1所示，要求對空格執(zhí)行空格左移、空格右移、空格上移 和空格下移這四個操作使得棋盤從初始狀態(tài)到目標狀態(tài)。例如：28312316484705765(a)初始狀態(tài)(b)目標狀態(tài)圖1八數(shù)碼問題示意圖請任選一種盲目搜索算法(廣度優(yōu)先搜索或深度優(yōu)先搜索) 或任選一種啟發(fā) 式搜索方法(全局擇優(yōu)搜索，加權(quán)狀態(tài)圖搜索，A算法或A*算法)編程求解八數(shù)碼問題(初始狀態(tài)任選)。選擇一個初始狀態(tài)，畫出搜索樹，填寫相應的OPEN 表和CLOSE表，給出解路徑，對實驗結(jié)果進行分析總結(jié)，得出結(jié)論。二、實驗目的1. 熟悉

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

3、) 是從初始結(jié)點到節(jié)點 n 的實際代價， h(n) 是從結(jié)點 n 到目標結(jié)點的最 佳路徑的估計代價。在這里主要是 h(n) 體現(xiàn)了搜索的啟發(fā)信息，因為 g(n) 是已 知的。用 f(n) 作為 f'(n) 的近似，也就是用 g(n) 代替 g'(n) ， h(n) 代替 h'(n) 。 這樣必須滿足兩個條件： (1)g(n)>=g'(n) (大多數(shù)情況下都是滿足的，可以不 用考慮)，且 f 必須保持單調(diào)遞增。( 2) h 必須小于等于實際的從當前節(jié)點到達 目標節(jié)點的最小耗費 h(n)<=h'(n) 。第二點特別的重要?？梢宰C明應用這樣的估 價

4、函數(shù)是可以找到最短路徑的。3.A* 算法的步驟A*算法基本上與廣度優(yōu)先算法相同，但是在擴展出一個結(jié)點后，要計算它的估價 函數(shù)，并根據(jù)估價函數(shù)對待擴展的結(jié)點排序， 從而保證每次擴展的結(jié)點都是估價 函數(shù)最小的結(jié)點。A*算法的步驟如下：1) 建立一個隊列，計算初始結(jié)點的估價函數(shù)f ，并將初始結(jié)點入隊，設置隊列 頭和尾指針。2) 取出隊列頭(隊列頭指針所指)的結(jié)點，如果該結(jié)點是目標結(jié)點，則輸出路 徑，程序結(jié)束。否則對結(jié)點進行擴展。3) 檢查擴展出的新結(jié)點是否與隊列中的結(jié)點重復，若與不能再擴展的結(jié)點重復 (位于隊列頭指針之前) ，則將它拋棄；若新結(jié)點與待擴展的結(jié)點重復(位于隊列頭指針之后)，則比較兩個結(jié)

5、點的估價函數(shù)中g(shù)的大小，保留較小g值的結(jié)點。 跳至第五步。4) 如果擴展出的新結(jié)點與隊列中的結(jié)點不重復，則按照它的估價函數(shù)f 大小將 它插入隊列中的頭結(jié)點后待擴展結(jié)點的適當位置，使它們按從小到大的順序排 列，最后更新隊列尾指針。5) 如果隊列頭的結(jié)點還可以擴展，直接返回第二步。否則將隊列頭指針指向下 一結(jié)點，再返回第二步。四、程序框圖五、實驗結(jié)果及分析輸入初始狀態(tài)：2 8 3目標狀態(tài)：1 2 3運行結(jié)果屏幕打印0 1 5 7 6 9 11 2OPEN 表與 CLOSE 表:OPENCLOSE1 2 3 402 3 4 5 60 12 3 4 6 70 1 52 3 4 6 8 90 1 5 7

6、2 3 4 8 9 100 1 5 7 62 3 4 8 11 12 130 1 5 7 6 92 3 4 8 12 13 14 150 1 5 7 6 9 113 4 8 12 13 14 15 16 174 8 12 13 14 15 16 17 19 208 12 13 14 15 16 17 19 21 2212 13 14 15 16 17 19 21 22 2312 13 14 15 16 17 19 21 22 24 2512 13 14 15 16 17 19 21 22 24 26發(fā)現(xiàn)26為目標節(jié)點0 1 5 7 6 9 11 2 3 180 1 5 7 6 9 11 2 3

7、 18 40 1 5 7 6 9 11 2 3 18 4 80 1 5 7 6 9 11 2 3 18 4 8 230 1 5 7 6 9 11 2 3 18 4 8 23 24搜索樹:24.8注釋：每個方格中最上面兩個數(shù)字 分別為編號與啟發(fā)值，下面 九個數(shù)字為八數(shù)碼。較粗的目標節(jié)點14.120 1 382-4-15.143 1 08-2-4-六、結(jié)論對于八數(shù)碼問題，BFS算法最慢，A*算法較快。八數(shù)碼問題的一個狀態(tài)實際 上是09的一個排列，對于任意給定的初始狀態(tài)和目標，不一定有解，也就是說 從初始狀態(tài)不一定能到達目標狀態(tài)。 因為排列有奇排列和偶排列兩類，從奇排列 不能轉(zhuǎn)化成偶排列。如果一個數(shù)

8、字08的隨機排列871526340,用F(X)表示數(shù)字 X前面比它小的數(shù)的個數(shù)，全部數(shù)字的F(X)之和為Y=E (F(X)，如果丫為奇數(shù)則稱原數(shù)字的排列是奇排列，如果 丫為偶數(shù)則稱原數(shù)字的排列是偶排列。因此， 可以在運行程序前檢查初始狀態(tài)和目標狀態(tài)的排序的奇偶行是否相同，相同則問題可解，應當能搜索到路徑。否則無解。七、源程序及注釋#in elude <iostream>#in elude <ctime>#in elude <veetor>using n amespace std;const int ROW = 3;const int COL = 3;cons

9、t int MAXDISTANCE = 10000;const int MAXNUM = 10000;int abs(int a)if (a>0) return a;else return -a;typedef struct _Nodeint digitROWCOL;int dist; /距離int dep; /深度int index; /索引值 Node;Node src, dest;vector<Node> node_v; / 儲存節(jié)點bool isEmptyOfOPEN() / 判斷 Open表是否空 for (int i = 0; i < node_v.size

10、(); i+) if (node_vi.dist != MAXNUM)return false;return true;bool isEqual(int index, int digitCOL) / 值指向的節(jié)點相同for (int i = 0; i < ROW; i+)for (int j = 0; j < COL; j+) if (node_vindex.digitij != digitij)return false;return true;ostream& operator<<(ostream& os, Node& node) for (i

11、nt i = 0; i < ROW; i+) for (int j = 0; j < COL; j+)os << node.digitij << ' 'os << endl;return os;void PrintSteps(int index, vector<Node>& rstep_v) / rstep_v.push_back(node_vindex);index = node_vindex.index;判斷節(jié)點是否與索引輸出步驟while (index != 0) rstep_v.push_back(no

12、de_vindex);index = node_vindex.index;for (int i = rstep_v.size() - 1; i >= 0; i-) cout << "Step " << rstep_v.size() - i << endl << rstep_vi << endl;交換void Swap(int& a, int& b) / int t;t = a;a = b;b = t;獲取節(jié)點void Assign(Node& node, int index) / fo

13、r (int i = 0; i < ROW; i+)for (int j = 0; j < COL; j+)node.digitij = node_vindex.digitij;int GetMinNode() / 獲取啟發(fā)值最小的節(jié)點 int dist = MAXNUM;int loc; / the location of minimize nodefor (int i = 0; i < node_v.size(); i+) if (node_vi.dist = MAXNUM)continue;else if (node_vi.dist + node_vi.dep) <

14、; dist) loc = i;dist = node_vi.dist + node_vi.dep;return loc;bool isExpandable(Node& node) / 判斷是否可擴展 for (int i = 0; i < node_v.size(); i+) if (isEqual(i, node.digit)return false;return true;計算距離int Distance(Node& node, int digitCOL) /int distance = 0;bool flag = false;for(int i = 0; i &l

15、t; ROW; i+)for (int j = 0; j < COL; j+)for (int k = 0; k < ROW; k+) for (int l = 0; l < COL; l+) if (node.digitij = digitkl) distance += abs(i - k) + abs(j - l); flag = true;break;elseflag = false;if (flag)break;return distance;二者取小展開節(jié)點int MinDistance(int a, int b) / return (a < b ? a :

16、b);void ProcessNode(int index) / int x, y;bool flag;for (int i = 0; i < ROW; i+) for (int j = 0; j < COL; j+) if (node_vindex.digitij = 0) x =i; y = j;flag = true;break;else flag = false;if(flag)break;Node node_up; / 上移操作Assign(node_up, index);int dist_up = MAXDISTANCE;if (x > 0) Swap(node_

17、up.digitxy, node_up.digitx - 1y); if (isExpandable(node_up) dist_up = Distance(node_up, dest.digit);node_up.index = index;node_up.dist = dist_up;node_up.dep = node_vindex.dep + 1;node_v.push_back(node_up);Node node_down; / 下移操作Assign(node_down, index);int dist_down = MAXDISTANCE;if (x < 2) Swap(n

18、ode_down.digitxy, node_down.digitx + 1y); if (isExpandable(node_down) dist_down = Distance(node_down, dest.digit); node_down.index = index;node_down.dist = dist_down;node_down.dep = node_vindex.dep + 1; node_v.push_back(node_down);Node node_left;/ 左移操作Assign(node_left, index);int dist_left = MAXDIST

19、ANCE;if (y > 0) Swap(node_left.digitxy, node_left.digitxy - 1);if (isExpandable(node_left) dist_left = Distance(node_left, dest.digit);node_left.index = index;node_left.dist = dist_left;node_left.dep = node_vindex.dep + 1;node_v.push_back(node_left);Node node_right; / 右移操作Assign(node_right, index

20、);int dist_right = MAXDISTANCE;if (y < 2) Swap(node_right.digitxy, node_right.digitxy + 1); if (isExpandable(node_right) dist_right = Distance(node_right, dest.digit); node_right.index = index;node_right.dist = dist_right;node_right.dep = node_vindex.dep + 1;node_v.push_back(node_right);node_vindex.dist = MAXNUM;int main() int number;cout << " 輸入初始狀態(tài) :" << endl;for (int i = 0; i < ROW