logo标签列表

回溯和动态规划的区别

algorithmdata-structures
73

我听说动态规划和回溯的唯一区别在于DP允许子问题重叠，例如：

fib(n) = fib(n-1) + fib (n-2)

这样做正确吗？还有其他的区别吗？

另外，我想知道使用这些技术解决了哪些常见问题。

我也发现这个视频很有启发 https://www.youtube.com/watch?v=Qq4gWBdJ1XQ - deathangel908
8个回答
61
有两种经典的动态规划实现方式：自底向上和自顶向下。 自顶向下动态规划本质上就是普通递归，通过存储中间子问题的解决方案来增强其性能。当出现第二（第三，第四……）个给定子问题时，不会从头开始求解，而是直接使用先前存储的解决方案。这种技术被称为记忆化搜索（在'i'之前没有'r'）。
这实际上就是费波那契数列例子所要说明的内容。只需使用递归公式来计算斐波那契数列，但沿途构建fib(i)值的表格，就可以得到该问题的自顶向下DP算法（例如，如果需要第二次计算fib(5)，则可以直接从表格中获取其值而无需再次计算）。
在自底向上动态规划中，这种方法也基于将子解存储在记忆中，但是它们按不同的顺序（从小到大）求解，并且算法的一般结构不是递归的。 LCS算法是经典的自底向上DP示例。
自底向上DP算法通常更高效，但通常更难（有时不可能）构建，因为不总是容易预测需要解决整个原始问题的基本子问题以及从小子问题到最终解决方案的最有效路径。
18
那么回溯法就是自底向上的动态规划吗？ - mb21
还有另一个精彩的解释... 回溯-记忆化-动态规划 - raksja
62
这并不回答DP与回溯法的不同之处，只是说明了创建DP解决方案的方法。 - DBedrenko
5
这个回答如何回答这个问题以及为什么它受到了如此高的赞同？ - learner
此外，回溯法没有最优子结构的属性。 - Apurva Singh
28

动态问题也需要"最优子结构"。

根据维基百科：

动态规划是一种将复杂问题分解成简单步骤来解决的方法。它适用于表现出 1) 重叠子问题，这些子问题仅略微较小和 2) 最优子结构 属性的问题。

回溯法是一种通用算法，用于找到某些计算问题的所有（或某些）解决方案，它逐步构建候选解，并在确定 c 无法完成有效解时立即放弃每个部分候选解 c（“回溯”）。

有关“最优子结构”的详细讨论，请阅读CLRS书。

我能想到的常见回溯问题有：

  1. 八皇后问题
  2. 地图着色
  3. 数独

DP问题：

  1. 这个麻省理工学院的网站收集了很多动态规划问题，并提供了易懂的动画解释。
  2. 柏克莱大学教授的一章书籍。
15
动态规划和回溯法有什么区别？ - Martin Thoma
11
假设我们有一个解决方案树，其叶子节点是原始问题的解决方案，而非叶子节点是该问题部分的次优解。 我们尝试遍历解决方案树以寻找解决方案。 动态规划更像BFS：我们找到代表非叶子节点的所有可能次优解，并仅在这些非叶子节点下增加一层来扩展树。 回溯法更像DFS：我们尽可能深地扩展树，在一个节点上修剪树，如果该节点下的解决方案不符合预期。
然后从上述理论得出一个推论：动态规划通常比回溯法占用更多空间，因为BFS通常比DFS占用更多空间(O(N) vs O(log N))。实际上，动态规划需要记忆先前步骤中的所有次优解以备后用，而回溯法不需要这样做。
2
在我看来，这应该是被接受的答案。这个解释让我大开眼界！这里的大多数其他答案都是从维基百科复制粘贴而来，没有给出准确回答OP问题。 - Vadim Kirilchuk
BFS：广度优先搜索（探索树的一层，向下走，重复），DFS：深度优先搜索（探索树的一个分支到叶子节点，返回上一级，探索另一个分支，重复）。 - Eric Burel
10

另一个区别可能是动态编程问题通常依赖于最优原则。最优原则指出，在一系列的决策或选择中，每个子序列都必须是最优的。

回溯问题通常在其过程中不是最优的！它们只适用于允许部分候选解概念的问题。

我非常确定，如果不调用“最优原理”，就无法构建DP。动态回溯听起来有点像启发式的应用。 - user968363
8
在我看来，DP和BCKT的区别非常微妙，因为两者都用于探索解决问题的所有可能性。
就目前而言，我看到了两个微小之处：
1. BCKT是一种问题的暴力解决方案。 DP不是一种暴力解决方案。因此，您可以说：DP比BCKT更优化地探索解决方案空间。在实践中，当您想使用DP策略解决问题时，建议首先构建递归解决方案。好吧，那个递归解决方案也可以被认为是BCKT解决方案。
2. 有数百种方法可以"更优化"地探索解决方案空间（欢迎来到优化的世界），但DP之所以成为DP，是因为它在其核心实现数学递推关系，即当前值是过去值的组合（从底部到顶部）。因此，我们可以说，DP之所以成为DP，是因为问题空间满足通过使用递推关系来探索其解空间。如果您基于另一个想法探索解决方案空间，那么那将不是DP解决方案。在任何问题中，问题本身可能会根据问题结构本身使用一种或另一种优化技术。某些问题的结构使DP优化技术可以使用。从这个意义上说，BCKT更通用，尽管并非所有问题都允许使用BCKT。
例如：数独使BCKT能够探索其整个解决方案空间。但是，它不允许使用DP更有效地探索其解决方案空间，因为无法推导出任何递归关系。但是，还有其他优化技术与该问题相匹配，并且可以改善暴力BCKT。
例如：只需获得经典数学函数的最小值。此问题不允许BCKT探索问题的状态空间。
例如：任何可以使用DP解决的问题也可以使用BCKT解决。在这个意义上，问题的递归解决方案可以被认为是BCKT解决方案。
希望这可以有所帮助。
5
DP允许将一个庞大而计算密集的问题分解为子问题，其解决方案仅需要知道前一个解决方案。通过学习Needleman-Wunsch并解决样例问题，您可以很好地理解这个应用。
回溯似乎更加复杂，其中解决方案树被修剪，因为已知特定路径不会产生最优结果。
因此，可以说回溯优化了内存，因为DP假设所有计算都已完成，然后算法通过最低成本节点返回。
我认为，这并不完全适用于DP。在DP中，您不必仅使用“仅”即时先前的解决方案。当前解决方案可以根据情况从其他先前的解决方案构建。在我看来，您在此描述的更像是贪心方法而不是DP。 - stdout
2

简单来说，动态规划是解决优化问题的一种策略。优化问题是指求最小值或最大值（一个结果）。但是，在回溯法中，我们使用暴力方法，不是为了解决优化问题，而是当你有多个结果时，你想要全部或部分结果。

原始答案翻译成中文是最初的回答。

1
这并不完全正确。DP也被用来解决计数问题。例如，UVA在线评测上的10617号问题就是一个使用DP解决的计数问题。 https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1558 - banna
-1

利用边界函数生成状态空间树的深度优先节点生成被称为回溯。在这里，当前节点依赖于生成它的节点。

利用记忆函数生成状态空间树的深度优先节点生成被称为自顶向下动态规划。在这里，当前节点依赖于它所生成的节点。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接