Dynamic Programming 动态规划
目录

1. 动态规划与分治法

动态规划通常应用于最优化问题。 最优化问题指把n维空间的每个可行解,通过一个评价函数,得到一个值。而值最大(或最小)的解就称为一个最优解。

最优解问题经常要做出一组选择以达到一个最优解。 在选择的同时,经常出现同样形式的子问题。 当某一特定的子问题可能出自于多于一种选择的集合时,动态规划很有有效的; 关键技术是存档这些子问题的每一个解,以备它重复出现。 这样可以将指数时间的算法转化为多项式时间的算法。

分治法一样,动态规划是通过组合子问题的解而解决整个问题的解。 但分治法是将问题划分成一些独立的子问题,递归地求解各子问题,然后合并子问题的解而得到原问题的解。 而动态规划适用于子问题不是独立的情况,也就是各子问题包含公共的子子问题^1。 这种问题分治法会重复计算公共的子子问题。 动态规划算法对每个子子问题只求解一次,将其结果保存在一张表中,从而避免每次遇到各子问题时重新计算答案。

2. 一般步骤

动态规划算法的设计可以分为如下4个步骤:

  1. 描述最优解的结构。
  2. 递归定义最优解的值。
  3. 按自底向上的方式计算最优解的值。
  4. 由计算结果构造一个最优解的值。(可选,要在第3步中加一些附加信息)

3. 算法需求

什么样的问题适合采用动态规划算法? 这有两个要素:最优子结构重叠子问题

最优子问题

分治法中已经说过,如果问题的一个最优解中包含了子问题的最优解,则该问题具有最优子结构。 如果问题包含这样的结构,那就说明动态规划或贪心算法可能适用的。 在动态规划中,我们利用子问题的最优解来构造问题的一个最优解。

非正式地,一个动态规划算法的运行时间依赖于两个因素的乘积:子问题的总个数每一个子问题中有多少选择。 在矩阵链乘法中,总共有Θ$(n^2)$个子问题,在每个子问题中又有n-1个选择,因此执行时间是$O(n^3)$。

动态规划以自底向上的方式利用最优子结构。也就是说,首先找到子问题的最优 解,解决子问题,然后找到问题的一个最优解。寻找问题的一个最优解需要在子 问题中做出选择,即选择将用哪一个来求解问题。问题解的代价通常是子问题的 代价加上选择本身带来的开销。

虽然贪心算法也适用于最优子结构,但是其是以自顶向下方式使用最优子结构的。

重叠子问题

适用于动态规划求解的最优化问题必须具有的第二个要素是子问题的空间要很小, 也就是用来解原文题的递归算法可以返回地解同样的子问题,而不是总产生子问题。 典型的,不同的子问题数是输入规模的一个多项式。 当一个递归算法不断的调用同一个问题时,我们说该最优问题包含重叠子问题。 相反地,适合用分治法解决的问题往往在递归的每一步都产生全新的问题。 动态规划算法充分利用重叠子问题,即通过每个子问题只解一次,把解保存在一个在需要时就可以查到的表中,而每次查表的时间为常数。

自顶向下的动态规划

前面所述的动态规划都是自底向上。我们可以对上面的方法进行变形,用一个表 记录已解决的子问题。当使用自顶向下的递归算法时,遇到子问题,先查表,如 已经解决就直接使用,否则计算新的子问题加入表中。

在实际应用中,如果所有的子问题都只少要被计算一次,则自底向上的方法好一 个常数因子,因为省取了递归和维护表的代价。而有些的问题的子问题没必要全 部求解,则自顶向下的方法它的有优点。

4. 问题举例

  • 装配线调度
  • 矩阵链乘法,表达式极值

发表评论