采用A算法解決八數(shù)碼問題

1、人工智能實驗一報告題目：采用 A*算法解決八數(shù)碼問題姓名：張博涵學號：081110317專業(yè)：信息與計算科學提交日期：2014-05-22.專業(yè)整理 .目錄1 問題描述 - 2 -1.1 待解決問題的解釋 - 2 -1.2 問題的搜索形式描述 - 2 -1.3 解決方案介紹（原理） - 3 -2 算法介紹 - 4 -2.1A* 搜索算法一般介紹 . - 4 -2.2 算法偽代碼 . - 4 -3 算法實現(xiàn) - 5 -3.1 實驗環(huán)境與問題規(guī)模 . - 5 -3.2 數(shù)據(jù)結構 . - 5 -3.3 實驗結果 . - 5 -3.4 系統(tǒng)中間及最終輸出結果 - 7 -4 參考文獻 - 8 -5 附錄

2、源代碼及其注釋 - 8 -. 學習幫手 .專業(yè)整理 .1 問題描述所謂八數(shù)碼問題是指這樣一種游戲：將分別標有數(shù)字 1，2，3， 8 的八 塊正方形數(shù)碼牌任意地放在一塊 33 的數(shù)碼盤上。 放牌時要求不能重疊。 于是， 在 3 3 的數(shù)碼盤上出現(xiàn)了一個空格。現(xiàn)在要求按照每次只能將與空格相鄰的數(shù) 碼牌與空格交換的原則， 不斷移動該空格方塊以使其和相鄰的方塊互換， 直至達 到所定義的目標狀態(tài)。空格方塊在中間位置時有上、下、左、右 4個方向可移動， 在四個角落上有 2個方向可移動， 在其他位置上有 3個方向可移動， 問題描述如下 圖1-1所示：1.1 待解決問題的解釋首先，八數(shù)碼問題包括一個初始狀態(tài)

3、(START) 和目標狀態(tài) (END)，所謂解決 八數(shù)碼問題就是在兩個狀態(tài)間尋找一系列可過渡狀態(tài)： (STARTSTATE1STATE2.E)ND 這個狀態(tài)是否存在就是我們要解決的第一個問題： Q1：每一個狀態(tài)及每一次操作 的表示方法？有許多表示方法， 比如一個 3*3 的八數(shù)碼盤可以壓縮成一個 int 值 表示，但不適用于 15 puzzle 或大于 8 的puzzle 問題。如果對空間要求很高，應 該還可以再壓縮。 本文采用一個 int 表示的方法。 表示方法如下： 由于 int 的表 示范圍大于 1e9，所以我們取一個 int 的低 9 位，為了方便尋找空格的位置， int 的個位我們用

4、來放空格的位置( 19)。而前 8 位，按照行從上到下，列從左到右 的順序依次記錄對應位置上的數(shù)字。1.2 問題的搜索形式描述八數(shù)碼問題形式化描述：初始狀態(tài)：初始狀態(tài)向量：規(guī)定向量中各分量對應的位置，各位置上的數(shù)字。把 33 的棋盤按從左到右，從上到下的順序寫成一個一維向量。 我們可以設定初始狀態(tài)： . 學習幫手 .專業(yè)整理 .后繼函數(shù)： 按照某種規(guī)則移動數(shù)字得到的新向量。例如： 目標測試： 新向量是都是目標狀態(tài)。即 是目標狀態(tài)？ 路徑耗散函數(shù)：每次移動代價為 1，每執(zhí)行一條規(guī)則后總代價加 1。1.3 解決方案介紹(原理)該問題是一個搜索問題。 它是一種狀態(tài)到另一種狀態(tài)的變換。 要解決這個問

5、題，必須先把問題轉化為數(shù)字描述。 由于八數(shù)碼是一個 3*3 的矩陣， 但在算法中 不實用矩陣， 而是將這個矩陣轉化為一個一維數(shù)組， 使用這個一維數(shù)組來表示八 數(shù)碼，但是移動時要遵守相關規(guī)則。(1) 可用如下形式的規(guī)則來表示數(shù)字通過空格進行移動： (2) 共 24 條移動規(guī)則，對應與每個位置的移動規(guī)則。(3) 搜索順序舉例： 優(yōu)先移動行數(shù)小的棋子 (數(shù)字 ) 同一行中優(yōu)先移動列數(shù)大的棋子(4) 約束規(guī)則：不使離開既定位置的數(shù)字數(shù)增加 八數(shù)碼的節(jié)點擴展應當遵循棋子的移動規(guī)則。 按規(guī)則，每一次可以將一個與 空格相鄰的棋子移動到空格中， 實際上也可以看做空格的相反方向移動。 空格的 移動方向可以是上下

6、左右， 當然不能出邊界。 棋子的位置， 也就是保存狀態(tài)的數(shù) 組元素的下標，空格移動后，相應位置發(fā)生變化，在不移出邊界的條件下，空格 向右，下，左，上移動后，新位置是原位置分別加上 1,3 ，-1，-3。在這里，空 格可以用任意數(shù)字表示。操作本文用 u r d l 分別表示空格的向上向右向下向 左四個操作。圖的搜索策略：經分析， 8 數(shù)碼問題的搜索策略共有： 1.廣度優(yōu)先搜索、 2. 深度優(yōu)先搜索、 3. 有界深度優(yōu)先搜索、 4. 最好優(yōu)先搜索、 5. 局部擇優(yōu)搜索， 等等。 其中廣度優(yōu)先搜索法是可采納的， 有界深度優(yōu)先搜索法是不完備的， 最好優(yōu)先和 局部擇優(yōu)搜索法是啟發(fā)式搜索法。本實驗采用啟發(fā)

7、式 A*搜索算法來實現(xiàn)。. 學習幫手 .專業(yè)整理 .2 算法介紹問題的求解實際上就是在這個圖中找到一條路徑可以從開始到結果。 這個尋 找的過程就是狀態(tài)空間搜索。 常用的狀態(tài)空間搜索有深度優(yōu)先和廣度優(yōu)先。 廣度 優(yōu)先是從初始狀態(tài)一層一層向下找， 直到找到目標為止。 深度優(yōu)先是按照一定的 順序前查找完一個分支，再查找另一個分支，以至找到目標為止。啟發(fā)式搜索就是在狀態(tài)空間中的搜索對每一個搜索的位置進行評估， 得到最 好的位置，再從這個位置進行搜索直到目標。 這樣可以省略大量無畏的搜索路徑， 提高了效率。2.1A* 搜索算法一般介紹A* 算法實際是一種啟發(fā)式搜索，所謂啟發(fā)式搜索，就是利用一個估價函數(shù)

8、評估每次的的決策的價值， 決定先嘗試哪一種方案， 這樣可以極大的優(yōu)化普通的 廣度優(yōu)先搜索。 一般來說， 從出發(fā)點 (A) 到目的地(B) 的最短距離是固定的， 我們 可以寫一個函數(shù) judge() 估計 A 到 B 的最短距離，如果程序已經嘗試著從出 發(fā)點 A 沿著某條路線移動到了 C 點, 那么我們認為這個方案的 A B 間的估計 距離為 A 到 C 實際已經行走了的距離 H 加上用 judge() 估計出的 C 到 B 的距離。如此，無論我們的程序搜索展開到哪一步， 都會算出一個評估值， 每一次決 策后，將評估值和等待處理的方案一起排序， 然后挑出待處理的各個方案中最有 可能是最短路線的一

9、部分的方案展開到下一步，一直循環(huán)到對象移動到目的地， 或所有方案都嘗試過卻沒有找到一條通向目的地的路徑則結束。 A*算法是一個可采納的最好優(yōu)先算法。 A*算法的估價函數(shù)可表示為：f(n) = g(n) + h(n) 這里， f(n) 是估價函數(shù)， g(n) 是起點到終點的最短路徑值， h(n) 是 n到目標 的最斷路經的啟發(fā)值。由于這個 f(n) 其實是無法預先知道的，所以我們用前面 的估價函數(shù) f(n) 做近似。 g(n) 代替 g(n) ，但 g(n)=g(n) 才可(大多數(shù)情況下 都是滿足的，可以不用考慮) ，h(n) 代替 h(n) ，但 h(n)=h(n) 才可?？梢宰C明 應用這樣的

10、估價函數(shù)是可以找到最短路徑的，也就是可采納的。2.2 算法偽代碼首先定義兩個表， open 表用于存放已經生成，且已用啟發(fā)式函數(shù)進行過估計或評價，但尚未產生它們的后繼節(jié)點的那些結點，這些結點也稱未考察結點；. 學習幫手 .專業(yè)整理 .closed 表用于存放已經生成， 且已考察過的結點。 設 S0 為初態(tài)，Sg 為目標狀態(tài)。 具體過程如下：(1) 把 S0放入 open 表，記為 f=h，令 closed 為空表；(2) 重復下列過程，直至找到目標結點為止。若 open 為空表，則失敗；(3) 選取 open 表中未設置過的具有最小 f 值的結點為最佳節(jié)點，并放入 closed 表中(4) 若

11、最佳節(jié)點不是目標節(jié)點，則擴展之，產生后繼節(jié)點。(5) 對每個后繼結點進行下列過程：? 建立從該后繼結點返回最佳節(jié)點的指針；? 計算 g(后繼結點) =g(最佳節(jié)點) +k(最佳節(jié)點，后繼結點) ；? Ss：如果該后繼節(jié)點 open，則稱此節(jié)點為 old ，并把它添加至最佳節(jié) 點的后繼節(jié)點中? 比較新舊路徑代價，如果個 g(后繼節(jié)點) g(old), 則重新確定 old 的 父親節(jié)點? 若至 old 節(jié)點的代價比較低或一樣，則停止擴展節(jié)點? 若后繼節(jié)點不再 open 表中，則看其是否在 closed 中? 若后繼節(jié)點在 open 表中，則轉向 Ss；? 若后繼節(jié)點既不在 open 表中，又不在

12、closed 表中，則把它放入 open 表中，并填入最佳節(jié)點的后裔表，然后走下一步(6) 計算 f 值(7) GO LOOP3 算法實現(xiàn)3.1 實驗環(huán)境與問題規(guī)模(1) 實驗環(huán)境： Windows XP(2) 實驗編程工具： VC+6.03.2 數(shù)據(jù)結構1) 定義狀態(tài)圖中的結點數(shù)據(jù)結構typedef struct Nodestatus data;/ 結點所存儲的狀態(tài). 學習幫手 .專業(yè)整理 .struct Node *parent;/指向結點的父親結點struct SpringLink *child;/ 指向結點的后繼結點struct Node *next;/指向 open 或者 close

13、d 表中的后一個結點int fvalue;/結點的總的路徑int gvalue;/結點的實際路徑int hvalue;/結點的到達目標的苦難程度NNode , *PNode;2）定義存儲指向結點后繼結點的指針的地址typedef struct SpringLinkstruct Node *pointData;/指向結點的指針struct SpringLink *next;/指向兄第結點SPLink , *PSPLink;3) 初始化一個空鏈表void initLink(PNode &Head)3.3 實驗結果經測試，程序運行良好，結果正確。輸入測試數(shù)據(jù)，初試狀態(tài) ，目標狀態(tài) ，運行結果有解，共

14、經過四步。. 學習幫手 .專業(yè)整理 .3.4 系統(tǒng)中間及最終輸出結果圖 3-1 程序運行中間結果. 學習幫手 .專業(yè)整理 .圖 3-2 程序運行最終結果4 參考文獻一種現(xiàn)代方1 Artificial intelligence :;a modern approach人工智能法 作者： Russell, Stuart J.出版社：清華大學出版社2 CSDN博客5 附錄源代碼及其注釋#include iostream#include stdlib.h#include conio.h#define size 3using namespace std;/ 定義二維數(shù)組來存儲數(shù)據(jù)表示某一個特定狀態(tài)type

15、def int statussizesize;struct SpringLink;/ 定義狀態(tài)圖中的結點數(shù)據(jù)結構typedef struct Nodestatus data;/結點所存儲的狀態(tài)struct Node *parent;/ 指向結點的父親結點struct SpringLink *child;/ 指向結點的后繼結點struct Node *next;/指向 open 或者 closed 表中的后一個結點int fvalue;/結點的總的路徑int gvalue;/結點的實際路徑int hvalue;/結點的到達目標的苦難程度NNode , *PNode;/ 定義存儲指向結點后繼結點的

16、指針的地址 typedef struct SpringLinkstruct Node *pointData;/指向結點的指針. 學習幫手 .專業(yè)整理 .指向兄第結點struct SpringLink *next;/ SPLink , *PSPLink;PNode open;PNode closed;/ 開始狀態(tài)與目標狀態(tài) status startt = 0,1,2,3,4,5,6,7,8; status target = 1,4,2,3,5,8,6,7,0;/ 初始化一個空鏈表void initLink(PNode &Head)Head = (PNode)malloc(sizeof(NNode

17、);Head-next = NULL;/ 判斷鏈表是否為空 bool isEmpty(PNode Head) if(Head-next = NULL) return true;elsereturn false;/ 從鏈表中拿出一個數(shù)據(jù)void popNode(PNode &Head , PNode &FNode) if(isEmpty(Head). 學習幫手 .專業(yè)整理 .FNode = NULL; return;FNode = Head-next;Head-next = Head-next-next;FNode-next = NULL;/ 向結點的最終后繼結點鏈表中添加新的子結點void a

18、ddSpringNode(PNode &Head , PNode newData) PSPLink newNode = (PSPLink)malloc(sizeof(SPLink); newNode-pointData = newData;newNode-next = Head-child;Head-child = newNode;/ 釋放狀態(tài)圖中存放結點后繼結點地址的空間void freeSpringLink(PSPLink &Head) PSPLink tmm;while(Head != NULL)tmm = Head;Head = Head-next;free(tmm);. 學習幫手 .

19、專業(yè)整理 ./ 釋放 open 表與 closed 表中的資源 void freeLink(PNode &Head)PNode tmn;tmn = Head;Head = Head-next; free(tmn);while(Head != NULL)/ 首先釋放存放結點后繼結點地址的空間 freeSpringLink(Head-child);tmn = Head;Head = Head-next;free(tmn);/ 向普通鏈表中添加一個結點void addNode(PNode &Head , PNode &newNode) newNode-next = Head-next;Head-ne

20、xt = newNode; / 向非遞減排列的鏈表中添加一個結點void addAscNode(PNode &Head , PNode &newNode) PNode P;PNode Q;. 學習幫手 .專業(yè)整理 .P = Head-next;Q = Head;while(P != NULL & P-fvalue fvalue) Q = P;P = P-next;/ 上面判斷好位置之后，下面就是簡單的插入了 newNode-next = Q-next;Q-next = newNode;/ 計算結點額 h 值int computeHValue(PNode theNode)int num = 0;

21、for(int i = 0 ; i 3 ; i+)for(int j = 0 ; j dataij != targetij)num+;return num;/ 計算結點的 f ， g， h 值void computeAllValue(PNode &theNode , PNode parentNode) if(parentNode = NULL)theNode-gvalue = 0;. 學習幫手 .專業(yè)整理 .elsetheNode-gvalue = parentNode-gvalue + 1;theNode-hvalue = computeHValue(theNode);theNode-fva

22、lue = theNode-gvalue + theNode-hvalue;/ 初始化函數(shù)，進行算法初始條件的設置 void initial()/ 初始化 open 以及 closed 表 initLink(open);initLink(closed);/ 初始化起始結點，令初始結點的父節(jié)點為空結點 PNode NULLNode = NULL;PNode Start = (PNode)malloc(sizeof(NNode); for(int i = 0 ; i 3 ; i+)for(int j = 0 ; j dataij = starttij;Start-parent = NULL;Sta

23、rt-child = NULL;Start-next = NULL; computeAllValue(Start , NULLNode);/ 起始結點進入 open 表 addAscNode(open , Start);. 學習幫手 .專業(yè)整理 ./ 將 B 節(jié)點的狀態(tài)賦值給 A 結點void statusAEB(PNode &ANode , PNode BNode) for(int i = 0 ; i 3 ; i+)for(int j = 0 ; j dataij = BNode-dataij;/ 兩個結點是否有相同的狀態(tài)bool hasSameStatus(PNode ANode , PN

24、ode BNode) for(int i = 0 ; i 3 ; i+)for(int j = 0 ; j dataij != BNode-dataij) return false;return true; / 結點與其祖先結點是否有相同的狀態(tài)bool hasAnceSameStatus(PNode OrigiNode , PNode AnceNode) while(AnceNode != NULL). 學習幫手 .專業(yè)整理 .if(hasSameStatus(OrigiNode , AnceNode) return true;AnceNode = AnceNode-parent;return

25、 false;/ 取得方格中空的格子的位置void getPosition(PNode theNode , int &row , int &col) for(int i = 0 ; i 3 ; i+)for(int j = 0 ; j dataij = 0)row = i;col = j;return;/ 交換兩個數(shù)字的值 void changeAB(int &A , int &B) int C;C = B;B = A;A = C;. 學習幫手 .專業(yè)整理 ./ 檢查相應的狀態(tài)是否在某一個鏈表中bool inLink(PNode spciNode , PNode theLink , PNode

26、 &theNodeLink , PNode &preNode)preNode = theLink; theLink = theLink-next;while(theLink != NULL)if(hasSameStatus(spciNode , theLink)theNodeLink = theLink;return true;preNode = theLink;theLink = theLink-next;return false;/ 產生結點的后繼結點 (與祖先狀態(tài)不同 ) 鏈表 void SpringLink(PNode theNode , PNode &spring) int row;

27、int col;getPosition(theNode , row , col);/ 空的格子右邊的格子向左移動 if(col != 2)PNode rlNewNode = (PNode)malloc(sizeof(NNode); statusAEB(rlNewNode , theNode);. 學習幫手 .專業(yè)整理 .changeAB(rlNewNode-datarowcol , rlNewNode-datarowcol + 1); if(hasAnceSameStatus(rlNewNode , theNode-parent)free(rlNewNode);/ 與父輩相同，丟棄本結點els

28、erlNewNode-parent = theNode;rlNewNode-child = NULL;rlNewNode-next = NULL; computeAllValue(rlNewNode , theNode);/ 將本結點加入后繼結點鏈表addNode(spring , rlNewNode);/ 空的格子左邊的格子向右移動if(col != 0)PNode lrNewNode = (PNode)malloc(sizeof(NNode);statusAEB(lrNewNode , theNode);changeAB(lrNewNode-datarowcol , lrNewNode-d

29、atarowcol - 1); if(hasAnceSameStatus(lrNewNode , theNode-parent)free(lrNewNode);/ 與父輩相同，丟棄本結點elselrNewNode-parent = theNode;lrNewNode-child = NULL;lrNewNode-next = NULL; computeAllValue(lrNewNode , theNode);/ 將本結點加入后繼結點鏈表addNode(spring , lrNewNode);. 學習幫手 .專業(yè)整理 ./ 空的格子上邊的格子向下移動if(row != 0)PNode udNe

30、wNode = (PNode)malloc(sizeof(NNode);statusAEB(udNewNode , theNode);changeAB(udNewNode-datarowcol , udNewNode-datarow - 1col); if(hasAnceSameStatus(udNewNode , theNode-parent)free(udNewNode);/ 與父輩相同，丟棄本結點elseudNewNode-parent = theNode;udNewNode-child = NULL;udNewNode-next = NULL; computeAllValue(udNe

31、wNode , theNode);/ 將本結點加入后繼結點鏈表addNode(spring , udNewNode);/ 空的格子下邊的格子向上移動if(row != 2)PNode duNewNode = (PNode)malloc(sizeof(NNode);statusAEB(duNewNode , theNode);changeAB(duNewNode-datarowcol , duNewNode-datarow + 1col); if(hasAnceSameStatus(duNewNode , theNode-parent)free(duNewNode);/ 與父輩相同，丟棄本結點e

32、lseduNewNode-parent = theNode;duNewNode-child = NULL;duNewNode-next = NULL;. 學習幫手 .專業(yè)整理 .computeAllValue(duNewNode , theNode); / 將本結點加入后繼結點鏈表 addNode(spring , duNewNode);/ 輸出給定結點的狀態(tài)void outputStatus(PNode stat)for(int i = 0 ; i 3 ; i+)for(int j = 0 ; j 3 ; j+)cout dataij ;cout gvalue;if(goal-parent

33、!= NULL) outputBestRoad(goal-parent); endl;cout 第 deepnum- 層的狀態(tài)：outputStatus(goal);. 學習幫手 .專業(yè)整理 .PNode spring;/tmpNode的后繼結點鏈void AStar()PNode tmpNode;/ 指向從 open 表中拿出并放到 closed 表中的結點的指針PNode tmpLNode;/tmpNode的某一個后繼結點PNode tmpChartNode;PNode thePreNode;/針指向將要從 closed 表中移到 open 表中的結點的前一個結點的指bool getGoal = false;/標識是否達到目標狀態(tài)long numcount = 1;/記錄從 open 表中拿出結點的序號initial();/ 對函數(shù)進行初始化 initLink(spring);/ 對后繼鏈表的初始化 tmpChartNode = NULL;cout 從 open 表中拿出的結點的狀態(tài)