算法导论第十五章——动态规划

动态规划与分治算法类似，通过组合子问题的解来求解原问题，不同的是，分治通常是将原问题划分为互不相交的子问题，而动态规划常用于子问题重叠的情况，即不同的子问题通常具有相同的子子问题，如此，使用分治时会产生大量的重复计算。

动态规划算法通常用求解最优化问题，常用如下四个步骤来设计一个动态规划算法

刻划一个最优解的结构特征

递归地定义最优解的值

计算最优解的值，通常采用自底向上的方法

利用计算出的信息构造出一个最优解

接下来，我们查看两个实例，随后给出动态规划的原理。

1. 钢条切割

我们有一段长钢条，打算将其切割为短钢条出售，公司希望知道最优的切割方案。

问题的详细描述:给定一个长为n的钢条和一个价格表 $pi$ ,求钢条切割方案，使得销售的收益r最大。
如图所示，即为价格表

价格表

我们首先来看切割4英寸钢条的案例，如图所示给出了所有的切割方案

钢条切割

我们会发现最优解即为分为2和2的两段，得到十元
如果一个最优解将钢条切割为k段，那么切割方案
$n = i_1+i_2+i_3...+i_k$
得到最大收益为
$r = p_{i_1}+p_{i_2}+p_{i_3}...+p_{i_n}$
一般的，对于 $r_n$ ,我们可以用更短钢条的最优切割收益来描述它
$r_n = max(p_n,r_1+r_{n-1},r_2+r_{n-2}...r_{n-1}+r_1)$

第一个参数 $p_n$ 对应不切割，其他参数对应着另外n-1个方案，首先将钢条分割为 $i,n-i$ 的两段，接着求出这两段的最优切割收益 $r_i和r_{n-i}$ ，我们必须考察所有的i，选出其中收益最大者。

为了求解规模为n的问题，我们先求解形式完全一样的，但规模更小的子问题，我们通过组合两个相关子问题的最优解，并在所有可能的两段切割方案中选取收益最高者，构成原问题的最优解。我们称钢条切割问题满足最优子结构性质：问题的最优解由相关子问题的最优解组合而成，而这些子问题可以独立求解。

除了上述方法外，还存在一种相似且更简单的递归求解方法，将钢条左边切割下长度为 $i$ 的一段，只对右边剩下的 $n-i$ 段进行切割。
即可得到如下公式
$r_n = \max_{1<=i<=n}(p_i+r_{n-i})$
在此公式中，原问题的最优解只包含一个相关子问题的解。
递归实现

inf = float("inf")
def cut_rod(p,n):
    if n==0:
        return 0
    q  =-inf
    for i in range(1,n+1):
        q = max(q,p[i]+cut_rod(p,n-i))
    return q

但这种递归计算会造成大量的重复计算，导致出现指数复杂度，如图所示

递归树.png

使用动态规划算法求解最优钢条切割问题

用动态规划算法仔细安排求解顺序，对每个子问题仅解一次，通过保存已计算的解，可以极大降低时间复杂度。

动态规划有两种实现形式，第一种是带备忘录的自顶向下方法，仍然使用递归，但会保存计算的中间结果，此后通过查询得到值。
第二种是自底向上法，先求解出子问题，再递推求解出父问题。两种方法有相同的渐进时间复杂度。

inf = float("inf")
def memoized_cut_rod(p,n):
    r = [-inf for i in range(n+1)]
    return memoized_cut_rod_aux(p,n,r)
def memoized_cut_rod_aux(p,n,r):
    q = -inf
    if r[n]>=0:
        return r[n]
    if n==0:
        q==0
    else:
        for i in range(1,n+1):
            q = max(q,p[i]+memoized_cut_rod_aux(p,n-i,r))
    r[n] = q
    return q

自底向上版本

inf = float("inf")
def bottom_up_cut_rod(p,n):
    r = [0 for i in range(n+1)]
    for j in range(1,n+1):
        q = -inf
        for i in range(1,j+1):
            q= max(q,p[i]+r[j-i])
        r[j] = q
    return r[n]

子问题图

当思考一个动态规划问题时,我们应该弄清所涉及的子问题及子问题之间的依赖关系.
问题的子问题图准确表达了这些信息.如图所示为n=4时的子问题图

子问题图.png

每个顶点唯一地对应一个子问题,若求解子问题x的最优解时需要用到y的最优解,那么x到y就有一条边.
自底向上的动态规划方法求解顺序为:对于一个给定的子问题x,在求解它之前求解邻接至它的子问题y。即对于任何子问题,只有当依赖它的所有子问题均已求解完成,才会求解它.
动态规划算法的运行时间与顶点和边的数量呈线性关系.

重构解

前文中讨论的方法并未返回解本身,我们可以扩展动态规划算法,使之对于每个子问题不仅保存最优收益值,而且还保存对应的切割方案.
如下给出扩展版本,对于长度为j的钢条不仅计算最大收益值 $r_j$ ,还保存最优解对应的第一段钢条的切割长度 $s_j$

inf = float("inf")
def extened_bottom_up_cut_rod(p,n):
    r = [0 for i in range(n+1)]
    s = [0 for i in range(n+1)]
    r[0] = 0
    for j in range(1,n+1):
        q = -inf
        for i in range(1,j+1):
            if q<p[i]+r[j-i]:
                q = p[i]+r[j-i]
                s[j] = i
        r[j] = q
    return (r,s)
def print_cut_rod_solution(p,n):
    (r,s) = extened_bottom_up_cut_rod(p,n)
    while n>0:
        print(s[n])
        n = n-s[n]

2.矩阵链乘法

对于如下n个矩阵序列,我们希望计算它们的乘积
$A_1A_2...A_n$
根据不同的运算次序,乘积运算的代价也会大不一样.
该问题可描述如下:

给定n个矩阵的链,求完全括号化方案(即给出运算次序),使得乘积所需要的标量乘法次数最少.

应用动态规划方法

最优括号化方案的结构特征
为论述方便起见,我们用符号 $A_{i..j}$ 来表示 $A_iA_{i+1}...A_{j}$ 的乘积结果.如果i<j,那么为了对 $A_iA_{i+1}...A_{j}$ 进行括号化,我们就必须在某个 $A_{k}和A_{k+1}$ 之间将矩阵链划分开.也就是说,对于某个整数k,我们首先计算矩阵 $A_{i..k}和A_{k+1..j}$ ,然后再计算它们的乘积得到最终结果.此方案的计算代价即为三者代价之和.
给出递归求解方案(找出最后一步,给出状态转移方程,确定状态)
令 $m[i,j]$ 表示计算矩阵 $A[i..j]$ 所需标量乘法次数的最小值,那么,计算 $A[1..n]$ 所需的最低代价就是 $m[1,n]$
$m[i,i]=0$
对于 $m[i,j]$ ,我们得到:
$m[i,j] = \min_{i≤k＜j}(m[i,k]+m[k+1,j]+p_{i-1}p_{k}p{j})$
3.计算最优代价
我们需要独立求解的子问题数量仅有 $Θ(n^2)$

3.动态规划原理

我们关注使用动态规划求解最优化问题应具备的两个要素:最优子结构和子问题重叠.

最优子结构

用动态规划方法求解最优化问题的第一步就是刻画最优解的结构,某个问题是否适合应用动态规划算法,它是否具有最优子结构是一个好线索.
在发掘最优子结构性质的过程中,实际上遵循了如下通用模式:

证明问题最优解的第一个组成部分是做出一个选择,例如选择矩阵链的划分位置,做出这次选择会产生一个或多个待解的子问题
对于一个给定的问题,在其可能的第一步选择中,你假定已经指导哪种选择才会得到最优解.
给定可获得最优解的选择后,你确定这次选择会产生哪些子问题,以及如何最好的刻画子问题空间.
4.利用反证法证明,作为构成原问题最优解的组成部分,每个子问题的解就是它本身的最优解.
对于不同问题领域，最优子结构的不同体现在以下两个方面：

原问题的最优解中有多少个子问题。

在确定最优解使用哪些子问题时，我们需要考察多少种选择。

例如在钢条切割问题中，长度为n的钢条最优切割方案仅使用一个字问题，但我们必须考查i的n种不同取值，来确定哪一种会产生最优解。

我们可以用子问题的总数和每个子问题需要考察多少种选择来粗略分析动态规划算法的运行时间。

一些微妙之处
无权最短路径可以动态规划算法求解，而最长路径无法使用动态规划算法求解。即最长简单路径问题不仅缺乏最优子结构的性质，而且由子问题的解组合出的甚至不是问原题的合法解。
为何最长简单路径的问题子结构和最短路径有这么大差别？原因在于最长简单路径的子问题时相关的，而最短路径子问题时无关的，即同一个原问题的一个子问题的解不影响另一个子问题的解。