为什么说深度优先搜索会遭受无限循环的困扰？ [英] Why is Depth-First Search said to suffer from infinite loops?

问题描述

我已经阅读了有关 DFS 和 BFS 很多次，但我对此疑问一直困扰不已。在很多文章中都提到DFS可能陷入无限循环。

I have read about DFS and BFS many times but I have this doubt lingering my mind since long. In a lot of articles it is mentioned that DFS can get stuck in infinite loops.

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

As far as I know, this limitation can easily be removed by keeping track of the visited nodes. In fact, in all the books that I have read, this little check is a part of DFS.

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

So why are 'infinite loops' mentioned as a disadvantage of DFS? Is it just because the original DFS algorithm did not have this check for visited nodes? Please explain.

推荐答案

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

(1) In graph search algorithms [used frequently on AI], DFS's main advantage is space efficiency. It is its main advantage on BFS. However, if you keep track of visited nodes, you lose this advantage, since you need to store all visited nodes in memory. Don't forget the size of visited nodes increases drastically over time, and for very large/infinite graphs - might not fit in memory.

（2）有时DFS可以是在无限分支中（在无限图中）。无限分支是一个没有结束的分支[总是有更多的儿子]，并且也没有将您带到目标节点，因此对于DFS，您可能会无限期地扩展该分支，并错过好的分支，

(2) Sometimes DFS can be in an infinite branch [in infinite graphs]. An infinite branch is a branch that does not end [always has "more sons"], and also does not get you to your target node, so for DFS, you might keep expanding this branch inifinitely, and 'miss' the good branch, that leads to the target node.

奖金：

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

这篇关于为什么说深度优先搜索会遭受无限循环的困扰？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！