算法导论 第15章 动态规划

《算法导论》这门课的老师是黄刘生和张曙，两位都是老人家了，代课很慢很没有激情，不过这一章非常有意思。

---

前言：

书中列举四个常见问题，分析如何采用动态规划方法进行解决。
　　装配线调度问题
　　矩阵链乘问题：
　　最长公共子序列问题：
　　最优二叉查找树问题：

基本概念

动态规划通常应用于最优化问题，此类问题可能包含多个可行解。每个解有一个值，而我们期望找到最大或者最小的解。

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

• 描述最优解的结构。
• 递归定义最优解的值。
• 按自底向上的方式计算最优解的值。（其实还应该有自顶向下的求解）
• 由计算出的结果构造一个最优解。

动态规划算法效率会非常高的原因在于，其特殊的实现方法，也就是第三步。

两种等价的实现方法：

• 带备忘的自顶向下法，此方法按照正常的递归编写过程，但过程会保存每个子问题的解（通常保存在一个数组或散列表中）。当需要一个子问题的解时，程序首先检查是否已经保存过此解。如果是，直接返回；若不是，递归计算这个子问题。这种递归方式是带备忘的。
• 自底而上法，这种方法需要恰当的定义子问题的规模，因为任何一个子问题的求解的依赖着更小的子问题。因此需要将问题进行排序，从小的问题开始处理。这样可以确保，在处理到大的问题时，其所依赖的更小的子问题已经求解完毕，结果已经保存。

因此，我们会说 动态规划算法属于典型的用空间换取时间。由于没有频繁的递归函数的开销，自底而上方法的时间复杂度会更好一些。

动态规划与分治法之间的区别：

• 分治法是指将问题分成一些独立的子问题，递归的求解各子问题。
• 动态规划适用于这些子问题不是独立的情况，也就是各子问题包含公共子问题。

动态规划基础

什么时候可以使用动态规范方法解决问题呢？这个问题需要讨论一下，书中给出了采用动态规范方法的最优化问题中的两个要素：最优子结构和重叠子结构。

最优子结构（自下向上）

最优子结构是指问题的一个最优解中包含了其子问题的最优解。在动态规划中，每次采用子问题的最优解来构造问题的一个最优解。

寻找最优子结构，遵循的共同的模式：

• 问题的一个解可以是做一个选择，得到一个或者多个有待解决的子问题。

• 假设对一个给定的问题，已知的是一个可以导致最优解的选择，不必关心如何确定这个选择。

• 在已知这个选择后，要确定哪些子问题会随之发生，如何最好地描述所得到的子问题空间。

• 利用“剪贴”技术，来证明问题的一个最优解中，使用的子问题的解本身也是最优的。

最优子结构在问题域中以两种方式变化：

• 有多少个子问题被使用在原问题的一个最优解中。
• 在决定一个最优解中使用哪些子问题时有多少个选择。

动态规划按照自底向上的策略利用最优子结构，即：首先找到子问题的最优解，解决子问题，然后逐步向上找到问题的一个最优解。

为了描述子问题空间，可以遵循这样一条有效的经验规则，就是尽量保持这个空间简单，然后在需要时再扩充它。

注意：在不能应用最优子结构的时候，就一定不能假设它能够应用。 警惕使用动态规划去解决缺乏最优子结构的问题！

使用动态规划时，子问题之间必须是相互独立的！可以这样理解，N个子问题域互不相干，属于完全不同的空间。

重叠子问题（自上向下）

用来解决原问题的递归算法可以反复地解同样的子问题，而不是总是产生新的子问题。

重叠子问题是指当一个递归算法不断地调用同一个问题。

动态规划算法总是充分利用重叠子问题，通过每个子问题只解一次，把解保存在一个需要时就可以查看的表中，每次查表的时间为常数。

由计算出的结果反向构造一个最优解：把动态规划或者是递归过程中作出的每一次选择（记住：保存的是每次作出的选择）都保存下来，在最后就一定可以通过这些保存的选择来反向构造出最优解。

做备忘录的递归方法：这种方法是动态规划的一个变形，它本质上与动态规划是一样的，但是比动态规划更好理解！
　　（1） 使用普通的递归结构，自上而下的解决问题。
　　（2） 当在递归算法的执行中每一次遇到一个子问题时，就计算它的解并填入一个表中。以后每次遇到该子问题时，只要查看并返回表中先前填入的值即可。

钢条切割问题

题目

给定一个长度为n的钢条，以及一个价格表p，p中列出了每英寸钢条的价格，将长度为n的钢条切割为若干短钢条出售，求一个钢条的切割方案，使得收益最大，切割工序没有成本。比如价格表p如下：

长度为n的钢条，一共有$2^{n-1}$种不同的切割方案，因为可以再距离钢条左边为i（i=1,2,…,n-1）处，我们总是可以选择切割或者不切割。比如下图表示了n=4的切割情况：

理论依据

我们称钢条切割问题满足最优子结构性质：问题的最优解由相关子问题的最优解组合而成，而这些子问题可以独立求解。

我们可以这样理解钢条问题：将钢条从左边切下一段长度为i的一段，对剩下的n-i的部分继续进行切割（递归求解），而不对左边长度为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

CUT-ROD的效率很差，这是因为CUT-ROD反复的求解一些相同的子问题，下图显示了当n==4时的调用情况：

带备忘的自顶向下

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]

方法采用子问题的自然顺序，因此过程中依次求解规模为$j=0,1,2,3,4…,n$的问题。

这两种算法具有相同的时间复杂度，BOTTOM-UP-CUT-ROD主要是双层嵌套循环，所以时间复杂度$Θ(n^2)$。MEMOIZED-CUT-ROD的时间复杂度也是$Θ(n^2)$。可以使用子问题图进行分析。

python实现切割钢条问题

def cut_rod():
    p = [0,1,5,8,9,10,17,17,20,24,30]
    n = len(p)
    r = [0 for i in range(n)]
    s = [0 for i in range(n)]
    for j in range(n):
        q = -10
        for i in range(j+1):
            if q < (p[i]+r[j-i]):
                q = (p[i]+r[j-i])
                s[j] = i
            #q = max(q,p[i]+r[j-i])
        r[j] = q
        
def find_way(n):
    cut_rod()
    print(n,'--->',r[n])
    while n > 0:
        print(s[n])
        n = n - s[n]

调用find_way(9)输出

矩阵链乘法

题目

给定n 个矩阵的序列，希望求它们的乘积：$A_1A_2A_3…A_n$ 。因为矩阵的乘法满足结合律，所以可以对n个矩阵序列加括号，来改变乘积顺序。比如对于矩阵链< $A_1$, $A_2$,$A_3$,$A_4$>可以有下面的加括号方案：

不同的加括号的方案，对于乘积运算的代价影响很大.

两个矩阵相乘，A为p q矩阵，B为q r矩阵。所以A 的乘法次数为pqr。

如果A（10,100 ），B（100,5）， C（5,50 ）三个矩阵相乘。

如果按照((AB)C)的顺序，则需要101005 + 10550 = 7500次乘法运算，如果按照(A(BC))的顺序，则需要100550 + 1010050 = 75000次乘法运算。所以，不同的加括号方案，对于矩阵链乘法的代价影响很大。

刻画最优解的结构特征

通过寻找最优子结构，利用最优子结构从子问题的最优解中构造出原问题的最优解。
假设$AiA{i+1}…Aj$的最优括号花方案的分割点是在$A_k$和$A{K+1}$之间，一个非平凡的矩阵链乘法任何时候都是需要划分链的，任何最优解都是有子问题的最优解构成的。

递归的定义最优解的值

令 $m[i,j] $表示计算矩阵 $A{i,j} $所需标量乘法的最小值，也即原问题的最优解，计算$ A{1..n} $的最低代价就是 $m[1,n]$

• 对于i == j 的平凡问题，矩阵链只包含唯一的矩阵$A_{i,j}$。
• 对于$Ai A{i+1}…Aj$ 的最优括号化方案的切割点在 $A_k$和$A{k+1}$之间。那么$m[i,j]$的解相当于计算$A{i..k}$和$A{k+1..j}$的代价加上，合并这两个子答案所需要的代价$p_{i-1}p_k p_j$

因此，我们得到

$$m[i,j] = m[i,k]+m[k,j]+p_{i-1}p_k p_j$$

计算最优解的值

算法应当按照长度递增的顺序求解矩阵链括号化问题，并按照对应的顺序填写表m。对举证连$A_{i,j}$，其规模为链的长度j-i+1

伪代码就不写了，直接写python代码

python实现矩阵链乘法问题

def MATRIX_CHAIN_ORDER(p):  
    n = len(p)  
    s = [[0 for j in range(n)] for i in range(n)]  
    m = [[0 for j in range(n)] for i in range(n)]  
    for l in range(2, n):           #l is the chain length  
        for i in range(1, n-l+1):  
            j = i + l - 1  
            m[i][j] = 1e9  
            for k in range(i, j):  
                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  
    PRINT_OPTIMAL_PARENS(s, 1, n-1)
    return m
    
      
def PRINT_OPTIMAL_PARENS(s, i, j):  
    if i == j:  
        print('A', end = '')  
        print(i, end = '')  
    else:  
        print('(', end = '')  
        PRINT_OPTIMAL_PARENS(s, i, s[i][j])  
        PRINT_OPTIMAL_PARENS(s, s[i][j]+1, j)  
        print(')', end = '')  
   

if __name__ == "__main__":
    A = [30, 35, 15, 5, 10, 20,25]
    m = MATRIX_CHAIN_ORDER(A) 
    print('\n','共计需要',m[1][n-1],'次相乘')

需要注意的问题是，这个算法的复杂度在O(n∧3)。而且这个算法和算法导论等地方的伪码比有些细微的差异体现在数组从0开始还是1开始上。大体上还是一致的。这里的空间复杂度也到了O(n∧2)。大致的计算顺序就是通过这个函数中的l来控制。l=2的时候，依次计算矩阵A[0]A[1], A[1]A[2], A[2]A[3]…的次数。l=3的时候就开始计算A[0]A[1]A[2], A[1]A[2]*A[3]..的次数。用更形象的话来说就是倒三角的顺序。下面的这个图就是对上面流程的描述：

---

以上