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

回溯是一种更通用的algorithm。

深度优先search是与search树结构有关的特定forms的回溯。维基百科：

从根开始（select一些节点作为图中的根节点）并在回溯之前尽可能沿每个分支进行探索。

它使用回溯作为其工作手段的一部分，但仅限于树结构。

但是，回溯可以用于任何types的结构，其中部分域可以被消除 – 不pipe它是否是一个逻辑树。维基的例子使用棋盘和一个特定的问题 – 你可以看一个特定的举动，并消除它，然后回到下一个可能的举措，消除它等。

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

对我而言，回溯与DFS的区别在于回溯处理隐式树，DFS处理明确的树。这似乎微不足道，但它意味着很多。当一个问题的search空间被回溯访问时，隐式树会在中间被遍历和修剪。然而，对于DFS，它所处理的树/图是明确构造的，而不可接受的情况在任何search完成之前已经被抛出，即被修剪掉。

所以，回溯是隐式树的DFS，而DFS是没有修剪的回溯。

通常情况下，深度优先search是通过实际graphics/树结构寻找值的迭代方式，而回溯则通过寻找解决scheme的问题空间进行迭代。回溯是一种更一般的algorithm，不一定与树有关。

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

回溯是一个广义的术语，从一个目标的末尾开始，逐渐地向后移动，逐渐构build一个解决scheme。

深度首先是遍历或search树的algorithm。看到这里。回溯是一个更为广泛的术语，无论解决scheme候选人是如何形成的，后来通过回溯到前一个状态而被丢弃。看到这里。深度优先search使用回溯search一个分支（解决scheme的候选人），如果不成功search其他分支。

我会说，DFS是回溯的特殊forms，回溯是DFS的一般forms。

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

他们在algorithm方面有相同的想法。

国际海事组织（IMO）在回溯的任何特定节点上，首先尝试深入分析每个子节点，但在分支到任何子节点之前，需要“清除”前一个子节点的状态（此步骤相当于后退走到父节点）。换句话说，每个兄弟姐妹的状态都不应该互相影响。

相反，在正常的DFSalgorithm中，你通常不会有这个约束，你不需要去除（回溯）前一个同胞的状态，以便构造下一个兄弟节点。