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

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

ID:25957475

大小:138.63 KB

页数:23页

时间:2018-11-23

深度宽度优先搜索---八数码_第1页
深度宽度优先搜索---八数码_第2页
深度宽度优先搜索---八数码_第3页
深度宽度优先搜索---八数码_第4页
深度宽度优先搜索---八数码_第5页
资源描述:

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

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、标节点成功-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表中移除节点n的深度是否等于最深界限OPEN表为空失败扩展n,把它的后继

3、放入OPEN表的前头,提供回到n的指针是否有任何后继节点为目标节点成功-23-方法一:用C语言实现#include#include#includetypedeflongUINT64;typedefstruct{charx;//位置x和位置y上的数字换位chary;//其中x是0所在的位置}EP_MOVE;#defineSIZE3//8数码问题,理论上本程序也可解决15数码问题,#defineNUMSIZE*SIZE//但move_gen需要做很多修改,输入初始和结束状态的部分和check_input也要修改#defineMAX_NOD

4、E1000000#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--){b[iii]=ttt&0xf;ttt>>=4;}}//将一个64位整数a转换为数组b//typedefstruct

5、EP_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->

6、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:move[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

7、=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;-23-mov

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。