1、重慶交通大學計算機與信息學院 驗證性實驗報告班 級：軟件開發專業2013級1班學 號： 631306050121姓 名：吳文靜實驗項目名稱：啟發式搜索實驗項目性質：驗證性實驗實驗所屬課程：人工智能實驗室（中心）:軟件中心實驗室（語音樓8樓）指導教師：朱振國實驗完成時間：2016 年6月12日評閱意見:簽名：年 月曰理解和掌握A*算法。二、實驗內容及要求內容：在8數碼問題中，利用策略函數判斷搜索，并使用A*算法減少搜索目標。要求：用選定的編程語言編寫程序，利用不同的搜索策略進行狀態空間搜索(如寬度優先搜索、 深度優先搜索、有界深度優先搜索等)。三、實驗設備及軟件PC機一臺VC6.0編程語言或其它

2、編程語言四、設計方案題目啟發式搜索設計的主要思路八數碼問題的求解算法(1) 盲目搜索寬度優先搜索算法、深度優先搜索算法(2)啟發式搜索啟發式搜索算法的基本思想是：定義一個評價函數f,對當前的搜索狀態進行評估，找 出一個最有希望的節點來擴展。先定義下面幾個函數的含義：f*(n)=g*(n)+h*(n)(1)式中g*(n)表示從初始節點s到當前節點n的最短路徑的耗散值;h*(n)表示從當前節點 n到目標節點g的最短路徑的耗散值，f*(n)表示從初始節點s經過n到目標節點g的最短路徑的耗散值。評價函數的形式可定義如(2)式所示:f(n)=g(n)+h(n)(2)其中n是被評價的當前節點f(n)、g(

3、n)和h(n)分別表示是對f*(n)、g*(n)和h*(n)3個函數值的估計值。利用評價函數f(n)=g(n)+h(n)來排列OPEN表節點順序的圖搜索算法稱為算法A。在A算法中， 如果對所有的x，h(x)=h*(x)(3)成立，則稱好h(x)為h*(x)的下界，它表示某種偏于保守的估計。采用h*(x)的下界h(x)為啟發函數的A算法，稱為A*算法 針對八數碼問題啟發函數設計如 下：F(n)=d(n)+p(n)(4)其中A*算法中的g(n)根據具體情況設計為d(n)，意為n節點的深度，而h(n)設計為p(n)，意 為放錯的數碼與正確的位置距離之和。由于實際情況中，一個將牌的移動都是單步進行的，

4、沒有交換拍等這樣的操作。所以要把所有 的不在位的將牌，移動到各自的目標位置上，至少要移動從他們各自的位置到目標位置的距離和這 么多次，所以最有路徑的耗散值不會比該值小，因此該啟發函數h(n)滿足A*算法的條件。主要功能在一個3*3的方棋盤上放置著1,2,3,4,5,6,7,8八個數碼，每個數碼占一格,且有一個空格。這些數 碼可以在棋盤上移動，其移動規則是：與空格相鄰的數碼方格可以移入空格。現在的問題是：對于 指定的初始棋局和目標棋局，給出數碼的移動序列。該問題稱八數碼難題或者重排九宮問題。五、主要代碼#include#include#include/八數碼狀態對應的節點結構體struct No

5、de(int s33;/保存八數碼狀態，0代表空格int f,g;/啟發函數中的f和g值struct Node * next;struct Node *previous;/保 存其父節點;int open_N=0; 記錄Open列表中節點數目/八數碼初始狀態int inital_s33= 2,8,3, 1,6,4, 7,0,5 ;/八數碼目標狀態int final_s33= 1,2,3, 8,0,4, 7,6,5 ;/添加節點函數入口，方法：通過插入排序向指定表添加/void Add_Node( struct Node *head, struct Node *p)struct Node *q;

6、if(head-next)/考 慮鏈表為空 q = head-next; if(p-f next-f)/考慮插入的節點值比鏈表的第一個節點值小p-next = head-next; head-next = p;else while(q-next)/考慮插入節點 x，形如 a= x f f |q-f = p-f) & (q-next-f p-f | q-next-f = p-f) p-next = q-next; q-next = p; break;q = q-next;if(q-next = NULL) /考慮插入的節點值比鏈表最后一個元素的值更大 q-next = p;else head-n

7、ext = p;/刪除節點函數入口/void del_Node(struct Node * head, struct Node *p ) struct Node *q; q = head;while(q-next) if(q-next = p) q-next = p-next; p-next = NULL; if(q-next = NULL) return;/ free(p); q = q-next; /判斷兩個數組是否相等函數入口/int equal(int s133, int s233) (int i,j,flag=0;for(i=0; i 3 i+) for(j=0; jnext; in

8、t flag = 0; while(q) if(equal(q-s,s)( flag=1; Old_Node-next = q; return 1; else q = q-next; if(!flag) return 0; /計算 p(n)的函數入口其中p(n)為放錯位的數碼與其正確的位置之間距離之和/具體方法：放錯位的數碼與其正確的位置對應下標差的絕對值之 和 /int wrong_sum(int s33) (int i,j,fi,fj,sum=0; /通過頭插法變更節點輸出次序 p-previous = NULL; q = head; while(q) (q1 = q-previous;q

9、-previous = p-previous; p-previous = q; q = q1; q = p-previous;while(q) (if(q = p-previous)printf(八數碼的初始狀態：n);else if(q-previous = NULL)printf(八數碼的 目 標狀態：n); else printf(八數碼的中間 態 dn”,count+); for(i=0; i3; i+) for(j=0; jsij); if(j = 2)printf(n); printf(f=%d, g=%dnn”,q-f,q-g); q = q-previous; /A*子算法入口

10、:處理后繼結點/void sub_A_algorithm(struct Node * Open, struct Node * BESTNODE, struct Node * Closed,struct Node * Successor) ( struct Node * Old_Node = (struct Node *)malloc(sizeof(struct Node);Successor-previous = BESTNODE;/ 建立從 successor 返回 BESTNODE 的指 針 Successor-g = BESTNODE-g + 1;/計算后繼結點的 g 值檢查后繼結點是否

11、已存在于Open和Closed表中，如果存在：該節點記為old_Node,比較后繼結點的g值和表中old_Node節點/g值，前者小代表新的路徑比老路徑更好，將Old_Node的父節點改為BESTNODE，并修改其f，g 值，后者小則什么也不做。/即不存在Open也不存在Closed表則將其加入OPen表，并計算其f 值 if( exit_Node(Open, Successor-s, Old_Node) )( if(Successor-g g) Old_Node- next-previous = BESTNODE;/ 將 Old_Node 的 父 節 點 改 為 BESTNODE Old_N

12、ode-next-g = Successor-g;/修改g值 Old_Node-next-f = Old_Node-g + wrong_sum(Old_Node-s);/ 修改 f 值 / 排 序 del_Node(Open, Old_Node); Add_Node(Open, Old_Node); else if( exit_Node(Closed, Successor-s, Old_Node) if(Successor-g g) Old_Node-nex t-previous = BESTNODE; Old_Node-next-g = Successor-g; Old_Node-next-

13、f = Old_Node-g + wrong_sum(Old_Node-s); /排序 del_Node(Closed, Old_Node); Add_Node(Closed, Old_Node); els e Successor-f = Successor-g + wrong_sum(Successor-s); Add_Node(Open, Successor); op en_N+; /A*算法入口/八數碼問題的啟發函數為：f(n)=d(n)+p(n)其中A*算法中的g(n)根據具體情況設計為d(n)，意為n節點的深度，而h(n)設計為p(n)，意為放 錯的數碼與正確的位置距離之和/void

14、 A_algorithm(struct Node * Open, struct Node * Closed) /A*算法int i,j;struct Node * BESTNODE, *inital, * Successor;inital = (struct Node * )malloc(sizeof(struct Node);/初始化起始節點for(i=0; i3; i+)for(j=0; jsij = inital_sij;inital-f = wrong_sum(inital_s);inital-g = 0;inital-previous = NULL;inital-next = NUL

15、L;Add_Node(Open, inital);/把初始節點放入 OPEN 表 open_N+; while(1)( if(open_N = 0)(printf(failure!); return;else (BESTNODE = get_BESTNODE(Open);/從 OPEN 表獲取 f 值最小的 BESTNODE,將其從 OPEN 表 刪除并加入CLOSED表中del_Node(Open, BESTNODE);open_N-;Add_Node(Closed, BESTNODE);if(equal(BESTNODE-s, final_s)/判斷BESTNODE是否為目標節點print

16、f(success!n);print_Path(BESTNODE);return;針對八數碼問題，后繼結點Successor的擴展方法：空格(二維數組中的0)上下左右移動，/ 判斷每種移動的有效性，有效則轉向A*子算法處理后繼節點，否則進行下一種移動elseSuccessor = (struct Node * )malloc(sizeof(struct Node); Successor-next = NULL;if(get_successor(BESTNODE, 0, Successor)sub_A_algorithm( Open, BESTNODE, Closed, Successor);S

17、uccessor = (struct Node * )malloc(sizeof(struct Node);Successor-next = NULL;if(get_successor(BESTNODE, 1, Successor) sub_A_algorithm( Open, BESTNODE,Closed, Successor);Successor = (struct Node * )malloc(sizeof(struct Node);Successor-next = NULL;if(get_successor(BESTNODE, 2, Successor)sub_A_algorithm

18、( Open, BESTNODE, Closed, Successor);Successor = (struct Node * )malloc(sizeof(struct Node);Successor-next = NULL;if(get_successor(BESTNODE, 3, Successor)sub_A_algorithm( Open, BESTNODE, Closed, Successor); /main ()函數入口定義Open和Closed列表。Open列表：保存待檢查節點。Closed列表：保存不需要再檢查的節點/void main() (struct Node * Op

19、en = (struct Node * )malloc(sizeof(struct Node);struct Node * Closed = (struct Node * )malloc(sizeof(struct Node);Open-next = NULL Open-previous = NULL;Closed-next =NULL; Closed-previous = NULL;A_algorithm(Open, Closed);六、測試結果及說明2*3 TOC o 1-5 h z 八散醐I申閭參 2fl31H47fcf 6*g2凡散醐)尊間應1 1Z?。且 4 765F 甘域七、實驗體

20、會。通過本次的試驗，我對啟發式搜索算法有了更加深入地了解。在實驗中，通過對兩種啟發式搜 索所擴在的節點數來看，p(n)看來比w(n)更加有成效，能在復雜的情況下求得更加優質的解，避免 不必要的節點的擴展。但是對于估價函數h*(n)來說，他的定義趨于多元化，p(n)只是他的一個比較 好的特例，對于一些復雜的搜索問題，如國際象棋問題，他就顯得特別的簡單。所以要更好的定義 一個估價函數還有待討論。在進行實驗探究時，我還遇到一些問題，在低階數碼問題中，使用簡單的寬搜或深搜便可以解 決。但是在實驗過程中，仍遇到很多的問題，這讓我意識到自己對該算法的認識還不夠充足，還要 更加的努力。重慶交通大學計算機與信

21、息學院 驗證性實驗報告班 級：軟件開發專業2013級1班學 號： 631306050121姓 名：吳文靜實驗項目名稱：狀態空間搜索實驗項目性質：驗證性實驗實驗所屬課程：人工智能實驗室（中心）:軟件中心實驗室（語音樓8樓）指導教師：朱振國實驗完成時間：2016 年6月12日評閱意見:實驗成績：簽名：年 月曰一、實驗目的熟悉人工智能系統中的問題求解過程；熟悉狀態空間的盲目搜索和啟發式搜索算法的應用；熟悉對八數碼問題的建模、求解及編程語言的應用。二、實驗內容及要求內容：在一個3*3的九宮中有1-8個數碼及一個空格隨即的擺放在其中的格子里，現在要求 實驗這個問題:將該九宮格調整為某種有序的形式。調整的

22、規則是，每次只能將與空格（上、 下、左、右）相鄰的一個數字平移到空格中。要求：用選定的編程語言編寫程序，利用不同的搜索策略進行狀態空間搜索（如寬度優先搜 索、深度優先搜索、有界深度優先搜索等）。三、實驗設備及軟件PC機一臺VC6.0編程語言或其它編程語言四、設計方案題目八數碼問題求解設計的主要思路1、基本數據結構分析和實現a.結點狀態我采用了 struct Node數據類型typedef struct _Node int digitROWCOL;int dist; / distance between one state and the destination 一個表和目的表的距離int de

23、p; / the depth of node 深度/ So the comment function = dist + dep,估價函數值int index; / point to the location of parent 父節點的位置 Node;b.發生器函數定義的發生器函數由以下的四種操作組成：將當前狀態的空格上移Node node_up;Assign(node_up, index);/ 向上擴展的節點int dist_up = MAXDISTANCE;將當前狀態的空格下移Node node_down;Assign(node_down, index);/向 下擴展的節點int dist

24、_down = MAXDISTANCE;將當前狀態的空格左移Node node_left;Assign(node_left, index);/向 左擴展的節點int dist_left = MAXDISTANCE;將當前狀態的空格右移Node node_right;Assign(node_right, index);/ 向右擴展的節點int dist_right = MAXDISTANCE;通過定義結點狀態和發生器函數，就解決了8數碼問題的隱式圖的生成問題。接下來就是 搜索了。2、圖的搜索策略經過分析，8數碼問題中可采用的搜速策略共有：1.廣度優先搜索、2.深度優先搜索、2.有界深度優先搜索、

25、4.最好優先搜索、5.局部擇優搜索，一共五種。其中，廣度優先搜索 法是可采納的，有界深度優先搜索法是不完備的，最好優先和局部擇優搜索法是啟發式搜索 法。實驗時，采用了廣度(寬度)優先搜索來實現。主要功能對空格執行空格左移、空格右移、空格上移和空格下移這四個操作使得從初始狀態到目標狀態。五、主要代碼#include #include #include using namespace std;const int ROW = 3;/彳亍數const int COL = 3;/列數const int MAXDISTANCE = 10000;/最 多可以有的表的數目const int MAXNUM =

26、10000;typedef struct _Node int digitROWCOL;int dist; / distance between one state and the destination 一個表和目的表的距離int dep; / the depth of node 深度/ So the comment function = dist + dep,估 價函數值int index; / point to the location of parent 父節點的位置 Node;Node src, dest;/父節表 目的表vector node_v; / store the nodes

27、 存儲節點bool isEmptyOfOPEN() /open 表是否為空for (int i = 0; i node_v.size(); i+) if (node_vi.dist != MAXNUM) return false; return true; bool isEqual(int index, int digitCOL) /判斷這個最優的節點是否和目的節點一樣for (int i = 0; i ROW; i+) for (int j = 0; j COL; j+) if (node_vindex.digitij != digitij) return false; return tru

28、e; ostream& operator(ostream& os, Node& node) for (int i = 0; i ROW; i+)for (int j = 0; j COL; j+)os node.digitij ;os endl;return os;void PrintSteps(int index, vector& rstep_v)/輸出每一個遍歷的節點深度遍歷rstep_v.push_back(node_vindex);index = node_vindex.index;while (index != 0)rstep_v.push_back(node_vindex);ind

29、ex = 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; void Assign(Node& node, int index)for (int i = 0; i ROW; i+) for (int j = 0; j COL; j+) node.digitij = node_vindex.digi

30、tij;int GetMinNode() /找到最小的節點的位置即最優節點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) dist) loc = i;dist = node_vi.dist + node_vi.dep;return loc; bool isExpandable(Node& node) for (i

31、nt 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 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 += a

32、bs(i - k) + abs(j - l);flag = true; break;elseflag = false;if (flag) break;return distance;int MinDistance(int a, int b)return (a b ? a : b);void ProcessNode(int index)int x, y; bool flag;for (int i = 0; i 0) Swap(node_left.digitxy, node_left.digitxy - 1);if (isExpandable(node_left)dist_left = Dista

33、nce(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);/向 右擴展的節點int dist_right = MAXDISTANCE; if (y 2)Swap(node_right.digitxy, node_right.digitxy + 1);if (isExpandable(n

34、ode_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 Input source: endl;for (int i = 0; i ROW; i+)/輸入初始的表for (int j = 0; j number;src.digitij = number; src.