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

该【深度宽度优先搜索---八数码 】是由【帅气的小哥哥】上传分享，文档一共【23】页，该文档可以免费在线阅读，需要了解更多关于【深度宽度优先搜索---八数码 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。-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的指针是否任何节点为目标节点成功-3-深度优先实现过程〔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的指针是否有任何后继节点为目标节点成功方法一:用C语言实现-3-#include<>#include<>#include<>typedeflongUINT64;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;}#RANS(a,b)/*{longiii;(b)=0;for(iii=0;iii<NUM;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->v>p->v)p=p->big;elseif(node->v<p->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->v>q->v){q->big=&m_ar[r];}elseif(node->v<q->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,);m_ar[0].prev=NULL;m_root=m_ar;m_root->small=NULL;m_root->big=NULL;while((h<r)&&(r<MAX_NODE-4)){c=move_gen(&m_ar[h],mv);for(i=0;i<c;i++){mov(&m_ar[h],&mv[i],&node);=&m_ar[h];if(==){pnode=&node;j=0;while(pnode->prev){m_out[j]=*pnode;j++;pnode=pnode->prev;}m_depth=j;