小编典典

为什么说深度优先搜索会遭受无限循环的困扰?

algorithm

我已经读过很多关于DFSBFS的文章,但是我对此疑问一直困扰着我很久。在许多文章中都提到DFS可能陷入无限循环。

据我所知,可以通过跟踪访问的节点来轻松消除此限制。实际上,在我读过的所有书中,这张小支票都是DFS的一部分。

那么为什么提到“无限循环”是DFS的缺点呢?仅仅是因为原始DFS算法没有对访问的节点进行此检查吗?请解释。


阅读 779

收藏
2020-07-28

共1个答案

小编典典

(1)在图搜索算法中[在AI上经常使用],DFS的主要优势是 空间效率 。这是它在BFS上的主要优势。但是,
如果跟踪访问的节点,则会失去此优势 ,因为您需要将所有访问的节点存储在内存中。不要忘记,访问的节点的大小会随着时间急剧增加,对于非常大/无限的图-
可能不适合内存。

(2)有时DFS可以在 无限分支中
[在无限图形中]。无限分支是一个没有结束的分支[总是有“更多的儿子”],并且也没有将您带到目标节点,因此对于DFS,您可能会继续无限扩大此分支,并“错过”好的分支,导致目标节点。

奖励:
您可以通过结合使用DFS和BFS来克服DFS中的这一缺陷,同时保持相对较小的内存大小:迭代加深DFS

2020-07-28