blocks|key|1474846|text|我认为this+answer对另一个相关问题提供了更多的见解。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1474847|对我来说，回溯和DFS的区别在于回溯处理的是隐式树，而DFS处理的是显式树。这看似微不足道，但却意义重大。当通过回溯访问问题的搜索空间时，隐式树在其中间被遍历和修剪。然而，对于DFS，它处理的树/图是显式构造的，在完成任何搜索之前，不可接受的情况已经被抛出，即被修剪掉。|1474848|因此，回溯是隐式树的DFS，而DFS是不修剪的回溯。|1474849|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/a/3156208/2073130^0|3|B|0|0|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@$A|Q|B|R|1|S]]|C|$]]|$1|D|3|E|5|6|7|T|8|@]|9|@]|C|$]]|$1|F|3|G|5|6|7|U|8|@]|9|@]|C|$]]|$1|H|3|-4|5|6|7|V|8|@]|9|@]|C|$]]]|I|$J|$5|K|L|M|C|$N|O]]]]

I think <a href="https://stackoverflow.com/a/3156208/2073130">this answer</a> to another related question offers more insights.

For me, the difference between backtracking and DFS is that backtracking handles an implicit tree and DFS deals with an explicit one. This seems trivial, but it means a lot. When the search space of a problem is visited by backtracking, the implicit tree gets traversed and pruned in the middle of it. Yet for DFS, the tree/graph it deals with is explicitly constructed and unacceptable cases have already been thrown, i.e. pruned, away before any search is done.

So, backtracking is DFS for implicit tree, while DFS is backtracking without pruning.

blocks|key|1474992|text|回溯通常被实现为DFS加上搜索修剪。您遍历搜索空间树深度优先，一路上构建部分解决方案。暴力DFS可以构建所有搜索结果，即使是那些在实际中没有意义的搜索结果。这也可能是非常低效的构造所有的解决方案(n！或2%5En)。因此，在实际执行DFS时，您还需要删除在实际任务上下文中没有意义的部分解决方案，并将重点放在部分解决方案上，这可能会导致有效的最优解。这就是实际的回溯技术--你尽可能早地丢弃部分解，后退一步，然后再次尝试找到局部最优。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1474993|使用BFS遍历搜索空间树并在此过程中执行回溯策略是没有任何意义的，但这在实践中没有意义，因为您需要在队列中逐层存储搜索状态，并且树的宽度呈指数级增长到高度，因此我们很快就会浪费大量空间。这就是为什么通常使用DFS遍历树的原因。在这种情况下，搜索状态存储在堆栈(调用堆栈或显式结构)中，并且不能超过树的高度。|1474994|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

Backtracking is usually implemented as DFS plus search pruning. You traverse search space tree depth-first constructing partial solutions along the way. Brute-force DFS can construct all search outcomes, even the ones, that do not make sense practically. This can be also very inefficient to construct all solutions (n! or 2^n). So in reality as you do DFS, you need to also prune partial solutions, which do not make sense in context of the actual task, and focus on the partial solutions, which can lead to valid optimal solutions. This is the actual backtracking technique - you discard partial solutions as early as possible, make a step back and try to find local optimum again.

Nothing stops to traverse search space tree using BFS and execute backtracking strategy along the way, but it doesn't make sense in practice because you would need to store search state layer by layer in the queue, and tree width grows exponentially to the height, so we would waste a lot of space very quickly. That's why trees are usually traversed using DFS. In this case search state is stored in the stack (call stack or explicit structure) and it can't exceed tree height.

blocks|key|1474677|text|通常，深度优先搜索是在实际的图/树结构中迭代查找值的一种方式，而回溯是在问题空间中迭代查找解决方案。回溯是一种更通用的算法，甚至不一定与树相关。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1474678|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Usually, a depth-first-search is a way of iterating through an actual graph/tree structure looking for a value, whereas backtracking is iterating through a problem space looking for a solution. Backtracking is a more general algorithm that doesn't necessarily even relate to trees.

blocks|key|1260255|text|我想说，DFS是回溯的特殊形式；回溯是DFS的一般形式。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1260256|如果我们将DFS扩展到一般问题，我们可以称之为回溯。如果我们使用回溯来解决树/图相关的问题，我们可以称之为DFS。|1260257|它们在算法方面具有相同的思想。|1260258|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

I would say, DFS is the special form of backtracking; backtracking is the general form of DFS.

If we extend DFS to general problems, we can call it backtracking.
If we use backtracking to tree/graph related problems, we can call it DFS.

They carry the same idea in algorithmic aspect.

blocks|key|1475084|text|DFS描述了浏览或遍历图的方式。它侧重于在有选择的情况下尽可能深入的概念。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1475085|回溯，虽然通常是通过DFS实现的，但更多地关注于尽早修剪没有希望的搜索子空间的概念。|1475086|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

DFS describes the way in which you want to explore or traverse a graph. It focuses on the concept of going as deep as possible given the choice.

Backtracking, while usually implemented via DFS, focuses more on the concept of pruning unpromising search subspaces as early as possible.

blocks|key|1260145|text|深度优先是一种遍历或搜索树的算法。参见here。回溯是一个更宽泛的术语，无论何时形成解决方案候选，然后通过回溯到以前的状态而被丢弃。参见here。深度优先搜索使用回溯首先搜索一个分支(候选解决方案)，如果不成功，则搜索其他分支。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1260146|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Depth-first_search|1|http://en.wikipedia.org/wiki/Backtracking^0|J|4|0|1W|4|1|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@$A|O|B|P|1|Q]|$A|R|B|S|1|T]]|C|$]]|$1|D|3|-4|5|6|7|U|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]|L|$5|G|H|I|C|$J|M]]]]

Depth first is an algorithm for traversing or searching a tree. See <a href="http://en.wikipedia.org/wiki/Depth-first_search" rel="nofollow noreferrer">here</a>. Backtracking is a much more broad term that is used whereever a solution candidate is formed and later discarded by backtracking to a former state. See <a href="http://en.wikipedia.org/wiki/Backtracking" rel="nofollow noreferrer">here</a>. Depth first search uses backtracking to search a branch first (solution candidate) and if not successful search the other branch(es).

blocks|key|1474943|text|在回溯的任何特定节点上，您尝试首先深入分支到其每个子节点，但在分支到任何子节点之前，您需要“清除”上一个子节点的状态(此步骤相当于反向遍历到父节点)。换句话说，每个同级状态不应该相互影响。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1474944|相反，在正常的DFS算法中，你通常没有这个约束，你不需要为了构造下一个兄弟节点而清除(回溯)上一个兄弟节点的状态。|1474945|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

IMO, on any specific node of the backtracking, you try to depth firstly branching into each of its children, but before you branch into any of the child node, you need to "wipe out" previous child's state(this step is equivalent to back walk to the parent node). In other words, each siblings state should not impact each other. On the contrary, during normal DFS algorithm, you don't usually have this constraint, you don't need to wipe out(back track) previous siblings state in order to construct next sibling node.

blocks|key|1260426|text|想法-从任何点开始，检查它是否是所需的终点，如果是，那么我们找到了一个解决方案，否则将到达所有下一个可能的位置，如果我们不能继续前进，则返回到前一个位置，并寻找其他替代方案，标记为当前路径不会引导我们到达该解决方案。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1260427|现在，回溯和DFS是两个不同的名称，应用于两个不同的抽象数据类型上的相同概念。|1260428|如果将这个想法应用于矩阵数据结构，我们称之为回溯。|1260429|如果将同样的思想应用于树或图，那么我们称之为DFS。|1260430|这里的陈词滥调是，矩阵可以转换为图形，图形可以转换为矩阵。所以，我们实际应用了这个想法。如果在图上，我们称其为DFS，如果在矩阵上，则我们称其为回溯。|1260431|这两种算法的思想是相同的。|1260432|entityMap^0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|O|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|P|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|Q|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|R|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|S|8|@]|9|@]|A|$]]|$1|L|3|-4|5|6|7|T|8|@]|9|@]|A|$]]]|M|$]]

Idea - Start from any point, check if its the desired endpoint, if yes then we found a solution else goes to all next possible positions and if we can't go further then return to the previous position and look for other alternatives marking that current path wont lead us to the solution.

Now backtracking and DFS are 2 different names given to the same idea applied on 2 different abstract data types. 

If the idea is applied on matrix data structure we call it backtracking.

If the same idea is applied on tree or graph then we call it DFS.

The cliche here is that a matrix could be converted to a graph and a graph could be transformed to a matrix. So, we actually apply the idea. If on a graph then we call it DFS and if on a matrix then we call it backtracking.

The idea in both of the algorithm is same.

blocks|key|1260571|text|在我看来，不同之处在于修剪树木。回溯可以通过检查给定的条件(如果不满足条件)来停止(完成)搜索中间的某个分支。然而，在DFS中，您必须到达分支的叶节点才能确定条件是否满足，因此在到达某个分支的叶节点之前，您不能停止搜索。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1260572|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

In my opinion, the difference is pruning of tree. Backtracking can stop (finish) searching certain branch in the middle by checking the given conditions (if the condition is not met). However, in DFS, you have to reach to the leaf node of the branch to figure out if the condition is met or not, so you cannot stop searching certain branch until you reach to its leaf nodes.

blocks|key|1475270|text|我对DFS和回溯的看法是，回溯要强大得多。DFS可以帮助我回答树中是否存在节点，而回溯可以帮助我回答两个节点之间的所有路径。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1475271|注意不同之处:+DFS访问一个节点并将其标记为已访问，因为我们主要是在搜索，所以只看到一次就足够了。回溯多次访问一个节点，因为它是一种路线修正，因此得名回溯。|1475272|大多数回溯问题都涉及：|1475273|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.|code-block|syntax|javascript|1475274|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|N|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|O|8|@]|9|@]|A|$]]|$1|F|3|G|5|H|7|P|8|@]|9|@]|A|$I|J]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

The way I look at DFS vs. Backtracking is that backtracking is much more powerful. DFS helps me answer whether a node exists in a tree, while backtracking can help me answer all paths between 2 nodes.
Note the difference: DFS visits a node and marks it as visited since we are primarily searching, so seeing things once is sufficient. Backtracking visits a node multiple times as it's a course correction, hence the name backtracking.
Most backtracking problems involve:
<pre><code>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.
</code></pre>

What's the difference between backtracking and depth first search?

What's the difference between backtracking and depth first search?

数据结构

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

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

回答 10

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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

回答 10

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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