反向跟踪和动态编程之间的区别

Question

我听说动态编程和反向跟踪之间的唯一区别是DP允许子问题的重叠.(fib(n)= fib(n-1)+ fib(n-2)).这样对吗 ？还有其他差异吗？我也想知道使用这些技术解决的一些常见问题.

Answer 1

动态编程方法有两种典型的实现方式:从底部到顶部和从顶部到底部.

从上到下的动态编程只不过是普通的递归,通过记忆中间子问题的解决方案得到了增强.当给定的子问题出现在第二(第三,第四......)时间时,它不是从头开始解决的,而是立即使用先前记忆的解决方案.这种技术在名称memoization('i'之前没有'r')下是已知的.

这实际上是你的Fibonacci序列的例子应该说明的.只需使用Fibonacci序列的递归公式,但是fib(i)沿途构建值表,并为此问题得到一个从上到下的DP算法(例如,如果你需要计算fib(5)第二次,你会得到它从表中而不是再次计算).

在从底部到顶部的动态编程中,该方法还基于将子解决方案存储在存储器中,但是它们以不同的顺序(从小到大)求解,并且算法的结果通用结构不是递归的.LCS算法是一个经典的从底部到顶部的DP示例.

从底部到顶部的DP算法通常更有效,但它们通常更难(有时甚至不可能)构建,因为要预测解决整个原始问题所需的原始子问题并不总是很容易,以及从小型子问题中获取哪条路径以最有效的方式获得最终解决方案.

Answer 2

动态问题还需要"最佳子结构".

根据维基百科:

动态编程是一种通过将复杂问题分解为更简单的步骤来解决复杂问题的方法.它适用于具有重叠子问题特性的问题,这些子问题仅略微小且最佳的子结构.

回溯是一种通用算法,用于查找某些计算问题的所有(或某些)解决方案,逐步构建解决方案的候选者,并在确定c不可能完成到c时放弃每个部分候选c("回溯")有效解决方案

有关"最佳子结构"的详细讨论,请阅读CLRS书籍.

我能想到的回溯的常见问题是:

1. 八皇后拼图
2. 地图着色
3. Sodoku？

DP问题:

1. 麻省理工学院的这个网站有很好的DP问题,有很好的动画解释.
2. 伯克利大学教授的一章.

Answer 3

假设我们有一个解树，其叶子节点是原始问题的解，其非叶子节点是部分问题的次优解。我们尝试遍历解决方案树来寻找解决方案。

动态规划更像是BFS：我们找到代表非叶节点的所有可能的次优解，并且只在这些非叶节点下将树生长一层。

回溯更像是 DFS：我们将树尽可能深地生长，如果某个节点下的解不是我们所期望的，则在该节点处修剪该树。

那么从上述理论得出一个推论：动态规划通常比回溯占用更多的空间，因为 BFS 通常比 DFS 占用更多的空间（O(N) vs O(log N)）。事实上，动态规划需要记住上一步中所有的次优解以备后用，而回溯则不需要。

Answer 4

恕我直言，差异非常微妙，因为两者（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解。

希望这个对你有帮助。

Answer 5

DP允许通过将其分解为子问题来解决大的计算密集型问题,其解决方案仅需要知道前一个解决方案.通过选择Needleman-Wunsch并解决样本,您将获得一个非常好的主意,因为它很容易看到应用程序.

在修剪解决方案树的情况下,回溯似乎更复杂,因为已知特定路径不会产生最佳结果.

因此可以说Backtracking优化了内存,因为DP假定所有计算都已执行,然后算法返回步进通过最低成本节点.

Answer 6

另一个不同可能是动态规划问题通常依赖于最优原理。最优性原则指出，决定或选择每个子序列的最优序列也必须是最优的。

回溯问题通常不是最优方法！它们仅适用于接受部分候选解概念的问题。