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

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

84142 次浏览
小开

通常，深度优先搜索是一种在实际的图/树结构中迭代寻找值的方法，而回溯则是在问题空间中迭代寻找解决方案。回溯是一种更普遍的算法，甚至不一定与树有关。

小开

在 深度优先搜索中，首先从树的根开始，然后沿着每个分支探索，然后从 回溯到每个后续的父节点并遍历它的子节点

回溯 是一个广义的术语，指的是从目标结束时开始，然后逐步向后移动，逐步构建解决方案。

小开
最佳答案

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

深度优先搜索 是与搜索树结构相关的一种特定形式的回溯:

一种是从根开始(在图中选择某个节点作为根) ，在回溯之前尽可能沿着每个分支进行探索。

它使用回溯作为其处理树的方法的一部分，但是仅限于树结构。

然而，回溯可以用于任何类型的结构，在这种结构中，域的某些部分可以被删除——不管它是否是一个逻辑树。Wiki 的例子使用了一个棋盘和一个特定的问题-你可以查看一个特定的移动，并消除它，然后回溯到下一个可能的移动，消除它，等等。

小开

深度优先是一种遍历或搜索树的算法。参见 给你。回溯是一个更为广泛的术语，用于形成解决方案候选方案并随后通过回溯到前一状态而丢弃的任何地方。见 给你。深度优先搜索使用回溯优先搜索一个分支(解决方案候选) ，如果不成功，则搜索另一个分支(es)。

小开

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

对我来说，回溯和 DFS 的区别在于，回溯处理的是一个隐式树，而 DFS 处理的是一个显式树。这看起来微不足道，但意义重大。当通过回溯访问问题的搜索空间时，隐式树在其中被遍历和修剪。然而，对于 DFS，它处理的树/图是显式构造的，不可接受的情况在完成任何搜索之前就已经被丢弃，也就是说被修剪掉了。

因此，对于隐式树，回溯是 DFS，而 DFS 是无需修剪的回溯。

小开

我想说，DFS 是回溯的特殊形式; 回溯是 DFS 的一般形式。

如果我们将 DFS 扩展到一般问题，我们可以称之为回溯。 如果我们使用回溯来解决与树/图相关的问题，我们可以称之为 DFS。

它们在算法方面具有相同的思想。

小开

IMO，在回溯的任何特定节点上，您尝试首先深入分支到它的每个子节点，但是在您分支到任何子节点之前，您需要“清除”以前子节点的状态(这一步相当于返回步行到父节点)。换句话说，每个兄弟状态不应该相互影响。相反，在正常的 DFS 算法中，您通常没有这个约束，您不需要为了构造下一个兄弟节点而删除(回溯)前一个兄弟节点状态。

小开

回溯通常实现为 DFS 加上搜索裁剪。沿途遍历搜索空间树深度优先构造部分解决方案。蛮力 DFS 可以构建所有搜索结果，即使是那些实际上没有意义的结果。构造所有解决方案(n！或2 ^ n)。因此在实际中，当您进行 DFS 时，您还需要修剪部分解决方案，这在实际任务的上下文中是没有意义的，并将重点放在部分解决方案上，这可以导致有效的最优解。这就是实际的回溯技术——尽早丢弃部分解决方案，后退一步，再次尝试找到局部最优解。

在使用 BFS 遍历搜索空间树和执行回溯策略的过程中，没有任何东西停下来，但是这在实践中是没有意义的，因为你需要在队列中一层一层地存储搜索状态，而且树的宽度成指数增长到高度，所以我们会很快地浪费大量的空间。这就是为什么通常使用 DFS 遍历树的原因。在这种情况下，搜索状态存储在堆栈(调用堆栈或显式结构)中，不能超过树高。

小开

想法-从任何一点开始，检查它是否是理想的终点，如果是，那么我们找到了一个解决方案，其他所有可能的位置，如果我们不能走得更远，然后回到以前的位置，并寻找其他替代标记，当前的路径不会带领我们找到解决方案。

现在，回溯和 DFS 是两个不同的名字给出了相同的想法应用于2个不同的抽象数据类型。

如果将这种思想应用到矩阵数据结构中，我们称之为回溯。

如果将同样的思想应用到树或图上，那么我们称之为 DFS。

这里的陈词滥调是，一个矩阵可以转换成一个图，一个图可以转换成一个矩阵。所以，我们实际上应用了这个想法。如果在图上，我们称之为 DFS 如果在矩阵上，我们称之为回溯。

这两种算法的思想是相同的。

小开

根据 Donald Knuth 的说法，是一样的。 下面是他论文中关于 Dancing Links 算法的链接，该算法用于解决 N 皇后和数独等“非树”问题。

回溯，也叫深度优先搜索

小开

DFS 描述了您希望探索或遍历图的方式。它的重点是尽可能深入的概念给予选择。

回溯虽然通常通过 DFS 实现，但更注重尽早删除无希望的搜索子空间的概念。

小开

恕我直言，大多数的答案要么大体上不准确，要么没有任何参考资料可供核实。

首先，DFS 是一种通用的图遍历(和搜索)算法。因此它可以应用于任何图(甚至林)。Tree 是一种特殊的图，因此 DFS 也适用于 Tree。本质上，我们不要再说它只对树或者类似的东西有效。

基于[1] ，回溯是一种特殊的 DFS，主要用于节省空间(内存)。我将要提到的区别可能看起来令人困惑，因为在这种类型的图算法中，我们习惯于使用邻接列表表示，并使用迭代模式访问一个节点的所有直接邻居(对树来说，它是直接的孩子) ，我们常常忽略了一个不好的 把所有的邻居都叫来实现可能会导致底层算法在内存使用上的差异。

此外，如果一个图形节点有分叉率 b 和直径 h (对于一棵树来说，这就是树的高度) ，如果我们在访问一个节点的每个步骤中存储所有的直接邻居，那么内存需求将是 大 O (bh)。但是，如果我们一次只取一个(直接的)邻居并展开它，那么内存复杂性就降低到 大 O (h)。前一种实现称为 < strong > DFS ，后一种实现称为 < strong > Backtrack .

现在您可以看到，如果您使用的是高级语言，那么很可能您实际上以 DFS 的名义使用了回溯。此外，对于一个非常大的问题集，跟踪访问过的节点可能会占用大量内存; 需要对 把所有的邻居都叫来进行仔细的设计(或者算法，这些算法可以在不陷入无限循环的情况下处理重访节点的问题)。

[1]斯图尔特 · 罗素和彼得 · 诺维格，《人工智能: 现代方法》 ，第3版

小开

回溯只是具有特定终止条件的深度优先搜索。

考虑走过一个迷宫，在这个迷宫中，你做出的每一个决定都是对调用堆栈的调用(进行深度优先搜索) ... ... 如果你到达了终点，你可以返回你的路径。但是，如果到达死端，您希望返回某个决策，实质上就是返回调用堆栈上的一个函数。

所以当我想到回溯时，我关心的是

  1. 国务院
  2. 决定
  3. 基本情况(终止条件)

我在回溯 给你的视频中解释过。

下面是对回溯代码的分析。在这个回溯代码中，我希望所有的组合将导致一个特定的和或目标。因此，我有3个决定，调用我的调用堆栈，在每个决定，我可以选择一个数字作为我的路径的一部分，达到目标数字，跳过这个数字，或挑选它，并再次挑选它。然后，如果我达到终止条件，我的回溯步骤正好是 返回。返回是回溯步骤，因为它从调用堆栈上的调用中出来。

class Solution:


"""


Approach: Backtracking


State
-candidates
-index
-target


Decisions
-pick one --> call func changing state: index + 1, target - candidates[index], path + [candidates[index]]
-pick one again --> call func changing state: index, target - candidates[index], path + [candidates[index]]
-skip one --> call func changing state: index + 1, target, path


Base Cases (Termination Conditions)
-if target == 0 and path not in ret
append path to ret
-if target < 0:
return # backtrack


"""


def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
"""
@desc find all unique combos summing to target
@args
@arg1 candidates, list of ints
@arg2 target, an int
@ret ret, list of lists
"""
if not candidates or min(candidates) > target: return []


ret = []
self.dfs(candidates, 0, target, [], ret)
return ret


def dfs(self, nums, index, target, path, ret):
if target == 0 and path not in ret:
ret.append(path)
return #backtracking
elif target < 0 or index >= len(nums):
return #backtracking




# for i in range(index, len(nums)):
#     self.dfs(nums, i, target-nums[i], path+[nums[i]], ret)


pick_one = self.dfs(nums, index + 1, target - nums[index], path + [nums[index]], ret)
pick_one_again = self.dfs(nums, index, target - nums[index], path + [nums[index]], ret)
skip_one = self.dfs(nums, index + 1, target, path, ret)
小开

在我看来，区别在于修剪树木。回溯可以通过检查给定的条件(如果条件不满足)来停止(完成)中间的某个分支的搜索。但是，在 DFS 中，必须到达分支的叶子节点才能确定是否满足条件，因此在到达其叶子节点之前，不能停止搜索某个分支。

小开

深度优先搜索(家庭服务部)和 回溯是两种不同的 寻找和 穿越算法。DFS 更为广泛，用于 图表和 树数据结构，而 DFS 仅限于 树。尽管如此，这并不意味着 DFS 不能在图中使用。它也可以用在图中，但是只能生成 生成树，一个没有循环的树(在同一个顶点有多个边开始和结束)。这就是为什么它仅限于树。
现在回到回溯，DFS 在树数据结构中使用回溯算法，所以在树上，DFS 和回溯是相似的。
因此，我们可以说，它们在树数据结构中是相同的，而在图数据结构中，它们是不相同的。

小开

我看待 DFS 与回溯的方式是，回溯要强大得多。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.

提交答案