动态规划和分而治之 [英] Dynamic programming and Divide and conquer

问题描述

我在读指出动态规划和我遇到了以下注释。

I was reading notes on Dynamic programming, and I encountered the following comment.

如果子问题是不独立的，即   子问题的份额subsubproblems，然后分而治之算法的多次解决了常见的   subsubproblems。   因此，它不会超过必要的工作

If the subproblems are not independent, i.e. subproblems share subsubproblems, then a divideand-conquer algorithm repeatedly solves the common subsubproblems. Thus, it does more work than necessary

这是什么意思？你能给我的例子做上面的点清楚了吗？

What does this mean ? Can you give me examples to make the above point clear ?

推荐答案

笔者指的是事实，许多分而治之的算法有相互重叠的子问题。举个例子，这个非常简单的斐波那契数的实现：

The author refers to the fact that many divide-and-conquer algorithms have subproblems that overlap with one another. Consider, for example, this very simple Fibonacci implementation:

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

    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

如果您描绘出做计算斐波那契调用（4），我们得到

If you trace out the calls done to compute Fibonacci(4), we get

• 在斐波那契数（4）调用斐波那契（3）和斐波那契数（2）
• 在斐波那契数（3）调用斐波那契（2）和斐波那契（1）
• 在斐波那契数（2）调用斐波那契（1）和斐波那契数（0）
• 斐波（2）（另一种）调用斐波（1）和斐波（0）
• 在斐波那契（1）终止。
• 在斐波那契（1）终止。
• 在斐波那契（1）终止。
• 在斐波那契数（0）结束。
• 在斐波那契数（0）结束。

在换句话说，9总的调用函数，但有只有五个这里唯一的呼叫（0斐波至4，含）。该算法可以作出更有效的，如果递归调用横渡的子共享，而不是每次都从头开始重新计算。这是背后动态规划的主要思路之一。

In other words, 9 total function calls are made, but there's only five unique calls here (Fibonacci of 0 to 4, inclusive). This algorithm could be made much more efficient if the recursive calls were shared across the subproblems rather than recomputed from scratch each time. This is one of the key ideas behind dynamic programming.

要计算˚F<子> N （第n个Fibonacci数），上述code将使总2F <子>的N + 1 - 1递归调用。由于斐波那契数成倍快速增长，这需要成倍大量的工作。然而，这是可以使用的事实，许多递归调用是相同的，大大地简化这一点。而不是开始于斐波那契（4）和工作下来，让我们开始在斐波那契数（0）和工作了。具体来说，我们将建立一个表格（我们称之为FTable）长度为5，将填充它，如下所示：

To compute F_n (the nth Fibonacci number), the above code will make a total of 2F_n+1 - 1 recursive calls. Since the Fibonacci numbers grow exponentially quickly, this requires exponentially much work. However, it's possible to use the fact that many recursive calls are identical to simplify this dramatically. Rather than starting at Fibonacci(4) and working down, let's start at Fibonacci(0) and work up. Specifically, we'll build a table (let's call it FTable) of length 5 and will fill it in as follows:

• FTable [0] = 0
• FTable [1] = 1

现在，假设我们要计算FTable [2]。这就要求我们要知道FTable [0]和FTable [1]，但我们已经知道，因为他们是在表中。因此，我们可以设置

Now, suppose we want to compute FTable[2]. This requires us to know FTable[0] and FTable[1], but we already do know that because they're in the table. We thus can set

• FTable [2] = 1

使用类似的逻辑，我们可以计算FTable [3]从FTable [2]和FTable [1]：

Using similar logic, we can compute FTable[3] from FTable[2] and FTable[1]:

• FTable [3] = 2

和FTable [4]从FTable [2]和FTable [3]

And FTable[4] from FTable[2] and FTable[3]:

• FTable [4] = 3

注意，我们避免了使许多由刚刚建立起来以相反的顺序重叠的递归调用！现在，这在计算时间为O（n），这是指数比以前快了斐波那契数。使用一些更高级的数学运算，我们可以做得比这更好，但这说明了为什么动态规划可以采取不可行的问题，让他们突然可行的。

Notice how we avoided making lots of overlapping recursive calls by just building them up in the reverse order! This now computes Fibonacci numbers in time O(n), which is exponentially faster than before. Using some more advanced math we can do even better than this, but this does illustrate why dynamic programming can take infeasible problems and make them suddenly feasible.

希望这有助于！

这篇关于动态规划和分而治之的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！