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

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