动态规划 gaunthan Posted on Aug 7 2016 ? Algorithm Design Techniques ? ## 概述 **动态规划**(dynamic programming)与**[分治法](http://leanote.com/blog/post/58a7b354ab6441489f003b6f)**(divide and conquer)相似,都是通过组合子问题的解来求解原问题。分治法将问题划分为互不相交的子问题,递归地求解子问题,再将它们的解组合起来,求出原问题的解。与此相反,动态规划应用于子问题重叠的情况,即不同的子问题具有公共的子子问题(子问题的求解是递归进行的,将其划分为更小的子子问题)。在这种情况下,分治算法会做许多不必要的工作,它会反复地求解那些公共子子问题。而动态规划算法对每个子子问题只求解一次,将其解保存在一个表格中,从而无需每次求解一个子子问题时都要重新计算,避免了这种不必要的计算工作。 动态规划方法通常用来求解**最优化问题**(optimization problem)。这类问题可以有很多可行解,每个解都有一个值,我们希望寻找具有最优值(最小值或最大值)的解。我们称这样的解为问题的**一个最优解**(an optimal solution),而不是**最优解**(the optimal solution),因为可能有多个解都达到最优值。 通常按如下4个步骤来设计一个动态规划算法: 1. 刻画一个最优解的结构特征。 2. 递归地定义最优解的值。 3. 计算最优解的值,通常采用自底向上的方法。 4. 利用计算出的信息构造一个最优解。 步骤1~3是动态规划算法求解问题的基础。如果我们仅仅需要一个最优解的值,而非解本身,可以忽略步骤4。如果确实要做步骤4,有时就需要在执行步骤3的过程中维护一些额外信息,以便用来构建一个最优解。 动态规划有两种等价的实现方法: * 带备忘的自顶向下法 * 自底向上法 两种方法得到的算法具有相同的渐进运行时间,仅有的差异是在某些特殊情况下,自顶向下方法并未真正递归地考察所有可能的子问题。由于没有频繁的递归函数调用的开销,自底向上方法的时间复杂性函数通常具有更小的系数。 ## 带备忘的自顶向下法 **带备忘的自顶向下法**(top-down with memoization)按自然的递归形式编写过程,但过程会保存每个子问题的解(通常保存在一个数组或散列表中)。当需要一个子问题的解时,过程首先检查是否已经保存过此解。如果是,则直接返回保存的值,从而节省了计算时间;否则,按通常方式计算这个子问题,然后保存该子问题的解。 ## 自底向上法 **自底向上法**(bottom-up method)一般需要恰当定义子问题的“规模”的概念,使得任何子问题的求解都只依赖于“更小的”子问题的求解。因而我们可以将子问题按规模排序,按由小至大的顺序进行求解。当求解某个子问题时,它所依赖的那些更小的子问题都已求解完毕,结果已经保存。每个子问题只需求解一次,当我们求解它(也是第一次遇到它)时,它的所有前提子问题都已求解完成。 ## 子问题图 当思考一个动态规划问题时,应该弄清所涉及的子问题及子问题之间的依赖关系。 问题的**子问题图**准确地表达了这些信息。子问题图是一个有向图,每个顶点唯一地对应一个子问题。若求子问题x的最优解时需要直接用到子问题y的最优解,那么在子问题图中就会有一条从子问题x的顶点到子问题y的顶点的有向边。我们可以将子问题图看作自顶向下递归调用树的“简化版”或收缩版,因为树中所有对应相同子问题的结点合并为图中单一顶点,相关的所有边都从父结点指向子结点。 子问题图的一个示意如下:  自底向上的动态规划方法处理子问题图中顶点的顺序为:对于一个给定的子问题x,在求解它之前求解邻接至它的子问题y。自底向上动态规划算法是按**逆拓扑序**(reverse topological sort)或**反序的拓扑序**(topological sort of the transpose)来处理子问题图中的顶点。换句话说,对于任何子问题,直至它依赖的所有子问题均已求解完成,才会求解它。类似地,我们可以用**深度优先搜索**(depth-first search)来描述(带备忘机制的)自顶向下动态规划算法处理子问题的顺序。 子问题图$G = (V, E)$的规模可以帮助我们确定动态规划算法的运行时间。由于每个子问题只求解一次,因此算法运行时间等于两个子问题求解时间之和。通常,一个子问题的求解时间与子问题图中对应顶点的出度(出射边的数目)成正比,而子问题的数目等于子问题图的顶点数。因此,通常情况下,动态规划算法的运行时间与顶点和边的数量呈线性关系。 ## 钢条切割问题 ### 描述 给定一段长度为n英寸的钢条和一个价格表$p_i(i = 1, 2, ···, n)$,求切割钢条方案,使得销售收益$r_n$最大。注意,如果长度为n英寸的钢条的价格$p_n$足够大,最优解可能就是完全不需要切割。 ### 分析 长度为n英寸的钢条共有$2^{n-1}$种不同的切割方案,因为在距离钢条左端$i(i = 1, 2, ···, n-1)$英寸处,总是可以选择切割或不切割。如果用普通的加法符号表示切割方案,那么如果一个最优解将钢条切割为k段($1 \le k \ge n$),则最优解切割方案为 $$n = i_1 + i_2 + ··· + i_k $$ 将钢条切割为长度分别为$i_1,i_2,···,i_k$的小段,得到最大收益 $$r_n = p_{i_1} + p_{i_2} + ··· + p_{i_k}$$ 更一般地,对于$r_n(n \ge 1)$,我们可以用更短的钢条的最优切割收益来描述它: $$r_n = max(p_n,r_1 + r_{n-1},r_2 + r_{n-2},···,r_{n-1} + r_1) $$ 第一个参数$p_n$对应不切割,直接出售长度为n英寸的钢条的方案。其他n-1个参数对应另外n-1种方案:对每个$i(i = 1, 2, ···, n-1)$,首先将钢条切割为长度为$i$和$n-i$的两段,接着求解这两段的最优切割收益$r_i$和$r_{n-i}$(每种方案的最优收益为两段的最优收益之和)。由于无法预知哪种方案会获得最优收益,我们必须考察所有可能的$i$,选取其中收益最大者。如果直接出售原钢条会获得最大收益,我们当然可以选择不做任何切割。 注意到,为了求解规模为n的原问题,我们先求解形式完全一样,但规模更小的子问题。即当完成首次切割后,我们将两段钢条看成两个独立的钢条切割问题实例。通过组合两个相关子问题的最优解,并在所有可能的两段切割方案中选取组合收益最大者,构成原问题的最优解。 钢条切割问题满足**最优子结构**(optimal substructure)性质:问题的最优解由相关子问题的最优解组合而成,而这些子问题可以独立求解。 ### 自顶向下递归实现 除了上述求解方法外,钢条切割问题还存在一种相似的但更为简单的递归求解方法:我们将钢条从左边切割下长度为i的一段,只对右边剩下的长度为n-i的一段继续进行切割(递归求解),对左边的一段则不再进行切割。这样,不做任何切割的方案就可以描述为:第一段的长度为n,收益为$p_n$,剩余部分长度为0,对应的收益为$r_0 = 0$。于是可以得到上面公式的简化版本: $$r_n = max(p_i + r_{n-i})$$ 在此公式中,原问题的最优解只包含一个相关子问题的解,而不是两个。伪代码描述见下: ``` CUT-ROD(p, n) if n == 0 return 0 q = -∞ for i = 1 to n q = max(q, p[i] + CUT-ROD(p, n - i)) return q ``` 假设$T(n)$表示第二个参数值为0时CUT-ROD的调用次数,此值等于递归调用树中根为n的子树中的结点总数,注意,此值包含了根结点对应的最初的一次调用。因此$T(0) = 1$,且 $$T(n) = 1 + \sum_{j=0}^{n-1}T(j)$$ 容易证明CUT-ROD的运行时间效率$T(n)\in2^n$。 ### 使用动态规划方法 可以看到,朴素递归算法效率很低,因为它反复求解相同的子问题。因此,动态规划方法仔细安排求解顺序,对每个子问题只求解一次,并将结果保存下来。如果随后再次需要子问题的解,只需查找保存的结果,而不必重新计算。因此,动态规划方法是付出额外的内存空间来节省计算时间,是典型的**时空权衡**(time-memory trade-off)的例子。而时间上的节省可能是非常巨大的:可能将一个指数时间的解转化为一个多项式时间的解。如果子问题的数量是输入规模的多项式函数,而我们可以在多项式时间内求解出每个子问题,那么动态规划方法的总运行时间就是多项式阶的。 #### 加入备忘机制 下面给出的是自顶向下CUT-ROD过程的伪代码,加入了备忘机制: ```cpp MEMOIZED-CUT-ROD(p, n) let r[0..n] be a new array for i = 0 to n r[i] = -∞ return MEMOIZED-CUT-ROD-AUX(p, n, r) MEMOIZED-CUT-ROD-AUX(p, n, r) if r[n] >= 0 return r[n] if n == 0 q = 0 else q = -∞ for i = 1 to n q = max(q, p[i] + MEMOIZED-CUT-ROD-AUX(p, n - i, r)) r[n] = q return q ``` #### 自底向上版本 自底向上版本更为简单: ``` BOTTOM-UP-CUT-ROD(p, n) let r[0..n] be a new array r[0] = 0 for j = 1 to n q = -∞ for i = 1 to j q = max(q, p[i] + r[j - i]) r[j] = q return r[n] ``` 自底向上版本BOTTOM-UP-CUT-ROD采用子问题的自然顺序:若$i<j$,则规模为$i$的子问题比规模为$j$的子问题“更小”。因此,过程依次求解规模为$j = 0, 1, ···, n$的子问题。 自底向上算法和自顶向下算法具有相同的渐进运行时间,都属于$\theta(n^2)$。 ### 重构解 前文给出的钢条切割问题的动态规划算法返回最优解的收益值,但并未返回解本身(一个长度列表,给出切割后每段钢条的长度)。我们可以扩展动态规划算法,使之对每个子问题不仅保存最优收益值,还保存对应的切割方案。利用这些信息,就能输出最优解。实际的做法是: ``` EXTENDED-BOTTOM-UP-ROD(p, n) let r[0..n] and s[0..n] be new arrays r [0] = 0 for j = 1 to n q = -∞ for i = 1 to j if q < p[i] + r[j - i] q = p[i] + r[j - i] s[j] = i r[j] = q return r and s ``` ## References - MarkAllenWeiss, 韦斯. 数据结构与算法分析:C语言描述[M]. 机械工业出版社, 2010. - ThomasH.Cormen. 算法导论[M]. 机械工业出版社, 2013. - [【算法】动态规划问题集锦与讲解](https://segmentfault.com/a/1190000004498566). 赏 Wechat Pay Alipay 并发问题 Orange Pi Lite新手指南