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

2、=0,-1,0,1;/上下左右移動(dòng)數(shù)組int top;/當(dāng)前節(jié)點(diǎn)在store中的位置bool eheek( int num)/判斷storenum節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)是否相同，目標(biāo)節(jié)點(diǎn)儲(chǔ)存在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節(jié)點(diǎn)是否已經(jīng)擴(kuò)展過，沒有擴(kuò)展返回trueint pre=storenum.father;/pre 指向 storenum的父節(jié)點(diǎn)位置b

3、ool test= true ;while (!pre)/循環(huán)直到pre為0,既初始節(jié)點(diǎn)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繼續(xù)指向storepre父節(jié)點(diǎn)位置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 "* 數(shù)碼移動(dòng)步驟 int mm=1; / 步數(shù)/打印路徑,storenum為目標(biāo)節(jié)點(diǎn)/存放路徑/從目標(biāo)節(jié)點(diǎn)回溯到初始節(jié)點(diǎn)<<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"所需步數(shù)為："<<storenum.deep<<endl; return ;int get_fn( int num)int fn_temp=0; bool test= true ;for (int i=0;i<3;i+)/返回storenum的評(píng)價(jià)函數(shù)值/評(píng)價(jià)函數(shù)值/當(dāng)找到一個(gè)值后，計(jì)算這個(gè)值位置與目標(biāo)

6、位置的距離差，test置為false后繼續(xù)尋找下一個(gè)值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) 尋值時(shí)排除空格位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;/ 加上節(jié)點(diǎn)深度return fn_temp;/void kongxy( int num)for (int i=0;i<3;i+)/獲得空格坐標(biāo)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數(shù)碼問題"<<endl;while (true )store.clear(); vector< int > open; int i,j,m,n,f;int min;int

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

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

10、ut<< "輸入重復(fù),請(qǐng)重新輸入:"<<endl;kongxy(1);/找岀空格的坐標(biāo)coutvv"請(qǐng)輸入目標(biāo)數(shù)碼棋盤狀態(tài),0代表空格："<<endl; /輸入目標(biāo)狀態(tài)，儲(chǔ)存在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+)/檢查是否有重復(fù)輸入，若有則重

11、新輸入for (j=i+1;j<9;j+)if (targeti=targetj)test= false ;break;if (test= false ) break;if (test= false )cout«"輸入重復(fù)，請(qǐng)重新輸入:"<<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=targetj)test= true ;break;if (test= false ) break;if

12、(test= false ) cout<< "輸入與初始狀態(tài)不匹配，請(qǐng)重新輸入:"<<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) 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);/ 獲取時(shí)間 Count1double d;store1.father=0; store1.go ne=0; store1.deep=0; store1.fn=get_f n (1

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

15、節(jié)占八、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);/把最小節(jié)點(diǎn)標(biāo)記遍歷過，并從open表中刪除m=store min .x; n=storemi n.y;/空格坐標(biāo)for (f=0;f<4;f+) i=m+mxf; j=n+myf;/上下左右移動(dòng)空格移動(dòng)if (i>=0&&i<=2&&j>=0&&

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