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

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

2、nclude "string.h"#include <queue>#include <stack>using namespace std;const int 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

3、) cout<<"*"<<endl; for(int i=0;i<N;i+) for(int j=0;j<N;j+) cout<<map->cellij<<" " cout<<endl; cout<<"*"<<endl;/移動(dòng)圖struct Map * MoveMap(struct Map * map,Direction Direct,bool CreateNewMap) struct Map * NewMap; /獲取空閑格位置 i

4、nt i,j; for(i = 0; i < N; i+) bool HasGetBlankCell = false; for(j = 0; j < N; j+) if(map->cellij = 0) HasGetBlankCell = true; break; if(HasGetBlankCell) break; /移動(dòng)數(shù)字 int t_i = i,t_j = j; bool AbleMove = true; switch(Direct) case Down: t_i+; if(t_i >= N) AbleMove=false; break; case Up: t_

5、i-; if(t_i < 0) AbleMove=false; break; case Left: t_j-; if(t_j < 0) AbleMove=false; break; case Right: 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 < N; y+) NewMap->

6、cellxy = map->cellxy; else NewMap = 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 < N; j+) if(map->cellij != Target->cellij) Is

7、Suc = false; break; if(!IsSuc) break; return IsSuc;struct Map * BNF_Search(struct Map * begin,struct Map * Target) struct Map * p1, *p2, *p=NULL; bool IsSucc = false; queue<struct Map *> Queue; if(IsSuccess(begin,Target) return begin; Queue.push(begin); do p1 = Queue.front(); Queue.pop(); for

8、(int i = 1; i <= 4; i+) Direction Direct=(Direction)i; if(Direct = p1->BelockDirec)/跳過屏蔽方向 continue; p2 = MoveMap(p1,Direct,true); if(p2 != p1) /數(shù)碼是否可以移動(dòng) p2->Parent = p1;switch(Direct)/設(shè)置屏蔽方向,防止往回推case Up: p2->BelockDirec = Down; break;case Down: p2->BelockDirec = Up; break;case Left:

9、 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 p;int Jou(struct Map *map) /將八數(shù)碼轉(zhuǎn)換成一個(gè)數(shù)列，并計(jì)算其逆序數(shù)int a=0;char b9;for(int i=0;i<N;i+)for(int j=0;j<N;j+)bi*3+j=map-

10、>cellij;for(int k=0;k<9;k+)for(int h=0;h<k;h+)if(bh<bk)&&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)for (i=0;i<9;i+) /此for循環(huán)用來把輸入的數(shù)存入到target

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

12、空格):"<<endl;for (i=0;i<9;i+) flag=0;cin>>targeti;for(j=0;j<i;j+)if(targeti=targetj) /判斷輸入的數(shù)是否正確flag=1;if (targeti<0|targeti>8|flag=1)i-;cout<<"輸入錯(cuò)誤，請(qǐng)關(guān)閉重新運(yùn)行!n"k=0;for (m=0;m<3;m+)for (n=0;n<3;n+) begin->cellmn=targetk;k+; begin->Parent = NULL;

13、begin->BelockDirec = None; cout<<"目標(biāo)圖:"<<endl; PrintMap(&Target); cout<<"起始圖:"<<endl; PrintMap(begin);a1=Jou(&Target);a2=Jou(begin); if(a1!=a2)cout<<"無解"<<endl; exit(0); /無解的話就退出，重新運(yùn)行 else double start=clock(); cout<<

14、"有解"<<endl; /圖搜索 T=BNF_Search(begin,&Target); /打印 if(T != NULL) /把路徑倒序 Map *p=T; stack<Map *> Stack1; while(p->Parent != NULL) Stack1.push(p); p = p->Parent; cout<<"寬度優(yōu)先最少步數(shù)的搜索過程為:"<<endl; while(!Stack1.empty() PrintMap(Stack1.top(); c+; Stack1.pop(); cout<