“八”数码问题的宽度优先搜索与深度优先搜索

《“八”数码问题的宽度优先搜索与深度优先搜索》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

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

3、展，得到节点3；4、判断节点3是否为目标节点，若是则搜索过程结束；若不是则将节点3向第3层扩展，得到节点4；5、判断节点4是否为目标节点，若是则搜索过程结束；若不是则将节点4向第4层扩展，得到节点5；6、判断节点5是否为目标节点，若是则搜索过程结束；若不是则结束此轮搜索，返回到第2层，将节点3向第3层扩展得到节点6；7、判断节点6是否为目标节点，若是则搜索过程结束；若不是则将节点6向第4层扩展，得到节点7；8、判断节点7是否为目标节点，若是则结束搜索过程；若不是则将节点6向第4层扩展得到节点8；9、依次类推，

4、知道得到目标节点为止。三、上述两种搜索策略的比较在宽度优先搜索过程中，扩展到第26个节点时找到了目标节点；而在深度优先搜索过程中，扩展到第18个节点时得到了目标节点。在宽度优先搜索过程中，需要遍历目标节点所在层之前每层的所有节点，即需要遍历所有的分支。而深度优先搜索过程中，则不需要遍历这么多的节点。所以，在“八”数码问题的求解过程中，深度优先搜索的效率明显比宽度优先搜索的效率要高。一般情况下，深度优先适合深度大的树，不适合广度大的树，广度优先则正好相反。所谓深度大的树就是指起始节点到目标节点的中间节点多的树（

5、可以理解成问题有很多中间解，这些解都可以认为是部分正确的，但要得到完全正确的结果——目标节点，就必须先依次求出这些中间解）。所谓广度大的树就是指起始节点到目标节点的可能节点很多的树（可以理解成问题有很多可能解，这些解要么正确，要么错误。要得到完全正确的结果——目标节点，就必须依次判断这些可能解是否正确）。多数情况下，深度优先搜索的效率要高于宽度优先搜索。但某些时候，对于这两种搜索策略的优劣（或效率）还需要针对不同的问题进行具体分析比较。