“八”数码问题的宽度优先搜索与深度优先搜索_第1页
“八”数码问题的宽度优先搜索与深度优先搜索_第2页
“八”数码问题的宽度优先搜索与深度优先搜索_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、“八”数码问题的宽度优先搜索与深度优先搜索我在观看视频和查看大学课本及网上搜索等资料才对“八”数码问题有了更进一步的了解和认识。一、“八”数码问题的宽度优先搜索步骤如下：1、判断初始节点是否为目标节点，若初始节点是目标节点则搜索过程结束；若不是则转到第2步；2、由初始节点向第1层扩展，得到3个节点：2、3、4；得到一个节点即判断该节点是否为目标节点，若是则搜索过程结束；若2、3、4节点均不是目标节点则转到第3步；3、从第1层的第1个节点向第2层扩展，得到节点5；从第1层的第2个节点向第2层扩展，得到3个节点：6、7、8；从第1层的第3个节点向第2层扩展得到节点9；得到一个节点即判断该节点是否为

2、目标节点，若是则搜索过程结束；若6、7、8、9节点均不是目标节点则转到第4步；4、按照上述方法对下一层的节点进行扩展，搜索目标节点；直至搜索到目标节点为止。二、“八”数码问题的深度优先搜索步骤如下：、设置深度界限，假设为5；2、判断初始节点是否为目标节点，若初始节点是目标节点则搜索过程结束；若不是则转到第2步；3、由初始节点向第1层扩展，得到节点2，判断节点2是否为目标节点；若是则搜索过程结束；若不是，则将节点2向第2层扩展，得到节点3；4、判断节点3是否为目标节点，若是则搜索过程结束；若不是则将节点3向第3层扩展，得到节点4；5、判断节点4是否为目标节点，若是则搜索过程结束；若不是则将节点4

3、向第4层扩展，得到节点5；6、判断节点5是否为目标节点，若是则搜索过程结束；若不是则结束此轮搜索，返回到第2层，将节点3向第3层扩展得到节点6；7、判断节点6是否为目标节点，若是则搜索过程结束；若不是则将节点6向第4层扩展，得到节点7；8、判断节点7是否为目标节点，若是则结束搜索过程；若不是则将节点6向第4层扩展得到节点8；9、依次类推，知道得到目标节点为止。三、上述两种搜索策略的比较在宽度优先搜索过程中，扩展到第26个节点时找到了目标节点；而在深度优先搜索过程中，扩展到第18个节点时得到了目标节点。在宽度优先搜索过程中，需要遍历目标节点所在层之前每层的所有节点，即需要遍历所有的分支。而深度优先搜索过程中，则不需要遍历这么多的节点。所以，在“八”数码问题的求解过程中，深度优先搜索的效率明显比宽度优先搜索的效率要高。一般情况下，深度优先适合深度大的树，不适合广度大的树，广度优先则正好相反。所谓深度大的树就是指起始节点到目标节点的中间节点多的树（可以理解成问题有很多中间解，这些解都可以认为是部分正确的，但要得到完全正确的结果目标节点，就必须先依次求出这些中间解）。所谓广度大的树就是指起始节点到目标节点的可能节点很多的树（可以理解成问题有很多可能解，这些解要么正确，要么错误。要得到完全正确的结果目标节点，就必须依次判断这些可能解是否正确）。多数情况下

人人文库> 全部分类> 办公材料 > 办公文档

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论