vja*_*n27 9 algorithm search breadth-first-search depth-first-search
我已多次阅读有关DFS和BFS的内容,但我对此长期以来一直怀疑.在很多文章中提到DFS可能陷入无限循环.
据我所知,通过跟踪访问的节点可以很容易地消除这种限制.事实上,在我读过的所有书中,这个小支票都是DFS的一部分.
那么为什么"无限循环"被提到是DFS的缺点呢？是不是因为原始DFS算法没有对访问过的节点进行此检查？请解释.
ami*_*mit 22
(1)在图搜索算法[在AI上经常使用],DFS的主要优点是空间效率.这是它在BFS上的主要优势.但是,如果您跟踪受访节点,则会失去此优势,因为您需要将所有访问过的节点存储在内存中.不要忘记访问节点的大小随着时间的推移而急剧增加,对于非常大/无限的图形 - 可能不适合内存.
(2)有时DFS可以处于无限分支 [无限图]中.无限分支是一个不结束的分支[总是有"更多的儿子"],也不会让你到达你的目标节点,所以对于DFS,你可以继续扩展这个分支,并且"错过"好的分支,它导致目标节点.
奖励:
您可以通过使用DFS和BFS的组合来克服DFS中的这个缺陷,同时保持相对较小的内存大小:迭代深化DFS