深度宽度优先搜索---八数码

-1-八数码问题具体思路：宽度优先算法实现过程（1）把起始节点放到OPEN表中；（2）如果OPEN是个空表，则没有解，失败退出；否则继续；（3）把第一个节点从OPEN表中移除，并把它放入CLOSED的扩展节点表中；（4）扩展节点n。如果没有后继节点，则转向（2）（5）把n的所有后继结点放到OPEN表末端，并提供从这些后继结点回到n的指针；（6）如果n的任意一个后继结点是目标节点，则找到一个解答，成功退出，否则转向（2）。开始把S放入OPEN表OPEN表为空失败把第一个节点n从把S放入OPEN表移除，放到CLOSED表中移除扩展n，把它的后继节点放入OPEN表的末端，提供回到n的指针是否任何节点为目标节点成功-2-深度优先实现过程（1）把起始节点S放入未扩展节点OPEN表中。如果此节点为一目标节点，则得到一个解；（2）如果OPEN为一空表，则失败退出；（3）把第一个节点从OPEN表移到CLOSED表；（4）如果节点n的深度等于最大深度，则转向（2）；（5）扩展节点n，产生其全部后裔，并把它们放入OPEN表的前头。如果没有后裔，则转向（2）；（6）如果后继结点中有任一个目标节点，则得到一个解，成功退出，否则转向（2）。方法开始把S放入OPEN表S是否为目标节点成功把第一个节点n从把S放入OPEN表移除，放到CLOSED表中移除节点n的深度是否等于最深界限OPEN表为空失败扩展n，把它的后继放入OPEN表的前头，提供回到n的指针是否有任何后继节点为目标节点成功-3-一：用C语言实现#includestdio.h#includestring.h#includestdlib.htypedeflongUINT64;typedefstruct{charx;//位置x和位置y上的数字换位chary;//其中x是0所在的位置}EP_MOVE;#defineSIZE3//8数码问题，理论上本程序也可解决15数码问题，#defineNUMSIZE*SIZE//但move_gen需要做很多修改，输入初始和结束状态的部分和check_input也要修改#defineMAX_NODE1000000#defineMAX_DEP100#defineXCHG(a,b){a=a+b;b=a-b;a=a-b;}#defineTRANS(a,b)/*{longiii;(b)=0;for(iii=0;iiiNUM;iii++)(b)=((b)4)+a[iii];}*///将数组a转换为一个64位的整数b#defineRTRANS(a,b)\{\longiii;\UINT64ttt=(a);\-4-for(iii=NUM-1;iii=0;iii--)\{\b[iii]=ttt&0xf;\ttt=4;\}\}//将一个64位整数a转换为数组b//typedefstructEP_NODE_Tag{UINT64v;//保存状态，每个数字占4个二进制位，可解决16数码问题structEP_NODE_Tag*prev;//父节点structEP_NODE_Tag*small,*big;}EP_NODE;EP_NODEm_ar[MAX_NODE];EP_NODE*m_root;longm_depth;//搜索深度EP_NODEm_out[MAX_DEP];//输出路径//longmove_gen(EP_NODE*node,EP_MOVE*move){longpz;//0的位置UINT64t=0xf;for(pz=NUM-1;pz=0;pz--){if((node-v&t)==0){break;//找到0的位置-5-}t=4;}switch(pz){case0:move[0].x=0;move[0].y=1;move[1].x=0;move[1].y=3;return2;case1:move[0].x=1;move[0].y=0;move[1].x=1;move[1].y=2;move[2].x=1;move[2].y=4;return3;case2:move[0].x=2;move[0].y=1;move[1].x=2;move[1].y=5;-6-return2;case3:move[0].x=3;move[0].y=0;move[1].x=3;move[1].y=6;move[2].x=3;move[2].y=4;return3;case4:move[0].x=4;move[0].y=1;move[1].x=4;move[1].y=3;move[2].x=4;move[2].y=5;move[3].x=4;move[3].y=7;return4;case5:move[0].x=5;move[0].y=2;move[1].x=5;-7-move[1].y=4;move[2].x=5;move[2].y=8;return3;case6:move[0].x=6;move[0].y=3;move[1].x=6;move[1].y=7;return2;case7:move[0].x=7;move[0].y=6;move[1].x=7;move[1].y=4;move[2].x=7;move[2].y=8;return3;case8:move[0].x=8;move[0].y=5;move[1].x=8;move[1].y=7;-8-return2;}return0;}longmov(EP_NODE*n1,EP_MOVE*mv,EP_NODE*n2)//走一步，返回走一步后的结果{charss[NUM];RTRANS(n1-v,ss);XCHG(ss[mv-x],ss[mv-y]);TRANS(ss,n2-v);return0;}longadd_node(EP_NODE*node,longr){EP_NODE*p=m_root;EP_NODE*q;while(p){q=p;if(p-v==node-v)return0;elseif(node-vp-v)p=p-big;elseif(node-vp-v)p=p-small;}-9-m_ar[r].v=node-v;m_ar[r].prev=node-prev;m_ar[r].small=NULL;m_ar[r].big=NULL;if(node-vq-v){q-big=&m_ar[r];}elseif(node-vq-v){q-small=&m_ar[r];}return1;}/*得到节点所在深度*/longget_node_depth(EP_NODE*node){longd=0;while(node-prev){d++;node=node-prev;}returnd;}/*返回值：成功－返回搜索节点数，节点数不够－(-1)，无解－(-2)*/longbfs_search(char*begin,char*end)-10-{longh=0,r=1,c,i,j;EP_NODEl_end,node,*pnode;EP_MOVEmv[4];//每个局面最多4种走法TRANS(begin,m_ar[0].v);TRANS(end,l_end.v);m_ar[0].prev=NULL;m_root=m_ar;m_root-small=NULL;m_root-big=NULL;while((hr)&&(rMAX_NODE-4)){c=move_gen(&m_ar[h],mv);for(i=0;ic;i++){mov(&m_ar[h],&mv[i],&node);node.prev=&m_ar[h];if(node.v==l_end.v){pnode=&node;j=0;while(pnode-prev){m_out[j]=*pnode;j++;pnode=pnode-prev;}m_depth=j;-11-returnr;}if(add_node(&node,r))r++;//只能对历史节点中没有的新节点搜索，否则会出现环}h++;printf(\rSearch...%9d/%d@%d,h,r,get_node_depth(&m_ar[h]));}if(h==r){return-2;}else{return-1;}}longcheck_input(char*s,chara,longr){longi;for(i=0;ir;i++){if(s[i]==a-0x30)return0;}return1;}longcheck_possible(char*begin,char*end){charfs;longf1=0,f2=0;longi,j;for(i=0;iNUM;i++)-12-{fs=0;for(j=0;ji;j++){if((begin[i]!=0)&&(begin[j]!=0)&&(begin[j]begin[i]))fs++;}f1+=fs;fs=0;for(j=0;ji;j++){if((end[i]!=0)&&(end[j]!=0)&&(end[j]end[i]))fs++;}f2+=fs;}if((f1&1)==(f2&1))return1;elsereturn0;}voidoutput(void){longi,j,k;charss[NUM];for(i=m_depth-1;i=0;i--){RTRANS(m_out[i].v,ss);for(j=0;jSIZE;j++){for(k=0;kSIZE;k++)-13-{printf(%2d,ss[SIZE*j+k]);}printf(\n);}printf(\n);}}intmain(void){chars1[NUM];chars2[NUM];longr;chara;printf(请输入开始状态:);r=0;while(rNUM){a=getchar();if(a=0x30&&a0x39&&check_input(s1,a,r)){s1[r++]=a-0x30;printf(%c,a);}}printf(\n请输入结束状态:);r=0;-14-while(rNUM){a=getchar();if(a=0x30&&a0x39&&check_input(s2,a,r)){s2[r++]=a-0x30;printf(%c,a);}}printf(\n);if(check_possible(s1,s2)){r=bfs_search(s1,s2);printf(\n);if(r=0){printf(查找深度=%d,所有的方式=%ld\n,m_depth,r);output();}elseif(r==-1){printf(没有找到路径.\n);}elseif(r==-2){printf(这种状态变换没有路径到达.\n);}else{printf(不确定的错误.\n);-15-}}else{printf(不允许这样移动!\n);}return0;}方法二：用MATLAB实现program8no_bfs;{八数码的宽度优先搜索算法}ConstDir:array[1..4,1..2]ofinteger{四种移动方向，对应产生式规则}=((1,0),(-1,0),(0,1),(0,-1));n=10000;TypeT8no=array[1..3,1..3]ofinteger;TList=recordFather:integer;{父指针}dep:byte;{深度}X0,Y0:byte;{0的位置}State:T8no;{棋盘状态}end;VarSource,Target:T8no;-16-List:array[0..10000]ofTList;{综合数据库}Closed,open,Best:integer{Best表示最优移动次数}Answer:integer;{记录解}Found:Boolean;{解标志}procedureGetInfo;{读入