Ree*_*sey 88
回溯是一种更通用的算法.
深度优先搜索是与搜索树结构相关的特定回溯形式.来自维基百科:
一个从根开始(在图形情况下选择一个节点作为根)并在回溯之前尽可能地沿着每个分支进行探索.
它使用回溯作为其使用树的方法的一部分,但仅限于树结构.
但是,回溯可以用于任何类型的结构,其中可以消除域的部分 - 无论它是否是逻辑树.Wiki示例使用棋盘和特定问题 - 您可以查看特定的移动,消除它,然后回溯到下一个可能的移动,消除它,等等.
lcn*_*lcn 23
我认为这个对另一个相关问题的回答提供了更多的见解.
对我来说,回溯和DFS之间的区别在于回溯处理隐式树而DFS处理显式树.这似乎微不足道,但它意味着很多.当通过回溯访问问题的搜索空间时,隐式树在其中间被遍历和修剪.然而对于DFS来说,它处理的树/图是明确构造的,并且在完成任何搜索之前已经抛出(即修剪)不可接受的情况.
因此,回溯是隐式树的DFS,而DFS是回溯而不修剪.
tkr*_*top 13
根据唐纳德·克努斯 (Donald Knuth) 的说法，情况是一样的。这是他关于 Dancing Links 算法的论文的链接，该算法用于解决诸如 N-queens 和数独求解器之类的“非树”问题。
twi*_*ind 12
回溯通常实现为 DFS 加搜索修剪。您一路遍历搜索空间树深度优先构建部分解决方案。蛮力 DFS 可以构建所有搜索结果，甚至是那些实际上没有意义的搜索结果。这对于构建所有解决方案（n！或 2^n）来说也是非常低效的。所以在现实中，当你做 DFS 时，你还需要修剪在实际任务上下文中没有意义的部分解决方案，并专注于部分解决方案，这可以导致有效的最佳解决方案。这是实际的回溯技术 - 您尽可能早地放弃部分解决方案，退后一步并尝试再次找到局部最优。
没有什么可以停止使用 BFS 遍历搜索空间树并沿途执行回溯策略，但这在实践中没有意义，因为您需要在队列中逐层存储搜索状态，并且树的宽度呈指数增长到高度，所以我们会很快浪费很多空间。这就是为什么通常使用 DFS 遍历树的原因。在这种情况下，搜索状态存储在堆栈中（调用堆栈或显式结构）并且它不能超过树的高度。
KGh*_*tak 12
恕我直言，大多数答案要么很大程度上不准确和/或没有任何参考验证。所以让我分享一个非常清晰的解释和参考。
首先，DFS 是一种通用的图遍历（和搜索）算法。所以它可以应用于任何图（甚至森林）。树是一种特殊的图，因此 DFS 也适用于树。本质上，让我们停止说它只适用于一棵树或类似的东西。
基于 [1]，回溯是一种特殊的 DFS，主要用于节省空间（内存）。我即将提到的区别可能看起来令人困惑，因为在这种图形算法中，我们习惯于使用邻接列表表示并使用迭代模式来访问节点的所有直接邻居（对于树来说，它是直接子节点） ，我们经常忽略get_all_immediate_neighbors的错误实现可能会导致底层算法的内存使用差异。
此外，如果图节点具有分支因子 b 和直径 h（对于树，这是树的高度），如果我们在访问节点的每个步骤中存储所有直接邻居，则内存需求将是大 O(bh)。然而，如果我们一次只取一个（直接）邻居并扩展它，那么内存复杂度会降低到big-O(h)。前一种实现称为DFS，后一种称为回溯。
现在您看到了，如果您使用高级语言，很可能您实际上是以 DFS 为幌子使用回溯。此外，跟踪非常大的问题集的访问节点可能会占用大量内存；要求仔细设计get_all_immediate_neighbors（或可以处理重新访问节点而不会陷入无限循环的算法）。
[1] Stuart Russell 和 Peter Norvig，人工智能：现代方法，第 3 版
小智 5
我会说，DFS 是回溯的特殊形式；回溯是 DFS 的一般形式。
如果我们将 DFS 扩展到一般问题，我们可以称之为回溯。如果我们使用回溯来解决树/图相关的问题，我们可以称之为 DFS。
它们在算法方面具有相同的想法。