八數(shù)碼問題A算法的實現(xiàn)及性能分析

1、八數(shù)碼問題A*算法的實現(xiàn)及性能分析 計算機科學(xué)與技術(shù)學(xué)院專業(yè)：計算機科學(xué)與技術(shù)161210404 楊凱迪目錄一、8數(shù)碼問題31.問題描述32. 八數(shù)碼問題形式化描述33. 解決方案4二、A*算法41. A*搜索算法一般介紹42. A*算法的偽代碼53. 建立合適的啟發(fā)式6三、算法實現(xiàn)及性能比較7四、算法性能分析8五、結(jié)論9六、參考文獻10附錄10一、8數(shù)碼問題1.問題描述八數(shù)碼問題是指這樣一種游戲：將分別標(biāo)有數(shù)字1，2，3，8 的八塊正方形數(shù)碼牌任意地放在一塊3×3 的數(shù)碼盤上。放牌時要求不能重疊。于是，在3×3 的數(shù)碼盤上出現(xiàn)了一個空格?，F(xiàn)在要求按照每次只能將與空格相鄰的

2、數(shù)碼牌與空格交換的原則，不斷移動該空格方塊以使其和相鄰的方塊互換，直至達到所定義的目標(biāo)狀態(tài)。空格方塊在中間位置時有上、下、左、右4個方向可移動，在四個角落上有2個方向可移動，在其他位置上有3個方向可移動，問題描述如圖1-1所示 初始狀態(tài) 過渡狀態(tài) 最終狀態(tài)圖1-1 八數(shù)碼問題執(zhí)行過程2. 八數(shù)碼問題形式化描述初始狀態(tài)：初始狀態(tài)向量：規(guī)定向量中各分量對應(yīng)的位置，各位置上的數(shù)字。把3×3的棋盤按從左到右，從上到下的順序?qū)懗梢粋€一維向量。我們可以設(shè)定初始狀態(tài)：<1,5,2,4,0,3,6,7,8>后繼函數(shù)：按照某種規(guī)則移動數(shù)字得到的新向量。例如：<1,5,2,4,0,3,

3、6,7,8>®<1,0,2,4,5,3,6,7,8>目標(biāo)測試：新向量是都是目標(biāo)狀態(tài)。即<1,2,3,4,5,6,7,8,0>是目標(biāo)狀態(tài)？路徑耗散函數(shù)：每次移動代價為1，每執(zhí)行一條規(guī)則后總代價加1。3. 解決方案該問題是一個搜索問題。它是一種狀態(tài)到另一種狀態(tài)的變換。要解決這個問題，必須先把問題轉(zhuǎn)化為數(shù)字描述。由于八數(shù)碼是一個3*3的矩陣，但在算法中不實用矩陣，而是將這個矩陣轉(zhuǎn)化為一個一維數(shù)組，使用這個一維數(shù)組來表示八數(shù)碼，但是移動時要遵守相關(guān)規(guī)則。(1)可用如下形式的規(guī)則來表示數(shù)字通過空格進行移動：<a1,a2,a3,a4,a5,a6,a7,a8,a

4、9><b1,b2,b3,b4,b5,b6,b7,b8,b9>(2)共24條移動規(guī)則，對應(yīng)與每個位置的移動規(guī)則。(3)搜索順序舉例：1) 優(yōu)先移動行數(shù)小的棋子(數(shù)字)2) 同一行中優(yōu)先移動列數(shù)大的棋子(4)約束規(guī)則：不使離開既定位置的數(shù)字數(shù)增加八數(shù)碼的節(jié)點擴展應(yīng)當(dāng)遵循棋子的移動規(guī)則。按規(guī)則，每一次可以將一個與空格相鄰的棋子移動到空格中，實際上也可以看做空格的相反方向移動?？崭竦囊苿臃较蚩梢允巧舷伦笥?，當(dāng)然不能出邊界。棋子的位置，也就是保存狀態(tài)的數(shù)組元素的下標(biāo)，空格移動后，相應(yīng)位置發(fā)生變化，在不移出邊界的條件下，空格向右，下，左，上移動后，新位置是原位置分別加上1,3，-1，-3

5、。在這里，空格可以用任意數(shù)字表示。操作本文用u(up) r(right) d(down) l(left) 分別表示空格的向上向右向下向左四個操作。經(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ā)式搜索法。本實驗采用啟發(fā)式A*搜索算法來實現(xiàn)。二、A*算法1. A*搜索算法一般介紹A* 算法實際是一種啟發(fā)式搜索，所謂啟發(fā)式搜索，就是利用一個估價函數(shù)評估每次的的決策的價值，決定先嘗試哪一種方案，這樣可以極大的優(yōu)化普通的廣度優(yōu)先

6、搜索。一般來說，從出發(fā)點(A)到目的地(B)的最短距離是固定的，我們可以寫一個函數(shù) judge() 估計 A 到 B 的最短距離，如果程序已經(jīng)嘗試著從出發(fā)點 A 沿著某條路線移動到了 C 點, 那么我們認為這個方案的 A B 間的估計距離為 A 到 C 實際已經(jīng)行走了的距離 H 加上用 judge() 估計出的 C 到 B 的距離。如此，無論我們的程序搜索展開到哪一步，都會算出一個評估值，每一次決策后，將評估值和等待處理的方案一起排序，然后挑出待處理的各個方案中最有可能是最短路線的一部分的方案展開到下一步，一直循環(huán)到對象移動到目的地，或所有方案都嘗試過卻沒有找到一條通向目的地的路徑則結(jié)束。A*

7、算法是一個可采納的最好優(yōu)先算法。A*算法的估價函數(shù)可表示為：f'(n) = g'(n) + h'(n)這里，f'(n)是估價函數(shù)，g'(n)是起點到終點的最短路徑值，h'(n)是n到目標(biāo)的最斷路經(jīng)的啟發(fā)值。由于這個f'(n)其實是無法預(yù)先知道的，所以我們用前面的估價函數(shù)f(n)做近似。g(n)代替g'(n)，但g(n)>=g'(n)才可（大多數(shù)情況下都是滿足的，可以不用考慮），h(n)代替h'(n)，但h(n)<=h'(n)才可。可以證明應(yīng)用這樣的估價函數(shù)是可以找到最短路徑的，也就是可采納的。2

8、. A*算法的偽代碼創(chuàng)建兩個表，OPEN表保存所有已生成而未考察的節(jié)點，CLOSED表中記錄已訪問過的節(jié)點。算起點的估價值;將起點放入OPEN表;    while(OPEN!=NULL)    從OPEN表中取估價值f最小的節(jié)點n;          if(n節(jié)點=目標(biāo)節(jié)點)          break;      

9、;               for(當(dāng)前節(jié)點n 的每個子節(jié)點X)                算X的估價值;               if(X in OPEN) 

10、0;                            if( X的估價值小于OPEN表的X估價值 )              把n設(shè)置為X的父親;    

11、0;        更新OPEN表中的估價值; /取最小路徑的估價值                                        &

12、#160; if(X inCLOSE)                  if( X的估價值小于CLOSE表的X估價值 )              把n設(shè)置為X的父親;            

13、60;              將該節(jié)點從close表中除去           把X節(jié)點放入OPEN /取最小路徑的估價值                    &#

14、160;                            if(X not inboth)         把n設(shè)置為X的父親;         求X的估價值;    

15、60;    并將X插入OPEN表中; /升序排列open               /end for將n節(jié)點插入CLOSE表中;按照估價值將OPEN表中的節(jié)點排序; /實際上是比較OPEN表內(nèi)節(jié)點f的大小，從最小路徑的節(jié)點向下進行。   /end while(OPEN!=NULL)保存路徑，即從終點開始，每個節(jié)點沿著父節(jié)點移動直至起點，這就是你的路徑；3. 建立合適的啟發(fā)式A*算法有個計算公式 f(x) = g(

16、x)+h(x)其中g(shù)(x)為從起始狀態(tài)到當(dāng)前狀態(tài)所消耗的步數(shù)，h(x)為一個啟發(fā)值，估算從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)所需的步數(shù)，一般h(x)小于等于實際需要步數(shù)為好，這樣不會將最優(yōu)解忽略，因為h(x)和解空間有一些關(guān)系，如果h(x)設(shè)置的比實際需要的步數(shù)多，那么解空間就有可能將最優(yōu)解忽略。舉個例子吧，寬度優(yōu)先搜索就是h(x)=0帶來的效果，深度優(yōu)先搜索就是g(x)=0帶來的效果，不過h(x)距離h*(x)實際需要的步數(shù)的程度不能過大，否則h(x)就沒有過強的區(qū)分能力，算法效率并不會很高。對一個好的h(x)的評價是：h(x)在h*(n)實際需要的步數(shù)的下界之下，并且盡量接近h*(n)實際需要的步數(shù).那么

17、8數(shù)碼問題g(x) 為經(jīng)過上下左右移動空格附近的數(shù)字來得到新狀態(tài)所需步數(shù)，h(x)為當(dāng)前狀態(tài)與目標(biāo)狀態(tài)的距離，就是所有不在目標(biāo)位置的數(shù)字總和，必然小于h*(x)三、算法實現(xiàn)及性能比較這里通過c+語言來實現(xiàn)各種排序算法（源碼見附錄），程序運行環(huán)境為windows 7，所用編譯器為vs2013。實驗分別以不同的初始棋盤和相同的目標(biāo)棋盤為例進行測試。初始數(shù)碼棋盤1：2 0 3 1 4 6 7 5 8初始數(shù)碼棋盤2：2 4 3 0 6 8 1 7 5初始數(shù)碼棋盤3：2 3 7 6 4 8 1 0 5初始數(shù)碼棋盤4：3 2 4 5 0 7 8 1 6初始數(shù)碼棋盤5：4 0 3 2 6 8 1 7 5初始

18、數(shù)碼棋盤6：1 4 3 5 7 0 2 6 8 初始數(shù)碼棋盤7：4 6 3 2 8 5 1 0 7目標(biāo)數(shù)碼棋盤：1 2 3 4 5 6 7 8 0實驗部分結(jié)果如圖3-1：圖3-1.測試結(jié)果四、算法性能分析在測試中我們根據(jù)不同的初始數(shù)碼狀態(tài)相同的目標(biāo)數(shù)碼狀態(tài)，產(chǎn)生不同的移動步驟，并給出了其步數(shù)和運行時間（單位ms）。表1為不同的初始數(shù)碼狀態(tài)相同的目標(biāo)數(shù)碼狀態(tài)測試后得到的運行時間數(shù)據(jù)。表2為不同的初始數(shù)碼狀態(tài)相同的目標(biāo)數(shù)碼狀態(tài)能否的到正確的步驟與否的數(shù)據(jù)。 初始數(shù)據(jù)棋盤1棋盤2棋盤3棋盤4棋盤5棋盤6棋盤7步數(shù)51121013017時間(ms)52.531507.6918220134.420281

19、5.83表1 步數(shù)和運行時間（單位ms） 初始數(shù)據(jù)棋盤1棋盤2棋盤3棋盤4棋盤5棋盤6棋盤7正確與否TTTFTFT表2 能否得到正確步驟為了直觀起見，根據(jù)實驗數(shù)據(jù)畫出不同的初始數(shù)碼狀態(tài)相同的目標(biāo)數(shù)碼狀態(tài)下時間隨步數(shù)的變化趨勢圖如圖3-2所示： 圖3-2時間隨步數(shù)的變化趨勢圖根據(jù)實驗數(shù)據(jù)表2，我們可得到該算法得到正確步驟路徑的概率為：71.42%。 五、結(jié)論最后我們得出結(jié)論：時間性能上，算法所需時間隨步數(shù)的增加而逐漸呈增加趨勢，但并不是線性增長。部分時間不隨移動步數(shù)變化。該算法能得到正確的解概率約為71.42%六、參考文獻1Artificial intelligence :;a modern a

20、pproach 人工智能 : 一種現(xiàn)代方法 作者：Russell, Stuart J. 出版社：清華大學(xué)出版社附錄#include<iostream>#include<time.h>#include<windows.h>#include<vector>#include<cmath>using namespace std;struct nodeint a33; /存放矩陣int father; /父節(jié)點的位置 int gone; /是否遍歷過,1為是,0為否int fn; /評價函數(shù)的值int x,y; /空格的坐標(biāo)int deep;

21、/節(jié)點深度 ;vector<node> store; /存放路徑節(jié)點int mx4=-1,0,1,0;int my4=0,-1,0,1; /上下左右移動數(shù)組int top; /當(dāng)前節(jié)點在store中的位置bool check(int num) /判斷storenum節(jié)點與目標(biāo)節(jié)點是否相同,目標(biāo)節(jié)點儲存在store0中 for(int i=0;i<3;i+)for(int j=0;j<3;j+)if(storenum.aij!=store0.aij)return false;return true; bool search(int num) /判斷storenum節(jié)點是否

22、已經(jīng)擴展過 ,沒有擴展返回true int pre=storenum.father; /pre指向storenum的父節(jié)點位置 bool test=true;while(!pre) /循環(huán)直到pre為0,既初始節(jié)點 for(int i=0;i<3;i+)for (int j=0;j<3;j+)if(storepre.aij!=storenum.aij)test=false;break;if(test=false) break;if(test=true) return false;pre=storepre.father; /pre繼續(xù)指向storepre父節(jié)點位置 return tr

23、ue;void print(int num) /打印路徑,storenum為目標(biāo)節(jié)點 vector<int> temp; /存放路徑 int pre=storenum.father;temp.push_back(num);while(pre!=0) /從目標(biāo)節(jié)點回溯到初始節(jié)點 temp.push_back(pre);pre=storepre.father;cout<<endl;cout<<"*數(shù)碼移動步驟*"<<endl; int mm=1; /步數(shù)for(int m=temp.size()-1;m>=0;m-)cout

24、<<"-第"<<mm<<"步-："<<endl;for(int i=0;i<3;i+)for(int j=0;j<3;j+)cout<<storetempm.aij<<" "cout<<endl;mm+;cout<<endl;cout<<"所需步數(shù)為: "<<storenum.deep<<endl; return;int get_fn(int num) /返回storenu

25、m的評價函數(shù)值 int fn_temp=0; /評價函數(shù)值 bool test=true;for(int i=0;i<3;i+) /當(dāng)找到一個值后,計算這個值位置與目標(biāo)位置的距離差,test置為false后繼續(xù)尋找下一個值 for(int j=0;j<3;j+)test=true;for(int k=0;k<3;k+)for(int l=0;l<3;l+)if(storenum.x!=i|storenum.y!=j)&&storenum.aij=store0.akl) /尋值時排除空格位 fn_temp=fn_temp+abs(i-k)+abs(j-l)

26、;test=false;if(test=false) break;if(test=false) break;fn_temp=fn_temp+storenum.deep; /加上節(jié)點深度 return fn_temp;void kongxy(int num) /獲得空格坐標(biāo) for(int i=0;i<3;i+)for(int j=0;j<3;j+)if(storenum.aij=0)storenum.x=i;storenum.y=j;return;int main()cout<<"-A*算法解決8數(shù)碼問題-"<<endl;while(tr

27、ue)store.clear(); /清空store vector<int> open; /建立open表 int i,j,m,n,f;int min; /storemin儲存fn值最小的節(jié)點 int temp;bool test;top=1; /當(dāng)前節(jié)點在store的位置,初始節(jié)點在store1 int target9; int begin9; /儲存初始狀態(tài)和目標(biāo)狀態(tài),用于判斷奇偶 int t1=0,t2=0; /初始狀態(tài)和目標(biāo)狀態(tài)的奇偶序數(shù) node node_temp; store.push_back(node_temp);store.push_back(node_temp

28、); /用于創(chuàng)建store0和store1,以便下面使用 cout<<"請輸入初始數(shù)碼棋盤狀態(tài),0代表空格："<<endl; /輸入初始狀態(tài),儲存在store1中 test=false;while(test=false)f=0;for(i=0;i<3;i+)for(j=0;j<3;j+)cin>>temp;store1.aij=temp;beginf+=temp;test=true;for(i=0;i<8;i+) /檢查是否有重復(fù)輸入,若有則重新輸入 for(j=i+1;j<9;j+)if(begini=begin

29、j)test=false;break; if(test=false) break;if(test=false) cout<<"輸入重復(fù),請重新輸入:"<<endl; kongxy(1); /找出空格的坐標(biāo) cout<<"請輸入目標(biāo)數(shù)碼棋盤狀態(tài),0代表空格： "<<endl; /輸入目標(biāo)狀態(tài),儲存在store0中 test=false;while(test=false)f=0;for(i=0;i<3;i+)for(j=0;j<3;j+)cin>>temp;store0.aij=temp

30、;targetf+=temp;test=true;for(i=0;i<8;i+) /檢查是否有重復(fù)輸入,若有則重新輸入 for(j=i+1;j<9;j+)if(targeti=targetj)test=false;break; if(test=false) break;if(test=false)cout<<"輸入重復(fù),請重新輸入:"<<endl;continue; /若重復(fù),重新輸入 for(i=0;i<9;i+) /檢查目標(biāo)狀態(tài)與初始狀態(tài)是否匹配 test=false;for(j=0;j<9;j+)if(begini=ta

31、rgetj)test=true;break; if(test=false) break;if(test=false) cout<<"輸入與初始狀態(tài)不匹配,請重新輸入:"<<endl; for(i=1;i<9;i+) /判斷奇偶序數(shù)是否相同,若不相同則無法找到路徑 for(j=1;i-j>=0;j+)if(begini>begini-j)if(begini-j!=0) t1+;for(i=1;i<9;i+)for(j=1;i-j>=0;j+)if(targeti>targeti-j)if(targeti-j!=0)

32、t2+;if(!(t1%2=t2%2)cout<<"無法找到路徑."<<endl;cout<<endl;/system("pause");/return 0;continue;LARGE_INTEGER Freg;LARGE_INTEGER Count1,Count2;QueryPerformanceFrequency(&Freg);QueryPerformanceCounter(&Count1);/獲取時間Count1double d;store1.father=0; /初始化參數(shù) store1.go

33、ne=0;store1.deep=0; /初始節(jié)點的父節(jié)點為0 store1.fn=get_fn(1);if(check(1) /判斷初始狀態(tài)與目標(biāo)狀態(tài)是否相同 print(1);/system("pause");/return 0;cout<<endl;continue;open.push_back(1); /把初始狀態(tài)在store中的位置數(shù)壓入open表中 while(!open.empty() /當(dāng)open表不為空時,開始尋找路徑 if(check(top) break;min=top;int i_min=0;for(i=0;i<open.size();i+) /遍歷open表中元素,找出store中fn值最小