《算法导论》--动态规划

1. 概述

动态规划与分治法相似，都是通过组合子问题来求解原问题。区别在于，分治法将问题划分为互不相交的子问题，递归地求解子问题，再将它们的解组合起来，求出原问题的解。与之相反，动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子问题（子问题的求解是递归进行的，将其划分为更小的子子问题）。在这种情况下，分治法会做许多不必要的工作，它会反复求解那些公共子子问题，而动态规划算法对每个子子问题只求解一次。

动态规划方法通常用来求最优化问题，这类问题可以有很多可行的解，每个解都有一个值，我们希望寻找具有最优值的解。我们称这样的解为问题的一个最优解，而不是最优解，因为可能有多个解达到最优值。

通常按4个步骤设计一个动态规划算法

1.刻画一个最优解的结构特征；
2.递归地定义最优解的值；
3.计算最优解的值，通常采用自底向上的方法；
4.利用计算的信息构造一个最优解。

步骤1~3是动态规划算法求解问题的基础，如果仅仅需要一个最优解的值，可以忽略步骤4.

2.钢条切割

2.1 问题及描述

image.png image.png

2.2 伪代码

自顶向下递归实现

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

运行时间是指数增长的，求解过程如下的树：

image.png

使用动态规划方法求解

我们已经看到，朴素递归算法之所以效率很低，是因为它反复求解相同的子问题，因此，动态规划仔细安排求解顺序，对每个子问题只求解一次，并将结果保存下来。以后需要用到此子问题的解，只需查找保存的结果，而不必重新计算。

因此，动态规划方法是付出额外的内存空间来节省计算时间，是典型的时空权衡的例子。而时间上的节省可能是非常巨大：可能将一个指数的解转化为一个多项式时间的解。如果子问题的数量是输入规模的多项式函数，而我们可以在多项式时间内求解出每个子问题，那么动态规划方法的总运行时间就是多项式阶的。

• 带备忘的自顶向下法

MEMORIZED-CUT-ROD(p, n)
let r[0..n] be a new array
for i = 0 to n
    r[i] = -∞
return MEMORIZED-CUT-ROD-AUX(p, n, r)

MEMORIZED-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] + MEMORIZED-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]

• 子问题图
  当思考一个动态规划问题时，我们应该弄清所涉及的子问题和子问题之间的依赖关系。
  问题的子问题图准确地表达了这些信息，下图显示了n=4时钢条切割问题的子问题图。它是一个有向图，每个顶点唯一地对应一子问题。若求子问题x的最优解时需要直接用到子问题y的最优解，那么在子问题图中就会有一条从子问题x的顶点到子问题y的顶点的有向边。

  
  image.png
• 重构解
  前文给出的钢条切割问题的动态规划算法返回最优解的收益值，但并未返回解本身。下面给出BOTTOM-UP-CUT-ROD的扩展版本。它对长度为j的钢条不仅计算最大收益值r[j]，还保存最优解对应的第一段钢条的切割长度s[j]:

EXTENDED-BOTTOM-UP-CUT-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

3.矩阵链乘法

给定一个n个矩阵的序列（矩阵链）(A1,A2...An)我们希望计算它们的乘积：

A1A2...An

根据矩阵乘法结合律，考虑有四个元素的矩阵链（A1,A2,A3,A4），则共有5种括号化的矩阵乘积链：

（A1(A2(A3A4))）
（A1(A2A3)A4)）
（(A1A2)(A3A4)）
（(A1(A2A3))A4）
（((A1A2)A3)A4）

对矩阵链加括号的方式会对乘积运算的代价产生巨大影响。我们先来分析两个矩阵相乘的代价。下面的伪代码给出了两个矩阵相乘的标准算法。

MATRIX-MULTIPLY(A, B)
if A.colums != B.rows
    error "invalid input"
else let C be a new A.rows * B.colums matrix
    for i = 1 to A.rows
        for j = 1 to B.colums
            cij = 0
            for k = 1 to A.colums
                cij = cij + aik * bkj
return C

两个矩阵A和B只有相容，即A的列数等于B的行数时，才能相乘。
如果A是p * q的矩阵，B是q * r的矩阵，那么乘积C是p * r的矩阵。计算C所需时间由 cij = cij + aik * bkj 的标量乘法的次数决定，即pqr。

我们以矩阵链（A1,A2,A3）相乘为例，来说明不同的加括号方式导致不同的计算代价。假设三个矩阵的规模分别为10x100，100x5，5x50。

• 如果按（(A1A2)A3）顺序计算，为计算A1A2（规模10x5），需要做10x100x5=5000次标量乘法，再与A3相乘有需要做10x5x50=2500次标量乘法，共需7500次。
• 如果按A1(A2A3）顺序计算，计算A2A3（规模100x50），需100x5x50=25000次，A1再与之相乘，又要做10x100x50=50000次，共需75000次
  因此，第一种比第二种要快10倍。

3. 1 矩阵乘法问题描述

image.png

3.2 计算括号化方案的数量

image.png

3.3 应用动态规划方法

我们按开头给出的步骤进行：

1.刻画一个最优解的结构特征；
2.递归地定义最优解的值；
3.计算最优解的值，通常采用自底向上的方法；
4.利用计算的信息构造一个最优解。

• 步骤1. 最优括号化方案的结构特征
  为方便起见，我们用A(i..j) （i<=j）表示Ai Ai+1 ...Aj乘积的结果矩阵。则矩阵链可以拆为A(i..k)和A(k+1 ... j)的乘积，再计算最终结果A(i...j) 。此方案的计算代价等于矩阵A(i...k)加上A(k+1 ... j)计算代价，再加上两者相乘的计算代价。

现在我们展示如何利用最优子结构性质从子问题的最优解构造原问题的最优解。我们已经看到，一个非平凡的矩阵链乘法问题实例的任何解都需要划分链，而任何最优解都是由子问题实例的最优解构成的。因此，为了构造一个矩阵链乘法问题实例的最优解，我们可以将问题划分为两个子问题（Ai Ai+1...Ak）和（Ak Ak+1...Aj的最优括号化问题），求出子问题实例的最优解，然后将子问题的最优解组合起来。我们必须保证在确定分割点时，已经考察了所有可能的划分点，这样就可以保证不会遗漏最优解。

• 步骤2. 一个递归求解方案
  下面用子问题的最优解来递归地定义原问题最优解的代价。对矩阵链乘法问题，我们可以将对所有1<=i<=j<=n确定Ai Ai+1...Aj的最小代价括号化方案作为子问题。令m[i, j]表示计算矩阵Ai...j所需标量乘法次数的最小值，那么，原问题的最优解——计算A1..n所需的最低代价就是m[1, n]。

我们可以递归定义m[i, j]如下。对于i=j时的一般性问题，矩阵链只包含唯一的矩阵Ai..i = Ai, 因此不需要做任何标量乘法运算。所以，对所有i=1,2...n, m[i, i] = 0。若i < j，我们利用步骤1中得到的最优子结构来计算m[i, j]。我们假设Ai Ai+1...Aj的最优括号化方案的分割点在矩阵Ak和Ak+1之间，其中i<=k<j。那么，m[i, j]就等于计算Ai..k和Ak+1..j的代价加上两者相乘的代价的最小值。由于矩阵Ai的大小为p[i-1] * p[i]，易知Ai..k与Ak+1..j相乘的代价为p[i-1]p[k]p[j]次标量乘法运算。因此，我们得到：

m[i, j] = m[i, k] + m[k + 1, j] + p[i - 1]*p[k]*p[j]

此递归公式假定最优分割点k是已知的，但实际上我们是不知道的。不过，k只有j-i种可能的取值，即k=i，i+1...j-1。由于最优分割点必在其中，我们只需检查所有可能情况，找到最优者即可。因此，Ai Ai+1...Aj最小代价括号化方案的递归求解公式变为：

image.png

• 步骤3. 计算最优代价
  我们很容易基于上步骤的递归公式写出一个递归算法，像钢条切割问题一样，但这样也是会重复计算子问题。
  为了实现自底向上方法，我们必须确定计算m[i, j]时需要访问哪些其它表项。j-i+1个矩阵链相乘的最优计算代价m[i, j]只依赖于那些少于j-i+1个矩阵链相乘的最优计算代价。也就是说，对k=i,i+1,...,j-1，矩阵Ai..k是k-i+1<j-i+1个矩阵的积。因此，算法应该按长度递增的顺序求解矩阵链括号化的问题，并按对应的顺序填写表m。对矩阵链AiAi+1..Aj最优括号化的子问题，我们认为其规模为链的长度j-i+1。

MATRIX- CHAIN-ORDER(p)
n = p.length - 1
let m[1...n, 1...n] and s[1...n-1, 2...n] be new tables
for i = 1 to n
    m[i, i] = 0
for l = 2 to n
    for i = 1 to n - l + 1
        j = i + l - 1
        m[i, j] = ∞
        for k = i to j -1
            q = m[i, k] + m[k+1, j] + p[i - 1]*p[k]*p[j]
            if q < m[i, j]
                m[i, j] = q
                s[i, j] = k
return m and s

• 步骤4. 构造最优解
  每个表项s[i, j]记录了一个k值，指出Ai Ai+1... Aj的最优括号化方案的分割点应该在Ak和Ak+1之间。下面给出递归输出最优括号方案的伪代码。

PRINT-OPTIMAL-PARENS(s, i, j)
if i == j
      print "A"
else print "("
        PRINT-OPTIMAL-PARENS(s, i, s[i, j])
        PRINT-OPTIMAL-PARENS(s, s[i, j], j)
        print ")"