logo标签列表

动态规划和分治算法

algorithmdynamic-programmingdivide-and-conquer
7
我正在阅读动态规划笔记，并遇到了以下评论。
如果子问题不是独立的，即子问题共享子子问题，则分治算法会重复解决公共的子子问题。因此，它做了比必要更多的工作。
这是什么意思？你能给我举些例子来说明上述观点吗？
1个回答
14

作者指的是许多分治算法具有彼此重叠的子问题。 例如，考虑这个非常简单的斐波那契实现：

int Fibonacci(int n) {
    if (n <= 1) return n;

    return Fibonacci(n - 1) + Fibonacci(n - 2);
}
如果跟踪计算 Fibonacci(4) 的调用，我们得到：
  • Fibonacci(4) 调用 Fibonacci(3) 和 Fibonacci(2)
  • Fibonacci(3) 调用 Fibonacci(2) 和 Fibonacci(1)
  • Fibonacci(2) 调用 Fibonacci(1) 和 Fibonacci(0)
  • 另一个 Fibonacci(2) 调用 Fibonacci(1) 和 Fibonacci(0)
  • Fibonacci(1) 终止。
  • Fibonacci(1) 终止。
  • Fibonacci(1) 终止。
  • Fibonacci(0) 终止。
  • Fibonacci(0) 终止。
换句话说，总共进行了 9 次函数调用，但这里只有五个唯一的调用（Fibonacci 从 0 到 4）。如果递归调用在子问题之间共享而不是每次重新计算，则可以使此算法更加高效。这是动态规划背后的关键思想之一。
为了计算 Fn（第 n 个斐波那契数），上面的代码将进行 2Fn+1 - 1 次递归调用。由于斐波那契数增长得非常快，因此这需要指数级别的工作量。然而，可以利用许多递归调用相同的事实来大大简化这个问题。与其从 Fibonacci(4) 开始递归，然后向下工作，不如从 Fibonacci(0) 开始向上工作。具体而言，我们将构建一个长度为 5 的表（称为 FTable），并将按以下方式填充它：
  • FTable[0] = 0
  • FTable[1] = 1
现在，假设我们想计算 FTable[2]。这要求我们知道 FTable[0] 和 FTable[1]，但因为它们已经在表中了，所以我们可以设置
  • FTable[2] = 1
使用类似的逻辑，我们可以从 FTable[2] 和 FTable[1] 计算出 FTable[3]：
  • FTable[3] = 2
从 FTable[2] 和 FTable[3] 可以计算出 FTable[4]：
  • FTable[4] = 3
请注意，通过仅按相反顺序构建它们，我们避免了进行许多重叠的递归调用！这现在以 O(n) 的时间计算 Fibonacci 数字，比以前快指数级。使用更高级的数学，我们甚至可以做得更好，但是这说明了动态规划如何将不可行的问题变得突然可行。
希望这有所帮助！
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接