八数码宽度优先搜索.docx

《八数码宽度优先搜索.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、/*程序利用C++程序设计语言，在VC6.0下采用宽度优先的搜索方式，成功的解决了八数码问题。程序中把OPEN表和CLOSED表用队列的方式存储，大大地提高了效率，开始的时候要输入目标状态和起始状态，由于在宽度优先搜索的情况下，搜索过程中所走过的状态是不确定且很庞大的，所以程序最后输出宽度优先情况下最少步数的搜索过程以及程序运行所需要的时间*/#include"iostream"#include"stdio.h"#include"stdlib.h"#include"time.h"#include"string.h"#include#include

2、usingnamespacestd;constintN=3;//3*3图enumDirection{None,Up,Down,Left,Right};//方向staticintn=0;staticintc=0;structMap//图{intcell[N][N];//数码数组DirectionBelockDirec;//所屏蔽方向structMap*Parent;//父节点};//打印图voidPrintMap(structMap*map){cout<<"**********************************************

3、***"<cell[i][j]<<"";}cout<

4、GetBlankCell=false;for(j=0;jcell[i][j]==0){HasGetBlankCell=true;break;}}if(HasGetBlankCell)break;}//移动数字intt_i=i,t_j=j;boolAbleMove=true;switch(Direct){caseDown:t_i++;if(t_i>=N)AbleMove=false;break;caseUp:t_i--;if(t_i<0)AbleMove=false;break;caseLeft:t_j--;if(t_j<0)Ab

5、leMove=false;break;caseRight:t_j++;if(t_j>=N)AbleMove=false;break;};if(!AbleMove)//不可以移动则返回原节点{returnmap;}if(CreateNewMap){NewMap=newMap();for(intx=0;xcell[x][y]=map->cell[x][y];}elseNewMap=map;NewMap->cell[i][j]=NewMap->cell[t_i][t_j];NewMap->cell[

6、t_i][t_j]=0;returnNewMap;}boolIsSuccess(structMap*map,structMap*Target){boolIsSuc=true;for(inti=0;icell[i][j]!=Target->cell[i][j]){IsSuc=false;break;}}if(!IsSuc)break;}returnIsSuc;}structMap*BNF_Search(structMap*begin,structMap*Target){structMap*p

7、1,*p2,*p=NULL;boolIsSucc=false;queueQueue;if(IsSuccess(begin,Target))returnbegin;Queue.push(begin);do{p1=Queue.front();Queue.pop();for(inti=1;i<=4;i++){DirectionDirect=(Direction)i;if(Direct==p1->BelockDirec)//跳过屏蔽方向continue;p2=MoveMap(p1,Direct,true);if(p2!=p1)//数码是否可以移

8、动{p2->Parent=p1;swi