《八数码宽度优先搜索》由会员分享，可在线阅读，更多相关《八数码宽度优先搜索（8页珍藏版）》请在金锄头文库上搜索。
1、/*程序利用C+程序设计语言，在VC6.0下采用宽度优先的搜索方式，成功的解决了八数码问题。程序中把OPEN表和CLOSED表用队列的方式存储，大大地提高了效率，开始的时候要输入目标状态和起始状态，由于在宽度优先搜索的情况下，搜索过程中所走过的状态是不确定且很庞大的，所以程序最后输出宽度优先情况下最少步数的搜索过程以及程序运行所需要的时间*/#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;/数码数组 Direction BelockDirec;/所屏蔽方向 struct Map * Parent;/父节点;/打印图void PrintMap(struct Map *map) cout*endl; for(int i=0;iN;i+) for(int j=0;jN;j+) coutcellij ; coutendl; cout*endl;/移动图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; /移动数字 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)/不可以移动则返回原节点 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)/跳过屏蔽方向 continue; p2 = MoveMap(p1,Direct,true); if(p2 != p1) /数码是否可以移动 p2
7、-Parent = p1;switch(Direct)/设置屏蔽方向,防止往回推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) /将八数码转换成一个数列，并计算其逆序数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请输入八数码的目标状态(用0代替空格):endl;/输入目标状态fo
9、r (i=0;itargeti;for(j=0;ji;j+)if(targeti=targetj) flag=1;if (targeti8|flag=1) /判断输入是否正确i-;cout输入错误，请关闭重新运行!n; int k=0;for (m=0;m3;m+) /把数组target中的数传给图Targetfor (n=0;n3;n+) Target.cellmn=targetk;k+; /输入起始状态cout请输入八数码的起始状态(用0代替空格):endl;for (i=0;itargeti;for(j=0;ji;j+)if(targeti=targetj) /判断输入的数是否正确flag=1;if (targeti8|flag=1)i-;cout输入错误，请关闭重新运行!n;k=0;for (m=0;m3;m+)for (n=0;ncellmn=targetk;k+; begin-Parent = NULL; begin-BelockDirec = None; cout目标图:endl; PrintMap(&Target); cout起始图:endl; PrintMap(begin)
