logo标签列表

理解动态规划的好例子、文章和书籍

algorithmlanguage-agnosticdynamic-programming
41
我无法理解动态规划的原理，但我真的想了解。DP非常强大，它可以解决像这样的问题： 获取数字差异的最小可能总和 那么，你能否向我推荐好的书籍或文章（最好附有真实代码示例），以便解释什么是动态规划？我真的希望首先有简单的例子，然后再深入学习。
你是指“元编程”吗？当我听到“动态编程”时，我想到的是从数据库中提取数据来修改由服务器动态生成的HTML。 - Achilles
递归、分治、回溯等等。 - namco
2
@Achilles：当大多数人使用“动态规划”这个术语时，他们特别是在算法的上下文中，指的是动态规划。 - sepp2k
@Achilles：元编程肯定不是动态编程。 - dfens
14个回答
34

动态规划是一种有用的算法类型，可通过将难题分解为更小的子问题来进行优化。通过存储和重复使用部分解决方案，它成功避免了使用贪心算法的缺点。有两种类型的动态规划：自底向上和自顶向下。

为了能够使用动态规划解决问题，该问题必须具备所谓的最优子结构属性。这意味着，如果将问题分解为一系列子问题，并找到每个子问题的最优解，则通过这些子问题的解决方案可以实现结果解。没有这种结构的问题无法使用动态规划解决。

自顶向下

自顶向下更为人所知的是记忆化。这是一种存储过去计算结果的想法，以避免每次重新计算。

给定一个递归函数，例如：

fib(n) = 0 if n = 0
         1 if n = 1
         fib(n - 1) + fib(n - 2) if n >= 2

我们可以从它的数学形式中轻松地以递归方式编写：

function fib(n)
  if(n == 0 || n == 1)
    n
  else
    fib(n-1) + fib(n-2)

现在，任何有一定编程经验或对算法效率了解一点的人都会告诉你这是个糟糕的主意。原因在于，在每一步中，你必须重新计算 fib(i) 的值，其中 i 是 2..n-2。

一个更高效的例子是存储这些值，创建自顶向下的动态规划算法。

m = map(int, int)
m[0] = 0
m[1] = 1
function fib(n)
  if(m[n] does not exist)
    m[n] = fib(n-1) + fib(n-2)

通过这种方式，我们最多只计算fib(i)一次。

自底向上

自底向上使用了与自顶向下相同的记忆化技术。然而，不同之处在于自底向上使用了比较子问题（称为递推）来优化最终结果。

在大多数自底向上的动态规划问题中，你通常要么试图最小化，要么试图最大化一个决策。在任何给定点上，你会得到两个（或更多）选项，你必须决定哪个对于你正在解决的问题更加优化。然而，这些决策是基于你先前做出的选择。

通过在每个子问题中做出最优决策，你可以确保整体结果最优。

这些问题最困难的部分是找到递推关系来解决你的问题。

为了支付一堆算法教材的费用，你计划抢劫一个有n个物品的商店。问题是你的微型背包最多只能装W千克的东西。知道每个物品的重量（w[i]）和价值（v[i]），你想最大化所有合在一起重量不超过W的被盗物品的价值。对于每个物品，你必须做出二进制选择——取或不取。

现在，你需要找到子问题是什么。作为一个非常聪明的小偷，你意识到给定物品i、最大重量w的情况下，一个给定物品的最大价值可以用m[i,w]来表示。此外，m[0,w]（最多装w千克的0件物品）和m[i,0]（i个物品重量最大为0）的价值将始终等于0。

因此，

m[i, w] = 0 if i = 0 or w = 0
穿上你的思考全脸面罩，你会发现如果你已经装满了尽可能多的重量，除非新物品的重量小于或等于您的最大重量与袋子当前重量之间的差，否则无法考虑新物品。另一种情况是如果它比袋子里的某个物品重量小于或等于，但价值更高，你可能会考虑这个物品。
 m[i, w] = 0 if i = 0 or w = 0
           m[i - 1, w] if w[i] > w
           max(m[i - 1, w], m[i - 1, w - w[i]] + v[i]) if w[i] <= w

这些是上面描述的递归关系式。一旦你有了这些关系式，编写算法就非常容易（而且短小精悍！）。

v = values from item1..itemn
w = weights from item1..itemn
n = number of items
W = maximum weight of knapsack
   
m[n, n] = array(int, int)
function knapsack
  for w=0..W
    m[0, w] = 0
  for i=1 to n
    m[i, 0] = 0
    for w=1..W
      if w[i] <= w
        if v[i] + m[i-1, w - w[i]] > m[i-1, w]
           m[i, w] = v[i] + m[i-1, w - w[i]]
        else
           m[i, w] = m[i-1, w]
      else
        m[i, w] = c[i-1, w]
  
  return m[n, n]

其它资源

  1. 算法导论
  2. 编程挑战
  3. 算法设计手册

示例问题

幸运的是，在竞赛编程中，动态规划已经变得非常流行。请访问UVAJudge上的动态规划，尝试解决一些实践问题，这将测试您实现和找到动态规划问题递归关系的能力。

+1 - 一些自底向上的算法被称为“表格算法”，因为它们基于计算结果的表格。这些表格通常是“反向”计算的，以确保在引用之前完成每个项目。简单的单词换行可以使用这种方法（我认为Sedgewick将其用作示例）。它不被称为“表格换行”，但我认为它是这样的。还有一个表格LR分析算法，如果我没记错，“packrat”基本上是表格LL分析。 - user180247
10
1
在我看来，动态规划并不是将问题分解成更简单的步骤，而是通过存储这些步骤的结果以供后续重复使用，从而避免重复计算等价步骤。 - user180247
@Steve314：那么，告诉维基百科吧（见第一个链接）。这是其中的第一句话。;-) 如果您不打破复杂性，就无法避免重复计算，因为您无法完全摆脱它的整个复杂性。虽然我理解并理解了您的观点，但这实际上是第二步，因为一旦您看到有重复，就可以理解并将其分解因式。然后，可以重构代码以避免重复。 - Will Marcouiller
1
问题是，所有算法范例都涉及将问题分解为更简单的步骤。分治法最接近于简单地陈述必须这样做，但仍包括如何细分的课程。贪心算法更多地关注如何选择首先处理哪个子问题等 - 每种特定范例的独特之处不仅仅在于将问题细分，因为将问题细分是所有范例共同具有的。 - user180247
6

从维基百科的动态规划文章开始

如果你想测试自己，我的在线评测选择如下：

当然，你也可以查看算法家的动态规划类别

你还可以查看好的大学算法课程。

毕竟，如果您无法解决问题，请向 Stack Overflow 提问，因为这里有许多算法爱好者。

5
请参见以下内容：

学习完动态规划后，您可以通过解决UVA问题来提高技能。在UVA的讨论板块中有一些UVA动态规划问题的列表。

此外，维基百科上有一些很好的简单示例。

编辑： 有关此书算法的信息，请参见以下内容：

此外，您还应该了解动态规划中的记忆化。

4
我认为值得一提的是代数动态规划(ADP)。它是动态规划技术的一个启示性演示，并广泛应用于生物信息学社区。此外，Bellman最优原理表述得非常易懂。
传统上，DP是通过例子来教授的：算法用存储中间问题解决方案的表项之间的递归形式表示，然后通过一些情况分析从这个表中构建出整体解决方案。
ADP将问题的分解和情况分析完全与预期的优化目标分离。这允许重用和组合DP算法的不同部分以解决类似的问题。
ADP算法有三个松散耦合的部分：
  • 构建搜索空间（以树文法的形式表述）;
  • 对搜索空间的每个元素打分；
  • 选择我们感兴趣的那些搜索空间元素的目标函数。
所有这些部分都会自动融合在一起，产生有效的算法。
3
这篇文章是了解DP基础知识和如何提高速度的好起点。然后看看该TopCoder文章，它也涵盖了基础知识，但写得不太好。CMU的这个教程也非常好。一旦你理解了这些，你就需要跨越到2D DP阶段去解决你所需要的问题。阅读该Topcoder文章直到包括苹果问题（标为中级）。
您可能还会觉得观看这个MIT视频讲座有用，具体取决于您从视频中掌握事物的能力。
同时请注意，在成功地学习DP之前，您需要对递归有牢固的掌握。DP很难！但真正困难的部分是看到解决方案。一旦您理解了DP概念（上述内容应该可以帮助您），并且有了解题的思路（例如，我对您的问题的回答），然后应用DP并不是那么难，因为DP解决方案通常非常简洁，与易于理解的递归解决方案的迭代版本相差不远。
您还应该查看记忆化，有些人发现它更容易理解，但它通常和DP一样有效。简单解释一下，记忆化将递归函数的结果缓存起来，以避免在未来对相同参数重新计算结果。
2

只有一些问题可以用动态规划来解决

由于没有人提到，应用动态规划算法需要满足以下条件：

  • 重叠子问题。 必须能够将原始问题分解为子问题，使得某些子问题出现多次。与普通递归相比，DP的优势在于每个子问题仅解决一次，并在必要时保存和重复使用结果。换句话说，DP算法以空间换时间。
  • 最优子结构。 必须能够仅使用子问题的最优解来计算子问题的最优解。验证此属性可能需要一些仔细思考。

例子：全源最短路径

作为DP算法的典型例子，考虑使用Floyd-Warshall算法查找图中所有顶点对之间的最短路径长度。

假设有n个编号为1到n的顶点。虽然我们想计算一个函数d(a, b)，即顶点a和b之间最短路径的长度，但很难从函数d()的其他值中高效计算出这个值。

让我们引入第三个参数c，并定义d(a, b, c)为仅访问范围在1到c之间的顶点的a和b之间最短路径的长度。（不需要访问所有这些顶点。）虽然这似乎是一个无意义的约束，但请注意我们现在有以下关系：

d(a, b, c) = min(d(a, b, c-1), d(a, c, c-1) + d(c, b, c-1))

上面min()的2个参数显示了2种可能情况。只使用顶点1到c的最短路径从a到b的最短方式要么是：

  1. 避免使用c（在这种情况下，它与仅使用前c-1个顶点的最短路径相同），或者
  2. 通过c。 在这种情况下，此路径必须是从a到c的最短路径，后跟从c到b的最短路径，两个路径都受限于只访问范围内的顶点1到c-1之间。 我们知道，如果这种情况（通过c）更短，则这两条路径不能访问任何相同的顶点，因为如果它们这样做，跳过它们之间的所有顶点（包括c）仍然会更短，因此将选择第1种情况。

这种表述满足最优子结构属性——只需要知道子问题的最优解即可找到更大问题的最优解。（并非所有问题都具有这个重要属性——例如，如果我们想要找到所有顶点对之间的最长路径，则此方法会失效，因为从a到c的最长路径可能会访问也被从c到b的最长路径访问的顶点。）

知道上述函数关系和边界条件d(a, b, 0)等于a和b之间的边的长度（如果不存在这样的边，则为无限大），就可以计算每个值d(a, b, c)，从c=1开始，一直到c=n。 d(a, b, n)是可以访问中间任何顶点的a和b之间的最短距离——我们要寻找的答案。

1

如果你想学习算法，我发现MIT有一些非常优秀的讲座视频可供观看。

例如，6.046J / 18.410J 算法导论 (SMA 5503) 看起来是一个不错的选择。

该课程涵盖了动态规划等许多有用的算法技术。个人认为所使用的书籍也非常出色，对于任何认真学习算法的人来说都值得购买。

此外，该课程还附带了一系列作业等，因此您将有机会将理论付诸实践。

相关问题：

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