广度首次搜索和迭代性深化之间的差异
-
24-10-2019 - |
题
我了解BFS和DFS,但是对于我的一生,我无法弄清迭代加深和BFS之间的区别。显然,迭代加深与DFS具有相同的内存使用率,但是我看不到这是怎么可能的,因为它只是像BF一样不断扩展。如果有人能澄清一下,那真是太棒了。
如果需要的话,可以处理:
A
/ \
B C
/ / \
D E F
解决方案
据我了解,迭代加深会使DFS降至深度1,然后DFS将DFS降至2 ...向下到深度N,依此类推,依此类推,直到它没有更多的水平
例如,我认为那棵树会被阅读
read visited depth
A A 1
ABC ABAC 2
ABDCEF ABDBACECF 3
我相信它几乎可以为每个级别的深度限制做一个单独的DFS并丢弃记忆。
其他提示
从我对算法的理解来看,IDDF(迭代深度深度搜索)只是多次执行的深度优先搜索,从而加深了每次迭代中搜索的节点的水平。因此,内存需求与深度优先搜索相同,因为最大深度迭代只是完整的深度优先搜索。
因此,以您给出的树的示例,第一次迭代将访问节点A,第二个迭代将访问Nodes A,B和C,并且第三个迭代将访问树的所有节点。
这样实现的原因是,如果搜索有时间限制,那么该算法至少将对“良好得分”节点有所了解,如果它在完成完整的遍历之前达到了时间限制那个树。
这与广度优先的搜索不同,因为在每次迭代中,节点都会像在深度搜索中一样,而不是在广度优先的搜索中。通常,IDDFS算法可能会存储从每次迭代中找到的“最佳评分”节点。
内存使用情况是它在任何时候节省的最大节点数量。不是访问的节点的数量。
在任何时候,IDFS都需要在分支中仅存储节点。 BFS必须保存其搜索深度的所有节点。要查看效果,带有分支因子8而不是2的树,要搜索到3的深度,BFS需要存储一个大量的64个节点。 IDF只需要3个。
不隶属于 StackOverflow