depth-first-search - 关于广度优先完整性与深度优先不完整性的问题

Question

根据 AIMA(人工智能:现代方法)中的 Norvig 的说法，深度优先算法并不完整(不会总是产生解决方案)，因为在某些情况下，下降的子树将是无限的。

另一方面，如果分支因子不是无限的，则广度优先方法被认为是完整的。但这不是与 DFS 中子树无限的情况有些相同的“事物”吗？

如果树的深度是有限的，就不能说 DFS 是完整的吗？那么 BFS 是完整的而 DFS 不是完整的，因为 BFS 的完整性依赖于分支因子是有限的!

Answer 1

一棵树可以是无限的，而没有无限的分支因子。例如，考虑魔方的状态树。给定立方体的配置，移动的次数是有限的(我相信是 18 次，因为一次移动包括选择 9 个“平面”中的一个并将其旋转到两个可能的方向之一)。然而，树是无限深的，因为它完全有可能例如只来回交替旋转同一平面(永远不会有任何进展)。为了防止 DFS 这样做，通常会缓存所有访问过的状态(有效地修剪状态树)——您可能知道。但是，如果状态空间太大(或实际上无限大)，这将无济于事。

我没有广泛研究人工智能，但我认为说 BFS 是完整的而 DFS 不是(毕竟，完整性只是一个在某处定义的术语)的基本原理是无限深的树比无限深的树更频繁地出现分支因子(因为具有无限分支因子意味着您有无限多的选择，我认为这并不常见 - 游戏和模拟通常是离散的)。即使对于有限树，BFS 通常会表现得更好，因为 DFS 很可能从错误的路径开始，在到达目标之前探索树的大部分。尽管如此，正如您所指出的，在有限树中，如果存在，DFS 最终会找到解决方案。