八數(shù)碼C語言知識(shí)學(xué)習(xí)A算法詳細(xì)代碼

1、#include #include #include #include #include using namespace std;struct nodeint a33;int father;int gone;int fn;int x,y;int deep;vector store;int mx4=-1,0,1,0;int my4=0,-1,0,1;/ 存放矩陣/ 父節(jié)點(diǎn)的位置/ 是否遍歷過 ,1為是 ,0 為否/ 評(píng)價(jià)函數(shù)的值/ 空格的坐標(biāo)/ 節(jié)點(diǎn)深度/ 存放路徑節(jié)點(diǎn)/ 上下左右移動(dòng)數(shù)組bool check( int num) / 判斷 storenum 節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)是否相同 ,目標(biāo)節(jié)點(diǎn)儲(chǔ)存

2、在 store0 中for (int i=0;i3;i+)for (int j=0;j3;j+)if (storenum.aij!=store0.aij)return false ;return true ;bool search( int num)/ 判斷 storenum 節(jié)點(diǎn)是否已經(jīng)擴(kuò)展過 ,沒有擴(kuò)展返回 true/pre 指向 storenum 的父節(jié)點(diǎn)位置/ 循環(huán)直到 pre 為 0,既初始節(jié)點(diǎn)int pre=storenum.father;bool test= true ;while (!pre)for (int i=0;i3;i+)for (int j=0;j3;j+)if(st

3、orepre.aij!=storenum.aij)test= false ;break ;if (test= false ) break ;if(test= true ) return false ;/pre 繼續(xù)指向 storepre 父節(jié)點(diǎn)位置pre=storepre.father;return true ;void print( int num)vector temp;int pre=storenum.father; temp.push_back(num);while (pre!=0)temp.push_back(pre);/ 打印路徑 ,storenum 為目標(biāo)節(jié)點(diǎn)/ 存放路徑/ 從目

4、標(biāo)節(jié)點(diǎn)回溯到初始節(jié)點(diǎn)pre=storepre.father;coutendl;cout數(shù)碼移動(dòng)步驟 *=0;m-)cout - 第 mm 步 - ：endl;for (int i=0;i3;i+)for (int j=0;j3;j+)coutstoretempm.aijcoutendl;mm+;coutendl;cout 所需步數(shù)為 : storenum.deependl;return ;int get_fn( int num)/ 返回 storenum 的評(píng)價(jià)函數(shù)值int fn_temp=0;/ 評(píng)價(jià)函數(shù)值bool test= true ;for (int i=0;i3;i+)/ 當(dāng)找到一個(gè)

5、值后 ,計(jì)算這個(gè)值位置與目標(biāo)位置的距離差 ,test 置為 false 后繼續(xù)尋找下一個(gè)值for (int j=0;j3;j+)test= true ;for (int k=0;k3;k+)for (int l=0;l3;l+)/ 尋值時(shí)if (storenum.x!=i|storenum.y!=j)&storenum.aij=store0.akl) 排除空格位fn_temp=fn_temp+abs(i-k)+abs(j-l);test= false ;if (test= false ) break ;if(test= false ) break ;fn_temp=fn_temp+storen

6、um.deep; / 加上節(jié)點(diǎn)深度return fn_temp;for (int i=0;i3;i+)for (int j=0;j3;j+)if (storenum.aij=0)storenum.x=i;storenum.y=j;intreturn ;main()cout A* 算法解決 8數(shù)碼問題 endl;while (true )store.clear();/ 清空 storevector open;/ 建立 open 表int i,j,m,n,f;int temp;bool test;top=1;/ 當(dāng)前節(jié)點(diǎn)在 store 的位置 ,初始節(jié)點(diǎn)在 store1int target9;in

7、t begin9;/ 儲(chǔ)存初始狀態(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); / 用于創(chuàng)建 store0 和 store1, 以便下面使用cout 請(qǐng)輸入初始數(shù)碼棋盤狀態(tài) ,0 代表空格： endl; / 輸入初始狀態(tài) ,儲(chǔ)存在 store1test= false ;while (test= false )f=0;for (i=0;i3;i+)for (j=0;jtemp;beginf+=temp;test= tr

8、ue ;for (i=0;i8;i+) / 檢查是否有重復(fù)輸入 ,若有則重新輸入for (j=i+1;j9;j+)if (begini=beginj)test= false ;break ;if(test= false ) break ;if (test= false ) cout 輸入重復(fù) ,請(qǐng)重新輸入 :endl;kongxy(1); / 找出空格的坐標(biāo)cout 請(qǐng)輸入目標(biāo)數(shù)碼棋盤狀態(tài) ,0 代表空格： endl; / 輸入目標(biāo)狀態(tài) ,儲(chǔ)存在 test= false ;while (test= false )f=0;for (i=0;i3;i+)for (j=0;jtemp;store0.

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

10、 false ) break ;if (test= false ) cout 輸入與初始狀態(tài)不匹配 ,請(qǐng)重新輸入 : endl; for (i=1;i=0;j+)if(beginibegini-j)if (begini-j!=0) t1+;for (i=1;i=0;j+)if(targetitargeti-j)if (targeti-j!=0) t2+;if(!(t1%2=t2%2)cout 無法找到路徑 .endl;coutendl;/system(pause);/return 0;continue ;LARGE_INTEGER Freg;LARGE_INTEGER Count1,Count

11、2;QueryPerformanceFrequency(&Freg);QueryPerformanceCounter(&Count1);double d;/ 獲取時(shí)間 Count1store1.father=0;store1.gone=0;store1.deep=0;store1.fn=get_fn(1);/ 初始化參數(shù)/ 初始節(jié)點(diǎn)的父節(jié)點(diǎn)為 0if(check(1) / 判斷初始狀態(tài)與目標(biāo)狀態(tài)是否相同 print(1);/system(pause);/return 0;coutendl;continue ;while (!open.empty() / 當(dāng) open 表不為空時(shí) ,開始尋找路徑

12、if (check(top) break ;min=top;int i_min=0;for (i=0;iopen.size();i+)/遍歷open表中元素，找岀store中fn值最小的節(jié)點(diǎn)if(storeopeni.fn=storemin.fn&storeopeni.gone=0)min=openi;i_min=i;storemin.gone=1;open.erase(open.begin()+i_min);/把最小節(jié)點(diǎn)標(biāo)記遍歷過 并從open表中刪除m=storemin.x;n=storemin.y;/空格坐標(biāo)for (f=0;f=0&i=0&j=2)top+;store.push_bac

13、k(storemin);storetop.father=min;storetop.gone=0;storetop.deep=storemin.deep+1;/ 當(dāng)變換后的空格坐標(biāo)在矩陣中時(shí)/ 把 storemin 壓入 store 中成為新增節(jié)/ 新增節(jié)點(diǎn)的父節(jié)點(diǎn)為 min/ 新增節(jié)點(diǎn)未被訪問/ 新增節(jié)點(diǎn)的深度為父節(jié)點(diǎn)深度temp=storetop.amn;storetop.amn=storetop.aij;storetop.aij=temp;storetop.x=i;storetop.y=j;storetop.fn=get_fn(top);open.push_back(top);if (check(top)print(top);/ 交換空格與相鄰數(shù)字/ 移動(dòng)后的空格坐標(biāo)/ 移動(dòng)后的 fn 值/把top壓入open表中/ 檢查是否到達(dá)目標(biāo)/system(pause);/return 0;break ;if (search(top)= false ) / 檢查新增節(jié)點(diǎn)是否被訪問過 ,若訪問過 ,則刪 除此節(jié)點(diǎn)top-;store.pop_back();ope