回溯算法和深度优先搜索有什么区别?
我认为另一个相关问题的这个答案提供了更多深入的见解。
对于我来说,回溯和DFS之间的区别在于回溯处理隐式树而DFS处理显式树。这似乎微不足道,但意义重大。当回溯访问问题的搜索空间时,隐式树会被遍历和剪枝。然而,对于DFS,它所处理的树/图是明确构建的,不可接受的情况已在任何搜索之前被抛弃,即被剪枝掉。
因此,回溯是针对隐式树的DFS,而DFS则是没有剪枝的回溯。
在我看来,大多数答案要么非常不精确,要么没有任何参考资料可以验证。所以让我分享一份带有参考的非常清晰的解释。
首先,DFS是一种通用的图遍历(和搜索)算法。因此它可以应用于任何图形(甚至森林)。树是图的一种特殊形式,因此DFS也适用于树。本质上,让我们停止说它只适用于树或类似的情况。
根据[1],回溯是一种特殊的DFS,主要用于节省空间(内存)。我即将提到的区别可能会令人困惑,因为在这种类型的图算法中,我们习惯于使用邻接列表表示和迭代模式来访问节点的所有直接相邻节点(对于树来说就是子节点),我们经常忽略一个糟糕的获取所有直接相邻节点实现可能导致底层算法的内存使用差异。
此外,如果图节点具有分支因子b和直径h(对于树来说这是树高度),如果我们在访问节点时存储所有直接相邻节点,内存要求将是big-O(bh)。然而,如果我们一次只取一个(直接的)相邻节点并扩展它,那么内存复杂度就会降低到big-O(h)。尽管前一种实现被称为DFS,后一种实现被称为回溯。
现在你看,如果你正在使用高级语言编程,很可能你实际上是在使用深度优先搜索的方式来执行回溯。此外,对于非常大的问题集跟踪已访问节点可能会占用大量内存;需要谨慎设计get_all_immediate_neighbors(或者可以处理重复访问节点而不会进入无限循环的算法)。
[1] Stuart Russell和Peter Norvig,《人工智能:一种现代方法》,第3版
根据Donald Knuth的说法,这是相同的。
这篇论文介绍了Dancing Links算法,该算法用于解决"N皇后"和数独等“非树形”问题。请注意保留所有HTML标签。
通常情况下,深度优先搜索是遍历实际图/树结构寻找值的一种方式,而回溯算法则是遍历问题空间以寻找解决方案。回溯算法是一种更为通用的算法,甚至不一定与树相关。
DFS(深度优先搜索)用于遍历图形,强调在给定条件下尽可能深地探索。
回溯法通常通过DFS实现,更注重尽早修剪不太有前途的搜索子空间。
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.