depth-first-search - DFS和回溯有什么区别

Question

我对 DFS 和回溯算法的区别感到困惑。在我看来，Backtracking 只是一个特殊版本的 DFS，对吗？

Answer 1

回溯算法递归遍历搜索树，从根向下，按深度优先顺序。在每个节点 c，算法检查 c 是否可以完成以得到有效的解决方案。 如果不能，则跳过以 c 为根的整个子树(修剪)。否则，算法检查 c 本身是否是一个有效的解决方案，如果是，则将其报告给用户；并递归枚举c的所有子树。两个测试和每个节点的子节点由用户给定的过程定义。

深度优先搜索 (DFS) 从根开始(在图的情况下选择任意节点作为根)并尽可能远地探索回溯前的每个分支。