根据Norimaig在AIMA（人工智能：一种现代方法）中，深度优先算法并不完整（并不总是产生解决方案），因为有些情况下子树下降将是无限的 .
另一方面，如果分支因子不是无限的，则称广度优先方法是完整的 . 但是，在DFS中子树无限的情况下，是不是有点像“东西”？
如果树的深度是有限的，那么DFS不能说是完整的吗？那么BFS是如何完成的而DFS不是完整的，因为BFS的完整性依赖于分支因子是有限的！
没有无限的分支因子，树可以是无限的 . 例如，考虑Rubik's Cube的状态树 . 给定立方体的配置，有一定数量的移动（18，我相信，因为移动包括选择9个“平面”中的一个并在两个可能的方向之一中旋转它） . 然而，树是无限深的，因为它完全可能是例如只能来回交替旋转同一平面（从不取得任何进展） . 为了防止DFS这样做，通常会缓存所有访问状态（有效地修剪状态树） - 正如您可能知道的那样 . 但是，如果状态空间太大（或实际上是无限的），这将无济于事 .
我没有广泛研究过AI，但是我认为说DFS不完整的理由是（完全性毕竟只是一个定义的术语）是无限深的树比无限的树更频繁地出现分支因子（因为具有无限的分支因子意味着你有无数的选择，我认为这种选择并不常见 - 游戏和模拟通常是离散的） . 即使对于有限树，BFS通常也会表现得更好，因为DFS很可能从错误的路径开始，在到达目标之前探索树的大部分 . 不过，正如您所指出的，在有限的树中，DFS最终会找到解决方案（如果存在） .
DFS不能卡在循环中（如果我们有一个打开和关闭状态列表） . 算法不完整，因为它没有在无限空间中找到解，即使解决方案深度远低于无穷大 . [2678774_] .
想象一个奇怪定义的状态空间，其中每个节点具有与Fibonacci序列中的跟随数相同的后继数 . 因此，它是递归定义的，因此是无限的 . 我们正在寻找节点2（图中标记为绿色） . 如果DFS以树的右分支开始，则将需要无数个步骤来验证我们的节点不在那里 . 因此它不完整（它不会在合理的时间内完成） . BFS会在第3次迭代中找到解决方案 .
Rubik的立方体状态空间是有限的，它是巨大的，但是有限的（人类陷入循环但DFS不会重复相同的移动两次） . DFS会发现如何解决它的效率非常低，有时这种解决方案是不可行的 . 通常我们认为最大深度是无限的，但我们的资源（存储器）总是有限的 .
2 回答
没有无限的分支因子，树可以是无限的 . 例如，考虑Rubik's Cube的状态树 . 给定立方体的配置，有一定数量的移动（18，我相信，因为移动包括选择9个“平面”中的一个并在两个可能的方向之一中旋转它） . 然而，树是无限深的，因为它完全可能是例如只能来回交替旋转同一平面（从不取得任何进展） . 为了防止DFS这样做，通常会缓存所有访问状态（有效地修剪状态树） - 正如您可能知道的那样 . 但是，如果状态空间太大（或实际上是无限的），这将无济于事 .
我没有广泛研究过AI，但是我认为说DFS不完整的理由是（完全性毕竟只是一个定义的术语）是无限深的树比无限的树更频繁地出现分支因子（因为具有无限的分支因子意味着你有无数的选择，我认为这种选择并不常见 - 游戏和模拟通常是离散的） . 即使对于有限树，BFS通常也会表现得更好，因为DFS很可能从错误的路径开始，在到达目标之前探索树的大部分 . 不过，正如您所指出的，在有限的树中，DFS最终会找到解决方案（如果存在） .
DFS不能卡在循环中（如果我们有一个打开和关闭状态列表） . 算法不完整，因为它没有在无限空间中找到解，即使解决方案深度远低于无穷大 . [2678774_] .
想象一个奇怪定义的状态空间，其中每个节点具有与Fibonacci序列中的跟随数相同的后继数 . 因此，它是递归定义的，因此是无限的 . 我们正在寻找节点2（图中标记为绿色） . 如果DFS以树的右分支开始，则将需要无数个步骤来验证我们的节点不在那里 . 因此它不完整（它不会在合理的时间内完成） . BFS会在第3次迭代中找到解决方案 .
Rubik的立方体状态空间是有限的，它是巨大的，但是有限的（人类陷入循环但DFS不会重复相同的移动两次） . DFS会发现如何解决它的效率非常低，有时这种解决方案是不可行的 . 通常我们认为最大深度是无限的，但我们的资源（存储器）总是有限的 .