回溯和深度优先搜索有什么区别？

Question

回溯算法和深度优先搜索有什么区别？

- user53670

Answer 1

回溯法 是一种更为通用的算法。

深度优先搜索 是一种特定形式的回溯法，用于搜索树结构。引用维基百科：

从根节点开始（在图形中选择某些节点作为根节点），沿着每个分支尽可能远地探索，然后进行回溯。

它使用回溯法作为与树交互的手段，但仅限于树结构。

而回溯法可以应用于任何类型的数据结构，只要该结构的部分领域可以被消除 - 不管它是否是逻辑树。维基百科的示例使用了国际象棋棋盘和一个特定的问题 - 您可以查看一步棋，并将其消除，然后回溯到下一步可能的棋步，再进行消除等。

- Reed Copsey

---

回复这里的一个古老帖子。回答不错，但是......国际象棋问题也可以表示为一棵树，是吗？:-)从棋盘上任何一个位置开始，对于给定的棋子，难道没有一棵延伸到未来的可能移动树吗？在任何可以使用回溯的情况下，我觉得都可以建模为一棵树，但我不确定我的直觉是否正确。 - The111

@The111：确实，任何搜索问题都可以表示为一棵树--对于每个可能的局部解决方案，您都有一个节点，并且从每个节点到该状态下可能的一个或多个备选选择之间都存在一条边。我认为lcn的答案，即回溯通常意味着在递归期间生成的（通常是隐式的）搜索树上进行DFS，最接近真相。 - j_random_hacker

那么，深度优先搜索是一种探索树（或者更普遍地说是图）的方式，而回溯则是解决问题的一种方法（它使用深度优先搜索和剪枝）。 :-) - The111

令人困惑的是，维基百科将回溯描述为深度优先搜索算法，似乎混淆了这两个概念。 - Anderson Green

一个好的解释！真的很有帮助。 - Zhou Haibo

我认为你指的是图而不是树。由于棋盘作为一个平面图可能会出现圆圈，而树却不能包含圆圈。 - Zack Light

Answer 2

我认为另一个相关问题的这个答案提供了更多深入的见解。

对于我来说，回溯和DFS之间的区别在于回溯处理隐式树而DFS处理显式树。这似乎微不足道，但意义重大。当回溯访问问题的搜索空间时，隐式树会被遍历和剪枝。然而，对于DFS，它所处理的树/图是明确构建的，不可接受的情况已在任何搜索之前被抛弃，即被剪枝掉。

因此，回溯是针对隐式树的DFS，而DFS则是没有剪枝的回溯。

- lcn

---

我认为将回溯视为处理隐式树是令人困惑的。当我第一次阅读时，我同意这一点，但深入挖掘后，我意识到“隐式树”实际上是递归树。以使用回溯的任何示例为例，例如对字符串进行排列，关于问题本身没有逻辑树（没有隐式树），但我们确实有一个递归树来模拟增量字符串构建过程。至于修剪，那就是对递归树进行修剪，其中执行了完全暴力搜索...（待续） - Gang Fang

打印“answer”字符串的所有排列组合，假设第3个字符必须是字符“a”。递归树的前两个级别符合O（n！），但在第三个级别上，除了那些附加“a”的分支之外，所有分支都被修剪（回溯）。 - Gang Fang

@GangFang同意，我喜欢指出这通常是一个递归树。尽管我猜它是解空间的概念树，但我不知道有什么情况下不使用递归来创建该解空间。 - yoyodunno

Answer 3

在我看来，大多数答案要么非常不精确，要么没有任何参考资料可以验证。所以让我分享一份带有参考的非常清晰的解释。

首先，DFS是一种通用的图遍历（和搜索）算法。因此它可以应用于任何图形（甚至森林）。树是图的一种特殊形式，因此DFS也适用于树。本质上，让我们停止说它只适用于树或类似的情况。

根据[1]，回溯是一种特殊的DFS，主要用于节省空间（内存）。我即将提到的区别可能会令人困惑，因为在这种类型的图算法中，我们习惯于使用邻接列表表示和迭代模式来访问节点的所有直接相邻节点（对于树来说就是子节点），我们经常忽略一个糟糕的获取所有直接相邻节点实现可能导致底层算法的内存使用差异。

此外，如果图节点具有分支因子b和直径h（对于树来说这是树高度），如果我们在访问节点时存储所有直接相邻节点，内存要求将是big-O(bh)。然而，如果我们一次只取一个（直接的）相邻节点并扩展它，那么内存复杂度就会降低到big-O(h)。尽管前一种实现被称为DFS，后一种实现被称为回溯。

现在你看，如果你正在使用高级语言编程，很可能你实际上是在使用深度优先搜索的方式来执行回溯。此外，对于非常大的问题集跟踪已访问节点可能会占用大量内存；需要谨慎设计get_all_immediate_neighbors（或者可以处理重复访问节点而不会进入无限循环的算法）。

[1] Stuart Russell和Peter Norvig，《人工智能：一种现代方法》，第3版

- KGhatak

---

完全同意。LCN、Reed等人都将DFS称为“树”搜索算法，这太狭窄（如果不是错误的话），会误导初学者。 - Eric

Answer 4

根据Donald Knuth的说法，这是相同的。

回溯算法，也称为深度优先搜索。

这篇论文介绍了Dancing Links算法，该算法用于解决"N皇后"和数独等“非树形”问题。请注意保留所有HTML标签。

- tkrishtop

---

在链接的PDF第一页提到。 - Steve Chavez

Answer 5

回溯算法通常是DFS和搜索剪枝的结合。你按深度优先遍历搜索空间树，途中构建部分解。朴素的DFS可能会构造出所有搜索结果，甚至那些在实际情况下没有意义的结果。构造所有解（n!或2 ^ n）也可能非常低效。因此，在进行DFS时，需要修剪无关上下文的部分解，并专注于导致有效最优解的部分解。这就是实际回溯技术——尽早放弃部分解，退回一步并再次寻找局部最优解。

使用BFS遍历搜索空间树并沿途执行回溯策略没有任何阻碍，但在实践中并没有意义，因为您需要在队列中逐层存储搜索状态，而树的宽度呈指数级增长，所以我们很快就会浪费很多空间。这就是为什么通常使用DFS遍历树。在这种情况下，搜索状态存储在堆栈中（调用堆栈或显式结构），并且不能超过树高。

- twinmind

Answer 6

通常情况下，深度优先搜索是遍历实际图/树结构寻找值的一种方式，而回溯算法则是遍历问题空间以寻找解决方案。回溯算法是一种更为通用的算法，甚至不一定与树相关。

- Eclipse

Answer 7

DFS(深度优先搜索)用于遍历图形，强调在给定条件下尽可能深地探索。

回溯法通常通过DFS实现，更注重尽早修剪不太有前途的搜索子空间。

- Wu-Man

Answer 8

我认为DFS是回溯的一种特殊形式，而回溯则是DFS的一般形式。

如果我们将DFS扩展到一般问题上，我们可以称其为回溯。如果我们在树/图相关问题上使用回溯，我们可以称其为DFS。

从算法角度来看，它们传递了相同的思想。

- Douglas Lear

---

DFS和回溯之间的关系实际上是相反的。请查看我的回复，其中详细说明了这一点。 - KGhatak

Answer 9

我认为深度优先搜索和回溯搜索的区别在于，回溯搜索更加强大。DFS帮助我回答一个节点是否存在于树中，而回溯搜索可以帮助我回答两个节点之间的所有路径。

请注意区别：DFS访问一个节点并将其标记为已访问，因为我们主要是搜索，所以只需看一次即可。回溯搜索多次访问一个节点，因为它是一种课程纠正，因此称为回溯。

大多数回溯问题涉及以下内容：

def dfs(node, visited):
  visited.add(node)
  for child in node.children:
    dfs(child, visited)
  visited.remove(node) # this is the key difference that enables course correction and makes your dfs a backtracking recursion.

- Ultrablendz

---

这是一个很棒的观察！ - J.W.

Answer 10

在回溯的任何特定节点上，您首先尝试深度优先遍历其每个子节点，但在进入任何子节点之前，您需要“清除”先前子节点的状态（此步骤相当于回溯到父节点）。换句话说，每个兄弟节点的状态不应互相影响。

相反，在正常的DFS算法中，通常没有这种约束条件，您不需要清除（回溯）以构造下一个兄弟节点的先前兄弟节点的状态。

- Peiti Li