graph - 在什么情况下我想运行 BFS 或 DFS 而不是 IDDFS？

Question

问题是关于树搜索。我相信我了解 DFS、BFS 和 IDDFS 之间的区别。在最优性、完整性、时间复杂度和空间复杂度方面，IDDFS 在树搜索方面具有更好的性能。

那么，我什么时候想在树搜索中运行 BFS 或 DFS 而不是 IDDFS？

谢谢

Answer 1

以下是我们对 DFS 和 BFS 的了解，以及为什么我们会考虑在它们之上使用 IDDFS：

DFS

DFS 遍历从与根相邻的一个节点开始，然后是与该节点相邻的下一个节点，依此类推。当目标节点靠近根但不在算法遍历的第一个相邻节点的子树中时，可能会出现这种方法的问题。这将导致算法遍历不包含目标节点的整个子树，效率不高。

BFS

BFS 逐层遍历一棵树。就深度而言，目标节点离根节点越近，找到它的速度就越快。如果目标节点不在最初遍历的子树中，这消除了 DFS 的问题。这里的权衡是 BFS 需要更多空间，O(n)，其中 n 是 DFS 需要 O(d) 空间的节点数，其中 d 是树的深度。

IDDFS

IDDFS 结合了 DFS 的空间效率和 BFS 的更快搜索（请注意 BFS 并不总是更快，但在许多情况下，它会首先找到目标节点）。IDDFS 调用具有初始值的不同深度的 DFS。它本质上是以 BFS 方式调用 DFS。这里的权衡是 IDDFS 实现起来要复杂得多，因此只有在您关心有限的空间和时间时才应该真正使用它。否则，根据您的喜好，BFS 或 DFS 就足够了。

我希望这些信息对你有用！