动态规划是最容易出现在笔试的编程题中的内容,之前写过一篇文章动态规划算法介绍了几种动态规划的应用.本文介绍一下动态规划的原理及实施步骤.

动态规划适用于什么问题

适合应用动态规划方法求解的最优化问题应该具备的两个要素:最优子结构子问题重叠.

如果一个问题的最优解包含其子问题的最优解,换句话说我们能将原始问题拆分成解规模更小的子问题的形式,我们就称此问题具有最优子结构性质.

子问题空间必须足够"小",即问题的递归算法会反复求解相同的子问题,而不是一直生成新的子问题,称为重叠子问题性质.与之相对的,适合用分治方法求解的问题通常在递归的每一步都生成全新的子问题.动态规划算法通常这样利用重叠子问题的性质:对每个子问题求解一次,将解存入一个备忘录中,这样同一个子问题只需计算一次,避免了重复计算.

使用动态规划的步骤

解决动态规划问题只需两步:

  1. 将原始问题拆分成规模更小的子问题,并写出递推式;
  2. 将每个子问题的解存到备忘录中,下次计算这个子问题从备忘录中取结果.

动态规划的难点在于第一步,因为对于不同问题领域,原始问题的拆分方式可能会有很大的不同,主要的不同体现在两个方面:

  1. 原问题的最优解中涉及多个子问题.
  2. 在确定最优解使用哪些子问题时,需要考察多少种选择.

具体的区别还是需要用例子来体会,下文中的几个例子难度逐渐递增:

  • 钢条切割问题拆分成一个子问题
  • 矩阵链乘法问题拆分成两个子问题
  • 最长公共子序列拆分成一个子问题,但是会根据不同的条件选择不同的子问题

钢条切割问题

Serling公司购买了长钢条,将其切割为短钢条出售.下面是不同长度的价格:

长度i 1 2 3 4 5 6 7 8 9 10
价格p 1 5 8 9 10 17 17 20 24 30

钢条切割问题是这样的:给定一段长为n的钢条和一个价格表p_i \; (i=1,2,3,...)如何切割才能使收益r_n最大?

第一步写出递推式,钢条可以切为两段,其中一段不一定收益最大,另一段是规模较小的子问题,是收益最大的.第一段的收益不是最大的,但是我们可以遍历第一段的所有情况找出收益最大的情况:

r _ { n } = \max _ { 1 \leqslant i \leqslant n } \left( p _ { i } + r _ { n - i } \right)

第二步将每个子问题的解存入r,其中r[i]为长i的钢条最大收益,下次从备忘录中取值:

p = {1:1,2:5,3:8,4:9,5:10,6:17,7:17,8:20,9:24,10:30}

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

矩阵链乘法问题

两个维度分别为(10,100),(100,20)的矩阵A,B相乘,他们的计算量为10 \times 100 \times 20.三个纬度分别为(10,100),(100,20),(20,200)的矩阵A,B,C相乘时,不同的计算顺序会有不同的计算量:

(AB)C = 10*100*20 + 10*20*200 = 60000

A(BC) = 100*20*200 + 10*100*200 = 600000

可以看到,两种计算顺序的计算量相差10倍.

矩阵链乘法问题可描述如下:给定n个矩阵的链A _ { 1 } A _ { 2 } \cdots A _ { n },矩阵A_i的规模为p_{i-1}\times p_i \; (1\leq i \leq n),求完全括号化方案,使得计算A _ { 1 } A _ { 2 } \cdots A _ { n }的乘法次数最小.

第一步写出递推式,能否像钢条切割那样,切分成一段不是最优的,另一端是最优的呢?实验一下会发现不行,因为在钢条切割例子中,不是最优段的收益可以直接获取,而在本例子中,我们切分成不是最优的一段的计算量无法直接获取.假设可以拆分成两个都是最优的子问题,那么只需要将两个子问题的计算量相加,然后再加上这两个子问题合并的计算量即可,但是我们不知道如何切割是最优的,所以遍历所有切割情况:

m [ i , j ] = \left\{ \begin{array} { ll } 
{ 0 } &{如果i=j}\\ 
{ \min _ { i \leq k < j } \left\{ m [ i , k ] + m [ k + 1 , j ] + p _ { i - 1 } p _ { k } p _ { j } \right\} }&{如果i<j} \end{array} \right.

第二步,将所有子问题存到m中,其中m[i,j]为第i个矩阵到第j个矩阵的最优计算量,下次计算同样的子问题从m中取:

import numpy as np

def matrix_chain(p):
    n = len(p)-1
    m = np.zeros((n,n))
    
    for l in range(2,n+1):
        for i in range(n-l+1):
            j = i+l-1
            q = float('inf')

            for k in range(i,j):
                q = min(q,m[i,k] + m[k+1,j] + p[i-1]*p[k]*p[j])
                
            m[i,j] = q
    return m[0,n-1]

matrix_chain([30,35,15,5,10,20,25])

最长公共子序列

在生物学中,为了比较两段基因的相似性,需要求它们的最长公共子序列:

\text{ACCGGTCGAGTGCGCGGAAGCCGGCCGAA}

\text{GTCGTTCGGAATGCCGTTGCTCTGTAAA}

公共子序列并不一定需要在两个字符串中连续出现,只需要顺序相同,并且都出现在两个字符串中即可.

这个问题可以抽象成给定两个序列:

X = \left\langle x _ { 1 } , x _ { 2 } , \cdots , x _ { m } \right\rangle

Y = \left\langle y _ { 1 } , y _ { 2 } , \cdots , y _ { n } \right\rangle

求他们的公共子序列.

第一步写出递推式,我们考虑这样两个子问题,如果x _ { m } = y _ { n },那么X与Y的最长公共子序列是X _ { m - 1 }Y _ { n - 1 }的最长公共子序列加上x _ { m };如果x _ { m } \neq y _ { n },X与Y的最长公共子序列是X _ { m - 1 }Y的最长公共子序列和XY _ { n - 1 }的最长公共子序列中最长的一个.

c [ i , j ] = \left\{ \begin{array} { ll} 
{ 0 } &{若i=0或j=0}\\ 
{ c [ i - 1 , j - 1 ] + 1 }  &{若i,j>0且x_i=y_i}\\ 
{ \max ( c [ i , j - 1 ] , c [ i - 1 , j ] ) } &{若i,j>0且x_i \neq y_i}
\end{array} \right.

第二步,将所有子问题存到c中,其中c[i,j]为第一个序列到i长度与第二个序列到j个长度的最优子序列长度,下次计算同样的子问题从c中取:

import numpy as np

def LCS_LENGTH(X,Y):
    m = len(X)
    n = len(Y)
    
    c = np.zeros((m+1,n+1))
    
    for i in range(1,m+1):
        for j in range(1,n+1):
            if X[i-1] == Y[j-1]:
                c[i,j] = c[i-1,j-1] + 1
            elif c[i,j-1] >= c[i-1,j]:
                c[i,j] = c[i,j-1]
            else:
                c[i,j] = c[i-1,j]
    return c[m,n]

X = ['A' , 'B' , 'C' , 'B' , 'D' , 'A' , 'B']
Y = ['B' , 'D' , 'C' , 'A' , 'B' , 'A']
LCS_LENGTH(X,Y)
posted @ 2019-02-11 19:04:36
评论加载中...

发表评论