采用A星算法實現(xiàn)八數(shù)碼問題

裝訂線實驗報告 人工智能實驗一報告 題目：采用A*算法解決八數(shù)碼問題成 員： 李文、郭彎彎 學 號： 、專 業(yè)： 計算機科學與技術(shù)完成日期： 2016/04/091、 實驗要求、目的及分工1.1實驗要求 使用A*算法實現(xiàn)八數(shù)碼問題，并用圖形界面展示。1.2實驗?zāi)康腶. 熟悉人工智能系統(tǒng)中的問題求解過程；b. 熟悉狀態(tài)空間的盲目搜索和啟發(fā)式搜索算法的應(yīng)用；c. 熟悉對八數(shù)碼問題的建模、求解及編程語言的應(yīng)用。1.3實驗分工我們小組共兩個人，共同查找背景資料，李文同學主要負責源代碼，郭彎彎同學主要負責實驗報告以及演示文稿的完成。2、 實驗問題2.1問題描述所謂八數(shù)碼問題是指這樣一種游戲：將分別標有數(shù)字1，2，3，8 的八塊正方形數(shù)碼牌任意地放在一塊33 的數(shù)碼盤上。放牌時要求不能重疊。于是，在33 的數(shù)碼盤上出現(xiàn)了一個空格?，F(xiàn)在要求按照每次只能將與空格相鄰的數(shù)碼牌與空格交換的原則，不斷移動該空格方塊以使其和相鄰的方塊互換，直至達到所定義的目標狀態(tài)?？崭穹綁K在中間位置時有上、下、左、右4個方向可移動，在四個角落上有2個方向可移動，在其他位置上有3個方向可移動，問題描述如下圖所示：150478326832451670 (a) 初始狀態(tài) (b) 目標狀態(tài) 圖1 八數(shù)碼問題示意圖2.2問題解釋 首先，八數(shù)碼問題包括一個初始狀態(tài)(START) 和目標狀態(tài)(TRAGET)，所謂解決八數(shù)碼問題就是在兩個狀態(tài)間尋找一系列可過渡狀態(tài)： （STARTSTATE1STATE2.TARGET）這個狀態(tài)是否存在就是我們要解決的第一個問題；第二個問題是我們要求出走的路徑是什么。2.3八數(shù)碼問題形式化描述初始狀態(tài)： 初始狀態(tài)向量：規(guī)定向量中各分量對應(yīng)的位置，各位置上的數(shù)字。把33的棋盤寫成一個二維向量。我們可以設(shè)定初始狀態(tài)：后繼函數(shù)：按照某種規(guī)則移動數(shù)字得到的新向量。例如： 路徑耗散函數(shù)：規(guī)定每次移動代價為1，即每執(zhí)行一條規(guī)則后總代價加1。2.4解決方案選擇該問題是一個搜索問題。它是一種狀態(tài)到另一種狀態(tài)的變換。要解決這個問題，必須先把問題轉(zhuǎn)化為數(shù)字描述。由于八數(shù)碼是一個3*3的矩陣，但在算法中不是用矩陣，而是將這個矩陣轉(zhuǎn)化為一個二維數(shù)組，使用這個二維數(shù)組來表示八數(shù)碼，但是移動時要遵守相關(guān)規(guī)則。按規(guī)則，每一次可以將一個與空格相鄰的棋子移動到空格中，實際上也可以看做空格的相反方向移動。空格的移動方向可以是上下左右，當然不能出邊界。棋子的位置，也就是保存狀態(tài)的數(shù)組元素的下標，空格移動后，相應(yīng)位置發(fā)生變化。經(jīng)分析，問題的求解實際上就是在這個圖中找到一條路徑可以從開始到結(jié)果。這個尋找的過程就是狀態(tài)空間搜索。常用的狀態(tài)空間搜索有深度優(yōu)先和廣度優(yōu)先。廣度優(yōu)先是從初始狀態(tài)一層一層向下找，直到找到目標為止。深度優(yōu)先是按照一定的順序前查找完一個分支，再查找另一個分支，以至找到目標為止。啟發(fā)式搜索就是在狀態(tài)空間中的搜索對每一個搜索的位置進行評估，得到最好的位置，再從這個位置進行搜索直到目標。這樣可以省略大量無畏的搜索路徑，提高了效率。所以，本實驗采用啟發(fā)式A*搜索算法來實現(xiàn)。3、 A*算法3.1算法介紹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(shù)(n)是從初始結(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明應(yīng)用這樣的估價函數(shù)是可以找到最短路徑的。3.2算法偽代碼首先定義兩個表，open表用于存放已經(jīng)生成，且已用啟發(fā)式函數(shù)進行過估計或評價，但尚未產(chǎn)生它們的后繼節(jié)點的那些結(jié)點，這些結(jié)點也稱未考察結(jié)點；closed表用于存放已經(jīng)生成，且已考察過的結(jié)點。把起始格添加到 開啟列表 do 尋找開啟列表中F值最低的格子, 我們稱它為當前格 把它切換到關(guān)閉列表 對當前格相鄰的8格中的每一個 if (它不可通過 | 已經(jīng)在 關(guān)閉列表 中) 什么也不做 if (它不在開啟列表中) 把它添加進 開啟列表，把當前格作為這一格的父節(jié)點, 計算這一格的 FGH if (它已經(jīng)在開啟列表中) if (用G值為參考檢查新的路徑是否更好，更低的G值意味著更好的路徑) 把這一格的父節(jié)點改成當前格，并且重新計算這一格的 GF 值 while( 目標格已經(jīng)在 開啟列表， 這時候路徑被找到) 如果開啟列表已經(jīng)空了，說明路徑不存在最后從目標格開始，沿著每一格的父節(jié)點移動直到回到起始格，這就是路徑。四、算法實現(xiàn)4.1 實驗環(huán)境(1)實驗環(huán)境：Windows 7(2)IDE：codeblocks（圖形界面的實現(xiàn)調(diào)用codeblocks里windows一系列函數(shù)）4.2數(shù)據(jù)結(jié)構(gòu)本實驗主要使用鏈表：/定義狀態(tài)圖中的結(jié)點數(shù)據(jù)結(jié)構(gòu)typedef struct Node int data33;/結(jié)點所存儲的狀態(tài) struct Node *parent;/指向結(jié)點的父親結(jié)點 struct Node *child; /用于指向臨時子節(jié)點，并且用于最后的最佳路徑上結(jié)點的子結(jié)點 struct Node *next;/指向open或者closed表中的后一個結(jié)點 int fvalue;/結(jié)點的總的路徑 int gvalue;/結(jié)點的實際路徑 int hvalue;/結(jié)點的到達目標的苦難程度NNode , *PNode;/* 定義兩個全局鏈表 */PNode OPEN,CLOSE;4.3實驗結(jié)果截屏4.4參考資料資料來源百度搜索，博客查找鏈接：/technology/archive/2011/05/26/.html5、 實驗心得1、 學習了新的算法A*算法，結(jié)合了偽代碼和網(wǎng)上的一些教程，實現(xiàn)了八數(shù)碼問題的求解，這是對我們編程能力的一種提升，也讓我們懂了更多做題的方法。 2、在這次實驗中，存在著許許多多細節(jié)上的小問題，是因為編程基礎(chǔ)不牢靠而產(chǎn)生的，通過這次實驗又讓我們懂了許多細節(jié)上的問題，以后就不會發(fā)生類似的問題了。 3、小組合作的形式能讓我們更多的去溝通與思考，學會理解與合作。附錄：程序源代碼及注釋#include #include #include#include #include #include #include #include #include /包含多媒體函數(shù)庫#pragma comment(lib,winmm.lib)/包含多媒體函數(shù)庫對應(yīng)的庫文件using namespace std;int start 33 = 2,8,3,1,6,4,7,0,5;int target33 = 1,3,4,8,2,0,7,6,5;/定義狀態(tài)圖中的結(jié)點數(shù)據(jù)結(jié)構(gòu)typedef struct Node int data33;/結(jié)點所存儲的狀態(tài) struct Node *parent;/指向結(jié)點的父親結(jié)點 struct Node *child; /用于指向臨時子節(jié)點，并且用于最后的最佳路徑上結(jié)點的子結(jié)點 struct Node *next;/指向open或者closed表中的后一個結(jié)點 int fvalue;/結(jié)點的總的路徑 int gvalue;/結(jié)點的實際路徑 int hvalue;/結(jié)點的到達目標的苦難程度NNode , *PNode;/* 定義兩個全局鏈表 */PNode OPEN,CLOSE;/* 將光標移動到指定位置 */void gotoxy(HANDLE hout, const int X, const int Y)COORD coord;coord.X = X;coord.Y = Y;SetConsoleCursorPosition(hout,coord);void setcolor(HANDLE hout, const int bg_color, const int fg_color)SetConsoleTextAttribute(hout, bg_color*16+fg_color);HANDLE hout = GetStdHandle(STD_OUTPUT_HANDLE); /取標準輸出設(shè)備對應(yīng)的句柄void output(int x,int y,int arr33) int i,j,k; for(j=0; j3; +j) for(i=0; i5; +i) gotoxy(hout,x,y+5*j+i); for(k=0; k3; +k) setcolor(hout,arrjk,arrjk); cout ; setcolor(hout,0,15); cout next = NULL;/判斷鏈表是否為空OKbool isEmpty(PNode Head) if(Head-next = NULL) return true; else return false;/求a和b相減的絕對值int subAbs(int a,int b) return (ab)?(a-b):(b-a);/* 計算結(jié)點的h值(到達目標結(jié)點的苦難程度) */int computeHValue(PNode theNode) int value = 0,singlevalue; int i,j,k,m; int temp; for(i=0; i3; +i) for(j=0; jdataij; if( temp ) /只有不是0的數(shù)字的才計入苦難值 for(k=0; k3; +k) for(m=0; mgvalue = 0; else theNode-gvalue = parentNode-gvalue + 1; theNode-hvalue = computeHValue(theNode); theNode-fvalue = theNode-gvalue + theNode-hvalue;/* 取得方格中空的格子的位置 */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; /* 將theNode所指結(jié)點作為第一個結(jié)點加入LIST表中 */void addNode(PNode &LIST,PNode theNode) theNode-next = LIST-next; LIST-next = theNode;/兩個結(jié)點是否有相同的狀態(tài)bool hasSameStatus(PNode ANode , PNode BNode) int i,j; for(i = 0 ; i 3 ; i+) for(j = 0 ; j dataij != BNode-dataij) return false; return true;/* 檢測theNode是否在LIST表中,若在則sameNode指向與theNode有相同狀態(tài)的結(jié)點 */bool inLink(PNode theNode, PNode &LIST, PNode &sameNode) sameNode = NULL; PNode temp = LIST-next; while(temp!=NULL) if(hasSameStatus(theNode,temp) = true) sameNode = temp; return true; temp = temp-next; return false;/將B節(jié)點的狀態(tài)賦值給A結(jié)點void statusBToA(PNode &ANode , PNode BNode) for(int i = 0 ; i 3 ; i+) for(int j = 0 ; j dataij = BNode-dataij;/交換兩個數(shù)字的值void changeAB(int &A , int &B) int C; C = B; B = A; A = C;/* 初始化OPEN表和CLOSE表，并將開始狀態(tài)加入OPEN表中 */void initial(PNode &Start) initLink(OPEN); initLink(CLOSE); /初始化起始結(jié)點，令初始結(jié)點的父節(jié)點為空結(jié)點 PNode NULLNode = NULL; Start = (PNode)malloc(sizeof(NNode); for(int i = 0 ; i 3 ; i+) for(int j = 0 ; j dataij = startij; Start-parent = NULL; Start-child = NULL; Start-next = NULL; computeAllValue(Start , NULLNode); /起始結(jié)點進入open表 addNode(OPEN , Start);/* 從OPEN表(非空)中找到f值最小的結(jié)點 */void findfValueMinNode(PNode &theMinNode,PNode &preNode) PNode p = OPEN,q = OPEN-next; theMinNode = q; preNode = OPEN; while(q-next) p = q; q = q-next; if(q-fvalue fvalue) theMinNode = q; preNode = p; /* 生成theNode結(jié)點的子節(jié)點的同時進行對子節(jié)點的處理 */void genDealSubNode(PNode theNode) int row; int col; PNode sameNode = NULL; getPosition(theNode , row , col); if(col!=2)/空的格子右邊的格子向左移動 PNode rlNewNode = (PNode)malloc(sizeof(NNode); statusBToA(rlNewNode , theNode); changeAB(rlNewNode-datarowcol , rlNewNode-datarowcol + 1); if( inLink(rlNewNode, CLOSE, sameNode)=false )/已經(jīng)在CLOSE表中，則忽略 if( inLink(rlNewNode, OPEN, sameNode) )/不在CLOSE表中，但是在OPEN表中 if( sameNode-gvalue theNode-gvalue + 1)/把這一格的父節(jié)點改成當前格, 并且重新計算這一格的 GF 值 sameNode-parent = theNode; computeAllValue(sameNode, theNode); else/不在CLOSE表中，也不在OPEN表中,則將其加入OPEN表中 addNode(OPEN,rlNewNode); rlNewNode-parent = theNode; computeAllValue(rlNewNode, theNode); if(col!=0)/空的格子左邊的格子向右移動 PNode lrNewNode = (PNode)malloc(sizeof(NNode); statusBToA(lrNewNode , theNode); changeAB(lrNewNode-datarowcol , lrNewNode-datarowcol - 1); if( inLink(lrNewNode, CLOSE, sameNode)=false )/已經(jīng)在CLOSE表中，則忽略 if( inLink(lrNewNode, OPEN, sameNode) )/不在CLOSE表中，但是在OPEN表中 if( sameNode-gvalue theNode-gvalue + 1)/把這一格的父節(jié)點改成當前格, 并且重新計算這一格的 GF 值 sameNode-parent = theNode; computeAllValue(sameNode, theNode); else/不在CLOSE表中，也不在OPEN表中,則將其加入OPEN表中 addNode(OPEN,lrNewNode); lrNewNode-parent = theNode; computeAllValue(lrNewNode, theNode); if(row!=2)/空的格子下邊的格子向上移動 PNode duNewNode = (PNode)malloc(sizeof(NNode); statusBToA(duNewNode , theNode); changeAB(duNewNode-datarow+1col , duNewNode-datarowcol); if( inLink(duNewNode, CLOSE, sameNode)=false )/已經(jīng)在CLOSE表中，則忽略 if( inLink(duNewNode, OPEN, sameNode) )/不在CLOSE表中，但是在OPEN表中 if( sameNode-gvalue theNode-gvalue + 1)/把這一格的父節(jié)點改成當前格, 并且重新計算這一格的 GF 值 sameNode-parent = theNode; computeAllValue(sameNode, theNode); else/不在CLOSE表中，也不在OPEN表中,則將其加入OPEN表中 addNode(OPEN,duNewNode); duNewNode-parent = theNode; computeAllValue(duNewNode, theNode); if(row!=0)/空的格子上邊的格子向下移動 PNode udNewNode = (PNode)malloc(sizeof(NNode); statusBToA(udNewNode , theNode); changeAB(udNewNode-datarow-1col , udNewNode-datarowcol); if( inLink(udNewNode, CLOSE, sameNode)=false )/已經(jīng)在CLOSE表中，則忽略 if( inLink(udNewNode, OPEN, sameNode) )/不在CLOSE表中，但是在OPEN表中 if( sameNode-gvalue theNode-gvalue + 1)/把這一格的父節(jié)點改成當前格, 并且重新計算這一格的 GF 值 sameNode-parent = theNode; computeAllValue(sameNode, theNode); else/不在CLOSE表中，也不在OPEN表中,則將其加入OPEN表中 addNode(OPEN,udNewNode); udNewNode-parent = theNode; computeAllValue(udNewNode, theNode); /* 通過調(diào)用前面寫的函數(shù)實現(xiàn)總的函數(shù) */bool AStar(PNode &theMinNode) PNode Start; initial(Start); theMinNode = NULL; PNode preNode = NULL; while(isEmpty(OPEN)=false) findfValueMinNode(theMinN