我读过 DFS和 BFS很多次,但我长期以来一直有这个疑问。在很多文章中都提到 DFS 会陷入无限循环。
据我所知,通过跟踪访问过的节点可以很容易地消除这个限制。事实上,在我读过的所有书籍中,这个小检查都是 DFS 的一部分。
那么,为什么将“无限循环”称为 DFS 的缺点?难道只是因为原来的DFS算法没有对访问过的节点做这个检查吗?请解释。
最佳答案
(1) 在图搜索算法中 [在 AI 上经常使用],DFS 的主要优势是空间效率。这是它在 BFS 上的主要优势。但是,如果您跟踪访问过的节点,就会失去这个优势,因为您需要将所有访问过的节点存储在内存中。不要忘记访问节点的大小会随着时间的推移急剧增加,对于非常大/无限的图 - 可能无法容纳在内存中。
(2) 有时 DFS 可以位于无限分支 [in infinite graphs]。无限分支是一个没有结束的分支[总是有“更多的儿子”],也不会把你带到你的目标节点,所以对于DFS,你可能会无限地扩展这个分支,并且“错过”好的分支,通向目标节点。
奖励:
您可以通过结合使用 DFS 和 BFS 来克服 DFS 中的这个缺陷,同时保持相对较小的内存大小:Iterative Deepening DFS
关于algorithm - 为什么说深度优先搜索会遇到无限循环?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36123465/