八數(shù)碼寬度優(yōu)先搜索

1、/*程序利用C+程序設(shè)計(jì)語(yǔ)言，在VC6.0下采用寬度優(yōu)先的搜索方式，成功的解決了八數(shù)碼問(wèn)題。程序中把OPEN表和CLOSED表用隊(duì)列的方式存儲(chǔ)，大大地提高了效率，開(kāi)始的時(shí)候要輸入目標(biāo)狀態(tài)和起始狀態(tài)，由于在寬度優(yōu)先搜索的情況下，搜索過(guò)程中所走過(guò)的狀態(tài)是不確定且很龐大的，所以程序最后輸出寬度優(yōu)先情況下最少步數(shù)的搜索過(guò)程以及程序運(yùn)行所需要的時(shí)間*/#include iostream#include stdio.h#include stdlib.h#include time.h#include string.h#include #include using namespace std;const in

2、t N = 3;/3*3圖enum DirectionNone,Up,Down,Left,Right;/方向static int n=0;static int c=0;struct Map/圖 int cellNN;/數(shù)碼數(shù)組 Direction BelockDirec;/所屏蔽方向 struct Map * Parent;/父節(jié)點(diǎn);/打印圖void PrintMap(struct Map *map) cout*endl; for(int i=0;iN;i+) for(int j=0;jN;j+) coutcellij ; coutendl; cout*endl;/移動(dòng)圖struct Map

3、* MoveMap(struct Map * map,Direction Direct,bool CreateNewMap) struct Map * NewMap; /獲取空閑格位置 int i,j; for(i = 0; i N; i+) bool HasGetBlankCell = false; for(j = 0; j cellij = 0) HasGetBlankCell = true; break; if(HasGetBlankCell) break; /移動(dòng)數(shù)字 int t_i = i,t_j = j; bool AbleMove = true; switch(Direct) c

4、ase Down: t_i+; if(t_i = N) AbleMove=false; break; case Up: t_i-; if(t_i 0) AbleMove=false; break; case Left: t_j-; if(t_j = N) AbleMove=false; break; ; if(!AbleMove)/不可以移動(dòng)則返回原節(jié)點(diǎn) return map; if(CreateNewMap) NewMap = new Map(); for(int x = 0; x N; x+) for(int y = 0; y cellxy = map-cellxy; else NewMa

5、p = map; NewMap-cellij = NewMap-cellt_it_j; NewMap-cellt_it_j = 0; return NewMap;bool IsSuccess(struct Map * map,struct Map * Target) bool IsSuc = true; for(int i = 0; i N; i+) for(int j = 0; j cellij != Target-cellij) IsSuc = false; break; if(!IsSuc) break; return IsSuc;struct Map * BNF_Search(stru

6、ct Map * begin,struct Map * Target) struct Map * p1, *p2, *p=NULL; bool IsSucc = false; queue Queue; if(IsSuccess(begin,Target) return begin; Queue.push(begin); do p1 = Queue.front(); Queue.pop(); for (int i = 1; i BelockDirec)/跳過(guò)屏蔽方向 continue; p2 = MoveMap(p1,Direct,true); if(p2 != p1) /數(shù)碼是否可以移動(dòng) p2

7、-Parent = p1;switch(Direct)/設(shè)置屏蔽方向,防止往回推case Up: p2-BelockDirec = Down; break;case Down: p2-BelockDirec = Up; break;case Left: p2-BelockDirec = Right; break;case Right: p2-BelockDirec = Left; break;if (IsSuccess(p2,Target) p = p2; return p;Queue.push(p2);n+; while(!Queue.empty() | p = NULL); return

8、p;int Jou(struct Map *map) /將八數(shù)碼轉(zhuǎn)換成一個(gè)數(shù)列，并計(jì)算其逆序數(shù)int a=0;char b9;for(int i=0;iN;i+)for(int j=0;jcellij;for(int k=0;k9;k+)for(int h=0;hk;h+)if(bhbk)&bh!=0)a+;return a%2;int main()int a1,a2;int i,j,m,n;int target9;int flag; Map Target; Map *begin,*T; begin=new Map; cout請(qǐng)輸入八數(shù)碼的目標(biāo)狀態(tài)(用0代替空格):endl;/輸入目標(biāo)狀態(tài)fo

9、r (i=0;itargeti;for(j=0;ji;j+)if(targeti=targetj) flag=1;if (targeti8|flag=1) /判斷輸入是否正確i-;cout輸入錯(cuò)誤，請(qǐng)關(guān)閉重新運(yùn)行!n; int k=0;for (m=0;m3;m+) /把數(shù)組target中的數(shù)傳給圖Targetfor (n=0;n3;n+) Target.cellmn=targetk;k+; /輸入起始狀態(tài)cout請(qǐng)輸入八數(shù)碼的起始狀態(tài)(用0代替空格):endl;for (i=0;itargeti;for(j=0;ji;j+)if(targeti=targetj) /判斷輸入的數(shù)是否正確fla

10、g=1;if (targeti8|flag=1)i-;cout輸入錯(cuò)誤，請(qǐng)關(guān)閉重新運(yùn)行!n;k=0;for (m=0;m3;m+)for (n=0;ncellmn=targetk;k+; begin-Parent = NULL; begin-BelockDirec = None; cout目標(biāo)圖:endl; PrintMap(&Target); cout起始圖:endl; PrintMap(begin);a1=Jou(&Target);a2=Jou(begin); if(a1!=a2)cout無(wú)解endl; exit(0); /無(wú)解的話就退出，重新運(yùn)行 else double start=clock(); cout有解endl; /圖搜索 T=BNF_Search(begin,&Target); /打印 if(T != NULL) /把路徑倒序 Map *p=T; stack Stack1; while(p-Parent != NULL) Stack1.push(p); p = p-Parent; cout寬度優(yōu)先最少步數(shù)的搜索過(guò)程為:en