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

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

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表的末端，

2、提供回到n的指针是否任何节点为目标节点成功-23-深度优先实现过程（1）把起始节点S放入未扩展节点OPEN表中。如果此节点为一目标节点，则得到一个解；（2）如果OPEN为一空表，则失败退出；（3）把第一个节点从OPEN表移到CLOSED表；（4）如果节点n的深度等于最大深度，则转向（2）；（5）扩展节点n，产生其全部后裔，并把它们放入OPEN表的前头。如果没有后裔，则转向（2）；（6）如果后继结点中有任一个目标节点，则得到一个解，成功退出，否则转向（2）。开始把S放入OPEN表S是否为目标节点成功把第一个节点n从把S放入OPEN表移除，放到CLOSED表中移除

3、节点n的深度是否等于最深界限OPEN表为空失败扩展n，把它的后继放入OPEN表的前头，提供回到n的指针是否有任何后继节点为目标节点成功-23-方法一：用C语言实现#include#include#includetypedeflongUINT64;typedefstruct{charx;//位置x和位置y上的数字换位chary;//其中x是0所在的位置}EP_MOVE;#defineSIZE3//8数码问题，理论上本程序也可解决15数码问题，#defineNUMSIZE*SIZE//但move_gen需要

4、做很多修改，输入初始和结束状态的部分和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;iii=0;iii--

5、){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

6、*node,EP_MOVE*move){longpz;//0的位置UINT64t=0xf;for(pz=NUM-1;pz>=0;pz--){if((node->v&t)==0){break;//找到0的位置-23-}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:mov

7、e[0].x=2;move[0].y=1;move[1].x=2;move[1].y=5;-23-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;

8、move[1].x=5;-23-mov