八数码宽度优先搜索

/*程序利用C++程序设计语言，在VC6.0下采用宽度优先的搜索方式，成功的解决了八数码问题。程序中把OPEN表和CLOSED表用队列的方式存储，大大地提高了效率，开始的时候要输入目标状态和起始状态，由于在宽度优先搜索的情况下，搜索过程中所走过的状态是不确定且很庞大的，所以程序最后输出宽度优先情况下最少步数的搜索过程以及程序运行所需要的时间*/#includeiostream#includestdio.h#includestdlib.h#includetime.h#includestring.h#includequeue#includestackusingnamespacestd;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*************************************************endl;for(inti=0;iN;i++){for(intj=0;jN;j++){coutmap-cell[i][j];}coutendl;}cout*************************************************endl;}//移动图structMap*MoveMap(structMap*map,DirectionDirect,boolCreateNewMap){structMap*NewMap;//获取空闲格位置inti,j;for(i=0;iN;i++){boolHasGetBlankCell=false;for(j=0;jN;j++){if(map-cell[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_i0)AbleMove=false;break;caseLeft:t_j--;if(t_j0)AbleMove=false;break;caseRight:t_j++;if(t_j=N)AbleMove=false;break;};if(!AbleMove)//不可以移动则返回原节点{returnmap;}if(CreateNewMap){NewMap=newMap();for(intx=0;xN;x++)for(inty=0;yN;y++)NewMap-cell[x][y]=map-cell[x][y];}elseNewMap=map;NewMap-cell[i][j]=NewMap-cell[t_i][t_j];NewMap-cell[t_i][t_j]=0;returnNewMap;}boolIsSuccess(structMap*map,structMap*Target){boolIsSuc=true;for(inti=0;iN;i++){for(intj=0;jN;j++){if(map-cell[i][j]!=Target-cell[i][j]){IsSuc=false;break;}}if(!IsSuc)break;}returnIsSuc;}structMap*BNF_Search(structMap*begin,structMap*Target){structMap*p1,*p2,*p=NULL;boolIsSucc=false;queuestructMap*Queue;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)//数码是否可以移动{p2-Parent=p1;switch(Direct)//设置屏蔽方向,防止往回推{caseUp:p2-BelockDirec=Down;break;caseDown:p2-BelockDirec=Up;break;caseLeft:p2-BelockDirec=Right;break;caseRight:p2-BelockDirec=Left;break;}if(IsSuccess(p2,Target)){p=p2;returnp;}Queue.push(p2);n++;}}}while(!Queue.empty()||p==NULL);returnp;}intJou(structMap*map)//将八数码转换成一个数列，并计算其逆序数{inta=0;charb[9];for(inti=0;iN;i++){for(intj=0;jN;j++)b[i*3+j]=map-cell[i][j];}for(intk=0;k9;k++){for(inth=0;hk;h++){if((b[h]b[k])&&b[h]!=0)a++;}}returna%2;}intmain(){inta1,a2;inti,j,m,n;inttarget[9];intflag;MapTarget;Map*begin,*T;begin=newMap;cout请输入八数码的目标状态(用0代替空格):endl;//输入目标状态for(i=0;i9;i++)//此for循环用来把输入的数存入到target数组中{flag=0;cintarget[i];for(j=0;ji;j++)if(target[i]==target[j])flag=1;if(target[i]0||target[i]8||flag==1)//判断输入是否正确{i--;cout输入错误，请关闭重新运行!\n;}}intk=0;for(m=0;m3;m++)//把数组target中的数传给图Target{for(n=0;n3;n++){Target.cell[m][n]=target[k];k++;}}//输入起始状态cout请输入八数码的起始状态(用0代替空格):endl;for(i=0;i9;i++){flag=0;cintarget[i];for(j=0;ji;j++)if(target[i]==target[j])//判断输入的数是否正确flag=1;if(target[i]0||target[i]8||flag==1){i--;cout输入错误，请关闭重新运行!\n;}}k=0;for(m=0;m3;m++){for(n=0;n3;n++){begin-cell[m][n]=target[k];k++;}}begin-Parent=NULL;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{doublestart=clock();cout有解endl;//图搜索T=BNF_Search(begin,&Target);//打印if(T!=NULL){//把路径倒序Map*p=T;stackMap*Stack1;while(p-Parent!=NULL){Stack1.push(p);p=p-Parent;}cout宽度优先最少步数的搜索过程为:endl;while(!Stack1.empty()){PrintMap(Stack1.top());c++;Stack1.pop();}cout\n完成!endl;cout找到目标状态所需要的最少步数为:cendl;doubleend=clock();cout程序运行的时间为:end-startmsendl;}}return0;}