1、#inelude <iostream>#inelude <time.h>#include <windows.h>#inelude <veetor>#inelude <emath> using namespaeestd;veetor <no de> store;/存放路徑節點struet no deinta33;/存放矩陣intfather;/父節點的位置intgone;/是否遍歷過,1為是,0為否intfn；/評價函數的值intx,y;/空格的坐標intdeep;/節點深度；int mx4=-1,0,1,0;int my4

2、=0,-1,0,1;/上下左右移動數組int top;/當前節點在store中的位置bool eheek( int num)/判斷storenum節點與目標節點是否相同，目標節點儲存在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 seareh( int num)/判斷storenum節點是否已經擴展過，沒有擴展返回trueint pre=storenum.father;/pre 指向 storenum的父節點位置b

3、ool test= true ;while (!pre)/循環直到pre為0,既初始節點for (int i=0;i<3;i+)for ( int j=0;j<3;j+)if (storepre.aij!=storenum.aij)test= falsebreak;if (test= false ) break;/pre繼續指向storepre父節點位置if (test= true ) return false pre=storepre.father;return true ;*“void print( int num)vectorv int > temp;int pre=s

4、torenum.father; temp.push_back (n um);while (pre!=0) temp.push_back(pre); pre=storepre.father;cout«e ndl;coutvv "* 數碼移動步驟 int mm=1; / 步數/打印路徑,storenum為目標節點/存放路徑/從目標節點回溯到初始節點<<e ndl;for (int m=temp.size()_1;m>=0;m_)cout«"- 第"<<mm<<- : "<<endl;f

5、or (int i=0;i<3;i+)for (int j=0;j<3;j+) cout<<storetempm.aij<<cout«e ndl;mm+;cout«e ndl;coutvv"所需步數為："<<storenum.deep<<endl; return ;int get_fn( int num)int fn_temp=0; bool test= true ;for (int i=0;i<3;i+)/返回storenum的評價函數值/評價函數值/當找到一個值后，計算這個值位置與目標

6、位置的距離差，test置為false后繼續尋找下一個值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=f n_temp+abs(i-k)+abs(j-l);test= false ;if (test= false ) break;if (test= false ) break;fn_temp=fn_temp+stor

7、enum.deep;/ 加上節點深度return fn_temp;/void kongxy( int num)for (int i=0;i<3;i+)/獲得空格坐標for (int j=0;j<3;j+)if (storenum.aij=0)store n um.x=i;store n um.y=j; returnint main()cout«"A*算法解決8數碼問題"<<endl;while (true )store.clear(); vector< int > open; int i,j,m,n,f;int min;int

8、temp;/ 清空 store/ 建立 open表storemin儲存fn值最小的節點bool test;top=1;/當前節點在store的位置，初始節點在store1int target9;int begin9;/儲存初始狀態和目標狀態，用于判斷奇偶int t1=0,t2=0;/初始狀態和目標狀態的奇偶序數node no de_temp;store.push_back (no de_temp);store.push_back(node_temp);/ 用于創建 store0和 store1, 以便下面使用coutvv"請輸入初始數碼棋盤狀態,0代表空格："<<

9、;endl; /輸入初始狀態，儲存在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;begi n f+=temp;test= true ;for (i=0;i<8;i+)/檢查是否有重復輸入，若有則重新輸入for (j=i+1;j<9;j+)if (begini=beginj)test= false ;break;if (test= false ) break;if (test= false ) co

10、ut<< "輸入重復,請重新輸入:"<<endl;kongxy(1);/找岀空格的坐標coutvv"請輸入目標數碼棋盤狀態,0代表空格："<<endl; /輸入目標狀態，儲存在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;targetf+=temp;test= true ;for (i=0;i<8;i+)/檢查是否有重復輸入，若有則重

11、新輸入for (j=i+1;j<9;j+)if (targeti=targetj)test= false ;break;if (test= false ) break;if (test= false )cout«"輸入重復，請重新輸入:"<<endl;continue ;/若重復,重新輸入for (i=0;i<9;i+)/檢查目標狀態與初始狀態是否匹配test= false ;for (j=0;j<9;j+)if (begini=targetj)test= true ;break;if (test= false ) break;if

12、(test= false ) cout<< "輸入與初始狀態不匹配，請重新輸入:"<<endl; for (i=1;i<9;i+)/判斷奇偶序數是否相同，若不相同則無法找到路徑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) t2+;if (!(t1%2=t2%2)cout«"無

13、法找到路徑."<<endl;cout«e ndl;system("pause");/return 0;continue ;LARGEN TEGER Freg;LARGEN TEGER Cou nt1,Cou nt2;QueryPerforma nceFreque ncy(&Freg);QueryPerformanceCounter(&Count1);/ 獲取時間 Count1double d;store1.father=0; store1.go ne=0; store1.deep=0; store1.fn=get_f n (1

14、);/初始化參數/初始節點的父節點為0if (check(1)prin t(1); system("pause");/return 0; cout«e ndl;continue ;/判斷初始狀態與目標狀態是否相同ope n.push_back(1);/把初始狀態在store中的位置數壓入open表中while (!open.empty()/當open表不為空時,開始尋找路徑if (check(top) break;mi n=top;int i_min=0;for (i=0;i<open.size();i+)/遍歷open表中元素，找岀store中fn值最小的

15、節占八、if (storeopeni.fn<=storemin.fn&&storeopeni.gone=0)min=ope ni; i_mi n=i;store min .go ne=1;ope n.erase(ope n.begi n()+i_mi n);/把最小節點標記遍歷過，并從open表中刪除m=store min .x; n=storemi n.y;/空格坐標for (f=0;f<4;f+) i=m+mxf; j=n+myf;/上下左右移動空格移動if (i>=0&&i<=2&&j>=0&&

16、j<=2)/當變換后的空格坐標在矩陣中時，開始top+;store.push_back(store min );節點，位置為storetopstoretop.father=mi n;storetop.g on e=0;storetop.deep=storemi n.deep+1;/+1把storemin壓入store中成為新增新增節點的父節點為min新增節點未被訪問/新增節點的深度為父節點深度temp=storetop.am n;storetop.am n=storetop.aij;storetop.aij=temp;/交換空格與相鄰數字storetop.x=i;storetop.y=j;storetop.f n=get_f n( top);/移動后的空格坐標移動后的fn值ope n.push_back(top); if (check(top)/把top壓入open表中檢查是否到達目標pr in t(top);system("pause");/return 0;break;if (search(top)= false )/檢查新增節點是否被訪問過，若訪問過，則刪除此節點top-;store.pop_back();ope n.pop_back();Query