根据 AIMA（人工智能：现代方法）中的 Norvig 的说法，深度优先算法并不完整（不会总是产生解决方案），因为在某些情况下，正在下降的子树将是无限的。
另一方面，如果分支因子不是无限的，则说广度优先方法是完整的。但这不是与 DFS 中子树无限的情况相同的“事情”吗？
如果树的深度是有限的，就不能说 DFS 是完整的吗？那么 BFS 是完整的而 DFS 不是完整的，因为 BFS 的完整性依赖于分支因子是有限的！
问问题
12846 次
3 回答
10
一棵树可以是无限的而没有无限的分支因子。例如，考虑魔方的状态树。给定立方体的配置，移动次数是有限的（我相信是 18 次，因为移动包括选择 9 个“平面”中的一个并在两个可能的方向之一上旋转它）。然而，树是无限深的，因为完全有可能例如只交替地来回旋转同一平面（永远不会取得任何进展）。为了防止 DFS 这样做，通常会缓存所有访问过的状态（有效地修剪状态树） - 正如您可能知道的那样。但是，如果状态空间太大（或实际上是无限的），这将无济于事。
我没有广泛研究过人工智能，但我假设说 BFS 是完整的而 DFS 不完整的理由是无限深的树比无限深的树更频繁地出现分支因子（因为具有无限分支因子意味着您有无限数量的选择，我认为这并不常见 - 游戏和模拟通常是离散的）。即使对于有限的树，BFS 通常也会表现得更好，因为 DFS 很可能从错误的路径开始，在到达目标之前探索树的大部分。尽管如此，正如您所指出的，在有限树中，如果存在，DFS 最终会找到解决方案。
于 2011-02-21T16:50:54.337 回答
7
DFS 不能陷入循环（如果我们有一个打开和关闭状态的列表）。该算法是不完整的，因为它没有在无限空间中找到解决方案，即使解决方案的深度d远低于无穷大。
想象一个奇怪定义的状态空间，其中每个节点的后继数与斐波那契数列中的后续数相同。因此，它是递归定义的，因此是无限的。我们正在寻找节点 2（图中标记为绿色）。如果 DFS 从树的右分支开始，则需要无数个步骤来验证我们的节点是否不存在。因此它不完整（它不会在合理的时间内完成）。BFS 将在第三次迭代中找到解决方案。
魔方的状态空间是有限的，它很大，但也是有限的（人类陷入循环但 DFS 不会重复相同的动作两次）。DFS 会找到非常低效的方法来解决它，有时这种解决方案是不可行的。通常我们认为最大深度是无限的，但我们的资源（内存）总是有限的。
于 2013-02-27T07:55:29.630 回答
0
深度优先搜索的属性很大程度上取决于使用的是图搜索还是树搜索版本。避免重复状态和冗余路径的图搜索版本在有限状态空间中是完整的，因为它最终会扩展每个节点。另一方面，树搜索版本并不完整——例如，在图 3.6 中，算法将永远遵循 Arad-Sibiu-Arad-Sibiu 循环
资料来源：人工智能：一种现代方法
于 2020-12-02T19:35:02.217 回答