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

1、人工智能實(shí)驗(yàn)一報(bào)告題目：采用A*算法解決八數(shù)碼問題姓名：XXX學(xué)號(hào)：10S003028專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)提交日期：2011-05-04目錄1 問題描述 - 2 -1.1 待解決問題的解釋 - 2 -1.2 問題的搜索形式描述 - 2 -1.3 解決方案介紹（原理） - 3 -2 算法介紹 - 4 -2.1A* 搜索算法一般介紹 - 4 -2.2 算法偽代碼 - 4 -3 算法實(shí)現(xiàn) - 5 -3.1 實(shí)驗(yàn)環(huán)境與問題規(guī)模 - 5 -3.2 數(shù)據(jù)結(jié)構(gòu) - 5 -3.3 實(shí)驗(yàn)結(jié)果 - 6 -3.4 系統(tǒng)中間及最終輸出結(jié)果 - 6 -4 參考文獻(xiàn) - 7 -5 附錄源代碼及其注釋 - 7 -1問題描

2、述所謂八數(shù)碼問題是指這樣一種游戲：將分別標(biāo)有數(shù)字 1, 2, 3,，8的八 塊正方形數(shù)碼牌任意地放在一塊3X 3的數(shù)碼盤上。放牌時(shí)要求不能重疊。于是, 在3X3的數(shù)碼盤上出現(xiàn)了一個(gè)空格?，F(xiàn)在要求按照每次只能將與空格相鄰的數(shù) 碼牌與空格交換的原則，不斷移動(dòng)該空格方塊以使其和相鄰的方塊互換，直至達(dá) 到所定義的目標(biāo)狀態(tài)?？崭穹綁K在中間位置時(shí)有上、下、左、右 4個(gè)方向可移動(dòng)， 在四個(gè)角落上有2個(gè)方向可移動(dòng)，在其他位置上有3個(gè)方向可移動(dòng)，問題描述如下 圖1-1所示：1.1待解決問題的解釋首先，八數(shù)碼問題包括一個(gè)初始狀態(tài)(START)和目標(biāo)狀態(tài)(END)，所謂解決 八數(shù)碼問題就是在兩個(gè)狀態(tài)間尋找一系列可過

3、渡狀態(tài)：(STARTSTATE1STATE2.END)這個(gè)狀態(tài)是否存在就是我們要解決的第一個(gè)問題：Q1:每一個(gè)狀態(tài)及每一次操作的表示方法？有許多表示方法，比如一個(gè) 3*3的八數(shù)碼盤可以壓縮成一個(gè)int 值表示，但不適用于15 puzzle或大于8的puzzle問題。如果對(duì)空間要求很高，應(yīng) 該還可以再壓縮。本文采用一個(gè)int表示的方法。表示方法如下：由于int的表 示范圍大于1e9,所以我們?nèi)∫粋€(gè)int的低9 位,為了方便尋找空格的位置，int的 個(gè)位我們用來放空格的位置(19)。而前8位，按照行從上到下，列從左到右的 順序依次記錄對(duì)應(yīng)位置上的數(shù)字。1.2問題的搜索形式描述八數(shù)碼問題形式化描述：

4、初始狀態(tài)：初始狀態(tài)向量：規(guī)定向量中各分量對(duì)應(yīng)的位置，各位置上的數(shù)字。把3X3的棋盤按從左到右，從上到下的順序?qū)懗梢粋€(gè)一維向量。我們可以設(shè)定初始狀態(tài)： 后繼函數(shù)：按照某種規(guī)則移動(dòng)數(shù)字得到的新向量。例如： 目標(biāo)測(cè)試：新向量是都是目標(biāo)狀態(tài)。即 是目標(biāo)狀態(tài)？ 路徑耗散函數(shù)：每次移動(dòng)代價(jià)為 1，每執(zhí)行一條規(guī)則后總代價(jià)加 1。1.3 解決方案介紹(原理)該問題是一個(gè)搜索問題。 它是一種狀態(tài)到另一種狀態(tài)的變換。 要解決這個(gè)問 題，必須先把問題轉(zhuǎn)化為數(shù)字描述。 由于八數(shù)碼是一個(gè) 3*3 的矩陣， 但在算法中 不實(shí)用矩陣， 而是將這個(gè)矩陣轉(zhuǎn)化為一個(gè)一維數(shù)組， 使用這個(gè)一維數(shù)組來表示八 數(shù)碼，但是移動(dòng)時(shí)要遵守相關(guān)

5、規(guī)則。(1) 可用如下形式的規(guī)則來表示數(shù)字通過空格進(jìn)行移動(dòng)： Va1,a2,a3,a4,a5,a6,a7,a8,a9(2) 共 24 條移動(dòng)規(guī)則，對(duì)應(yīng)與每個(gè)位置的移動(dòng)規(guī)則。(3) 搜索順序舉例：優(yōu)先移動(dòng)行數(shù)小的棋子 (數(shù)字 ) 同一行中優(yōu)先移動(dòng)列數(shù)大的棋子(4) 約束規(guī)則：不使離開既定位置的數(shù)字?jǐn)?shù)增加八數(shù)碼的節(jié)點(diǎn)擴(kuò)展應(yīng)當(dāng)遵循棋子的移動(dòng)規(guī)則。 按規(guī)則，每一次可以將一個(gè)與 空格相鄰的棋子移動(dòng)到空格中， 實(shí)際上也可以看做空格的相反方向移動(dòng)。 空格的 移動(dòng)方向可以是上下左右， 當(dāng)然不能出邊界。 棋子的位置， 也就是保存狀態(tài)的數(shù) 組元素的下標(biāo)，空格移動(dòng)后，相應(yīng)位置發(fā)生變化，在不移出邊界的條件下，空格 向

6、右，下，左，上移動(dòng)后，新位置是原位置分別加上1,3，-1，-3。在這里，空格可以用任意數(shù)字表示。操作本文用 u r d l 分別表示空格的向上向右向下向左 四個(gè)操作。圖的搜索策略：經(jīng)分析， 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ā)式搜索法。本實(shí)驗(yàn)采用啟發(fā)式 A* 搜索算法來實(shí)現(xiàn)2 算法介紹問題的求解實(shí)際上就是在這個(gè)圖中找到一條路徑可以從開始到結(jié)果。 這個(gè)尋 找的過程就是狀態(tài)空間搜索。 常用的狀態(tài)空間

7、搜索有深度優(yōu)先和廣度優(yōu)先。 廣度 優(yōu)先是從初始狀態(tài)一層一層向下找， 直到找到目標(biāo)為止。 深度優(yōu)先是按照一定的 順序前查找完一個(gè)分支，再查找另一個(gè)分支，以至找到目標(biāo)為止。啟發(fā)式搜索就是在狀態(tài)空間中的搜索對(duì)每一個(gè)搜索的位置進(jìn)行評(píng)估， 得到最 好的位置，再從這個(gè)位置進(jìn)行搜索直到目標(biāo)。 這樣可以省略大量無畏的搜索路徑， 提高了效率。2.1A* 搜索算法一般介紹A* 算法實(shí)際是一種啟發(fā)式搜索，所謂啟發(fā)式搜索，就是利用一個(gè)估價(jià)函數(shù) 評(píng)估每次的的決策的價(jià)值， 決定先嘗試哪一種方案， 這樣可以極大的優(yōu)化普通的 廣度優(yōu)先搜索。一般來說，從出發(fā)點(diǎn)(A)到目的地(B)的最短距離是固定的，我們 可以寫一個(gè)函數(shù) jud

8、ge() 估計(jì) A 到 B 的最短距離，如果程序已經(jīng)嘗試著從出 發(fā)點(diǎn) A 沿著某條路線移動(dòng)到了 C 點(diǎn), 那么我們認(rèn)為這個(gè)方案的 A B 間的估 計(jì)距離為 A 到 C 實(shí)際已經(jīng)行走了的距離 H 加上用 judge() 估計(jì)出的 C 到 B 的距離。如此，無論我們的程序搜索展開到哪一步， 都會(huì)算出一個(gè)評(píng)估值， 每一次決 策后，將評(píng)估值和等待處理的方案一起排序， 然后挑出待處理的各個(gè)方案中最有 可能是最短路線的一部分的方案展開到下一步，一直循環(huán)到對(duì)象移動(dòng)到目的地， 或所有方案都嘗試過卻沒有找到一條通向目的地的路徑則結(jié)束。A*算法是一個(gè)可采納的最好優(yōu)先算法。A*算法的估價(jià)函數(shù)可表示為：f(n) =

9、g(n) + h(n)這里，f(n)是估價(jià)函數(shù)，g(n)是起點(diǎn)到終點(diǎn)的最短路徑值，h(n)是n到目標(biāo)的最 斷路經(jīng)的啟發(fā)值。由于這個(gè)f(n)其實(shí)是無法預(yù)先知道的，所以我們用前面的估價(jià) 函數(shù)f(n)做近似。g(n)代替g(n)，但g(n)=g(n)才可(大多數(shù)情況下都是滿足的， 可以不用考慮)，h(n)代替h(n),但h(n)v=h(n)才可?？梢宰C明應(yīng)用這樣的估價(jià) 函數(shù)是可以找到最短路徑的，也就是可采納的。2.2 算法偽代碼首先定義兩個(gè)表， open 表用于存放已經(jīng)生成，且已用啟發(fā)式函數(shù)進(jìn)行過估 計(jì)或評(píng)價(jià)，但尚未產(chǎn)生它們的后繼節(jié)點(diǎn)的那些結(jié)點(diǎn)，這些結(jié)點(diǎn)也稱未考察結(jié)點(diǎn)； closed表用于存放已經(jīng)生

10、成，且已考察過的結(jié)點(diǎn)。設(shè)SO為初態(tài)，Sg為目標(biāo)狀態(tài)。 具體過程如下： 把SO放入open表，記為f=h，令closed為空表；(2) 重復(fù)下列過程，直至找到目標(biāo)結(jié)點(diǎn)為止。若 open為空表，則失??；(3) 選取open表中未設(shè)置過的具有最小f值的結(jié)點(diǎn)為最佳節(jié)點(diǎn)，并放入 closed表 中(4) 若最佳節(jié)點(diǎn)不是目標(biāo)節(jié)點(diǎn)，則擴(kuò)展之，產(chǎn)生后繼節(jié)點(diǎn)。(5) 對(duì)每個(gè)后繼結(jié)點(diǎn)進(jìn)行下列過程：? 建立從該后繼結(jié)點(diǎn)返回最佳節(jié)點(diǎn)的指針；? 計(jì)算g (后繼結(jié)點(diǎn))=g (最佳節(jié)點(diǎn))+k (最佳節(jié)點(diǎn)，后繼結(jié)點(diǎn))；? Ss：如果該后繼節(jié)點(diǎn) open,貝U稱此節(jié)點(diǎn)為old，并把它添加至最佳節(jié)點(diǎn) 的后繼節(jié)點(diǎn)中? 比較新舊路徑

11、代價(jià)，如果個(gè) g (后繼節(jié)點(diǎn))vg(old),則重新確定old的父 親節(jié)點(diǎn)? 若至 old 節(jié)點(diǎn)的代價(jià)比較低或一樣，則停止擴(kuò)展節(jié)點(diǎn)? 若后繼節(jié)點(diǎn)不再open表中，則看其是否在closed中? 若后繼節(jié)點(diǎn)在open表中，則轉(zhuǎn)向Ss；? 若后繼節(jié)點(diǎn)既不在open表中，又不在closed表中，則把它放入open表 中，并填入最佳節(jié)點(diǎn)的后裔表，然后走下一步計(jì)算f值(7)GO LOOP3 算法實(shí)現(xiàn)3.1 實(shí)驗(yàn)環(huán)境與問題規(guī)模(1) 實(shí)驗(yàn)環(huán)境： Windows XP(2) 實(shí)驗(yàn)編程工具： VC+6.O(3) 問題規(guī)模算法規(guī)模小，最大搜索深度不超過 32。3.2 數(shù)據(jù)結(jié)構(gòu)本實(shí)驗(yàn)主要采用鏈表，隊(duì)列，堆：stru

12、ct Chess/棋 盤int cellNN;/ 數(shù)碼數(shù)組int Value;/評(píng)估值Direction BelockDirec;/ 所屏蔽方向 struct Chess * Pare nt;父節(jié)點(diǎn);queuevstruct Chess * Queue;隊(duì)列stackvChess *Stack;/堆Chess *p=ChessList;p=p-Pare nt;/鏈表3.3 實(shí)驗(yàn)結(jié)果經(jīng)測(cè)試，程序運(yùn)行良好，結(jié)果正確。輸入測(cè)試數(shù)據(jù)，初試狀態(tài)，目標(biāo)狀態(tài) v0 1 2 3 4 5 6 7 8，運(yùn)行結(jié)果有解，共經(jīng)過四步。3.4 系統(tǒng)中間及最終輸出結(jié)果輸入數(shù)據(jù)結(jié)果如下圖 3-1 所示：圖 3-1 輸入數(shù)據(jù)結(jié)

13、果運(yùn)行中間及最終結(jié)果如下圖 3-2 所示圖 3-2 程序運(yùn)行結(jié)果4 參考文獻(xiàn)1Artificial intelligence :;a modern approach 人工智能 : 一種現(xiàn)代方法 作者： Russell, Stuart J. 出版社：清華大學(xué)出版社2 CSDN 博客5 附錄源代碼及其注釋/* 栗麗霞 2011-04-29*/#include #include stdio.h#include stdlib.h#include time.h#include string.h#include #include using namespace std;const int N=3;/3*3

14、 棋盤const int Max_Step=32;/ 最大搜索深度enum DirectionNone,Up,Down,Left,Right;/ 方向，分別對(duì)應(yīng)上下左右 struct Chess/ 棋盤int chessNumNN;/ 棋盤數(shù)碼int Value;/ 評(píng)估值Direction BelockDirec;/ 所屏蔽方向struct Chess * Pare nt; 父節(jié)點(diǎn);void PrintChess(struct Chess *TheChess);/ 打印棋盤struct Chess * MoveChess(struct Chess * TheChess,Direction D

15、irect,bool CreateNewChess);/ 移 動(dòng)棋盤數(shù)字int Appraisal(struct Chess * TheChess,struct Chess * Target);/ 估價(jià)函數(shù)struct Chess * Search(struct Chess* Begin,struct Chess * Target);/A* 搜索函數(shù)int main()/本程序的一組測(cè)試數(shù)據(jù)為/*初始棋盤*1 4 0* *3 5 2* *6 7 8*/*目標(biāo)棋盤*0 1 2*3 4 5*6 7 8*/Chess Target;Chess *Begin,*ChessList;Begin=new

16、Chess;int i;cout 請(qǐng)輸入初始棋盤，各數(shù)字用空格隔開：endl;for(i=0;iN;i+)for(int j=0;jBegin-chessNumij;endl;cout 請(qǐng)輸入目標(biāo)棋盤，各數(shù)字用空格隔開：for(i=0;iN;i+)for(int j=0;jTarget.chessNumij;/獲取初始棋盤Appraisal(Begin,&Target);Begin-Parent=NULL;Begin-BelockDirec=None;Target.Value=0;cout 初始棋盤 :;PrintChess(Begin);cout 目標(biāo)棋盤 :;PrintChess(&Tar

17、get);ChessList=Search(Begin,&Target);/ 搜索 /打印 if(ChessList)/* 將返回的棋盤列表利用棧將其倒敘 */Chess *p=ChessList; stackStack; while(p-Parent!=NULL)Stack.push(p);p=p-Parent;cout 搜索結(jié)果 :endl;int num=1;while(!Stack.empty()cout 第 num 步: ;num+;PrintChess(Stack.top();Stack.pop();coutn 完成 !endl;elsecout 搜索不到結(jié)果，搜索深度大于32ne

18、ndl;return 0;/打印棋盤void PrintChess(struct Chess *TheChess)cout( 評(píng)估值為 ; coutValue; cout)endl;for(int i=0;iN;i+)cout ;for(int j=0;jN;j+)coutchessNumij ;coutendl;/移動(dòng)棋盤struct Chess * MoveChess(struct Chess * TheChess,Direction Direct,bool CreateNewChess) struct Chess * NewChess;/獲取空閑格位置 int i,j;for(i=0;i

19、N;i+)bool HasGetBlankCell=false;for(j=0;jchessNumij=0) HasGetBlankCell=true; break;if(HasGetBlankCell)break;int ii=i,jj=j;bool AbleMove=true;/判斷是否可以移動(dòng)switch(Direct)case Up:i+;if(i=N)AbleMove=false; break;case Down:i-;if(i=N)AbleMove=false;break;j-;if(j0)AbleMove=false;break;if(!AbleMove)/ 不可以移動(dòng)則返回原節(jié)

20、點(diǎn)return TheChess;if(CreateNewChess)NewChess=new Chess();for(int x=0;xN;x+)for(int y=0;ychessNumxy=TheChess-chessNumxy;/ 創(chuàng)建新棋盤，此 時(shí)值與原棋盤一致elseNewChess=TheChess;NewChess-chessNumiijj = NewChess-chessNumij;/ 移動(dòng)數(shù)字NewChess-chessNumij=0;/ 將原數(shù)字位置設(shè)置為空格return NewChess;/估價(jià)函數(shù)int Appraisal(struct Chess * TheChess,struct Chess * Target)int Value=0;for(int i=0;iN;i+)for(int j=0;jchessNumij!=Target-chessNumij) Value+;TheChess-Value=Value;return Value;/A* 搜索函數(shù)struct Chess * Search(str