无信息搜索策略对比.doc

《无信息搜索策略对比.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、无信息搜索策略对比广度优先一致代价搜索深度优先深度受限搜索迭代加深的深度优先搜索双向搜索完备性首先扩展根节点，然后扩展根节点的所有后继，接着再扩展它们的后继，从而一层一层的对节点进行扩展。BFS是一个简单的搜索策略，在搜索过程中会对所有状态进行遍历，因此它是完备的在BFS的基础上，一致代价搜索不在扩展深度最浅的节点，而是通过比较路径消耗g（n），并选择当前代价最小的节点进行扩展，因此它是完备的DFS扩展根节点的一个后继，然后扩展它的一个后继，直到到达搜索树的最深层，那里的节点没有后继，于是DFS回溯到上一层，扩展另外一个未被扩展的节点。在有限状态空间中，DFS是完备的，因为它

2、可以把所有空间遍历一遍；而在无限空间中，DFS则有可能会进入深度无限的分支，因此是不完备的。深度受限搜索设定一个最大深度dmax，当搜索深度大于dmax的时候立即回溯，从而避免了在无穷状态空间中陷入深度无限的分支，是不完备的。迭代加深的深度有限搜索也设定一个最大深度dmax，开始我们把dmax设为1，然后进行深度受限搜索，如果么有找到答案，则让dmax加一，并再次进行深度有限搜索，以此类推直到找到目标。这样既可以避免陷入深度无限的分支，同时还可以找到深度最浅的目标解，从而在每一步代价一致的时候找到最优解双向搜索从两个方向同时搜索，直到相遇，所以是完备的。最优性因为我们总会在最

3、浅那一层找到目标状态，因此当且仅当每一步的代价都一致的时候，BFS可以得到最优解因为我们只需要保存当前分支的状态，因此空间复杂度远远好于BFS。然而DFS并不能保证找到最优解深度受限搜索可能因为两种失败而告终，标准的failure返回值指示无解，cutoff值指示在深度界限内无解，迭代加深的深度优先搜索做法是不断的增加深度限制，直到找到目标，所以可以保证找到最优解双向搜索总是可以找到最优解在BFS的基础上，一致代价搜索不在扩展深度最浅的节点，而是通过比较路径消耗g（n），并选择当前代价最小的节点进行扩展，因此可以保证无论每一步代价是否一致，都能够找到最优解所以不能保证得到最优

4、解时间复杂度假设搜索树每个节点有b个后继，深度为d，则时间复杂度和空间复杂度均为O(b^d)比广度优先复杂得多，比O()大得多DFS的时间复杂度为为O()其时间与空间复杂度与深度界限l有关，为O()时间复杂度是O(),与宽度优先搜索相似时间复杂度是o()空间复杂度假设搜索树每个节点有b个后继，深度为d，则时间复杂度和空间复杂度均为O()比广度优先复杂得多，比O()大得多空间复杂度仅为O（d）其时间与空间复杂度与深度界限l有关，为O()空间复杂度仅为O（bd）空间复杂度是o()