八数码宽度优先搜索

1、精选优质文档-倾情为你奉上/*程序利用C+程序设计语言，在VC6.0下采用宽度优先的搜索方式，成功的解决了八数码问题。程序中把OPEN表和CLOSED表用队列的方式存储，大大地提高了效率，开始的时候要输入目标状态和起始状态，由于在宽度优先搜索的情况下，搜索过程中所走过的状态是不确定且很庞大的，所以程序最后输出宽度优先情况下最少步数的搜索过程以及程序运行所需要的时间*/#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;/数码数组 Direction BelockDirec;/所屏蔽方向 struct Map * Parent;/父节点;/打印图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;/移动图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; /移动数字 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)/不可以移动则返回原节点 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) /数码是否可以移动 p2->Parent = p1;switch(Direct)/设置屏蔽方向,防止往回推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) /将八数码转换成一个数列，并计算其逆序数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<<"请输入八数码的目标状态(用0代替空格):"<<endl;/输入目标状态for (i=0;i<9;i+) /此for循环用来把输入的数存入到target

11、数组中flag=0;cin>>targeti;for(j=0;j<i;j+)if(targeti=targetj) flag=1;if (targeti<0|targeti>8|flag=1) /判断输入是否正确i-;cout<<"输入错误，请关闭重新运行!n" int k=0;for (m=0;m<3;m+) /把数组target中的数传给图Targetfor (n=0;n<3;n+) Target.cellmn=targetk;k+; /输入起始状态cout<<"请输入八数码的起始状态(用0代替

12、空格):"<<endl;for (i=0;i<9;i+) flag=0;cin>>targeti;for(j=0;j<i;j+)if(targeti=targetj) /判断输入的数是否正确flag=1;if (targeti<0|targeti>8|flag=1)i-;cout<<"输入错误，请关闭重新运行!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<<"目标图:"<<endl; PrintMap(&Target); cout<<"起始图:"<<endl; PrintMap(begin);a1=Jou(&Target);a2=Jou(begin); if(a1!=a2)cout<<"无解"<<endl; exit(0); /无解的话就退出，重新运行 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<<"宽度优先最少步数的搜索过程为:"<<endl; while(!Stack1.empty() PrintMap(Stack1.top(); c+; Stack1.pop(); cout<