【每日一题】- 2020-06-01 - 深度优先遍历和回溯的关系？

[azl397985856]

深度优先遍历的范围更大还是回溯的范围更大？为什么？

[unclegem]

我的理解是：dfs是回溯思想的一种体现

• 回溯：是在整个搜索空间中搜索出可行解，在搜索过程中不断剪枝回退，这是回溯的思想，这个搜索空间并没有限制于特定的数据结构。
• dfs：dfs是指特定的数据结构中如图，树（特殊的图）中搜索答案，范围限制在了特定的数据结构。

个人拙见。

[Liu821218213]

关系：回溯法中用到了DFS的搜索方式，DFS也体现了回溯的思想

• 深度优先搜索：DFS
  在一个搜索空间（可以是树，也可以是图）的状态空间树上进行搜索，从根节点开始沿着左子树搜索，搜索到叶子节点会回溯到上一个父节点，然后再搜索该父节点的右子树，以这种方式搜索完整个树。深度优先搜索通常是搜索完整个树，但是也可以加上限制调节，得到第一个解即返回，这样的话，DFS在某种意义上就是回溯法。

• 回溯法
  回溯法是按照深度优先搜索的方式进行搜索，如果当前搜索路径上已经没有解，则进行回溯，然后继续搜索。

区别：

其实没必要硬去区分它们的区别，我觉得只是这两种方式强调的思想不一样。
DFS更强调搜索方式
而回溯法更强调回溯的策略（也即剪枝的策略），让搜索方式更优，搜索的更快。
因此，回溯搜索的范围更小。

[stale]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.