chap15 动态规划

动态规划 矩阵链乘法 LCS 算法导论

内容

动态规划的原理

1. 必要因素： 最优子结构和子问题重叠；前者是划分的依据，后者是可以以及需要使用动态规划的标志。另外子问题之间是无关的，否则划分途径将要失效。
2. 这句话也很明显，无论分治还是动归，都是将问题变成小问题集，解决小问题集中的问题，通过依赖关系得到大问题的解。因而实际要求解的就是这些小问题，因而他们的规模越小越好。

刻画子问题空间的好经验是：保持子问题空间尽可能简单，只有在必要时才扩展它

1. 最优子结构，即提到的母、子问题间的依赖关系，此处它表示一个问题的最优解包含其子问题的最优解
2. 重叠子问题，即子问题空间必须足够小，及问题的递归算法会反复地求解相同的子问题，而不是一直生成性的子问题。

钢条切割

1. 最优子结构： $r_{n} = max(p_{i} + r_{n-1})$,原问题的最优解只包含一个相关子问题（自然满足划分的条件）

2. 具体实现，自顶向下和自底向上———$\Theta(n^2)$。前者需要一个备忘机制，来存储已经求得的子问题的解，后者则不需要

   • 自顶向下，从一个大问题出发，按照自然的递归顺序，会逐渐求解该大问题所需的所有小问题的解；将这些解保存，在进行另一个大问题的求解时，在直接求解小问题前，会先查表，看看该小问题是否在之前的大问题求解过程中算过，如果算过，则直接查看答案即可。显然，这种做法在某些情况下会漏掉一些子问题集的解。
   • 自底向上，不按自然的递归顺序，而是按照子问题的规模大小，由小到大对子问题逐个求解。

自顶向下
Memoized-cut-rod(p,n)

let r[0...n] and s[0...n] be new arrays
for i = o to n
    r[i] = -00
(val,s) = memoized-cut-rod-aux(p,n,r,s)
print val
while n > 0
    print s[n]
    n = n - s[n]

memoized-cut-rod-aux(p,n,r,s)

if r[n] >= 0
    return r[n]
if n == 0
    q = 0
else q = -00
    for i = 1 to n
        (val,s) = memoized-cut-rod-aux(p,n-i,r,s)
        if q < p[i] + val
            q = p[i] + val
            s[n] = i
r[n] = q
return (q,s)

自底向上

bottom-up-cut-rod(p,n)

(r,s) = extended-bottom-up-cut-rod(p,n)
print r
while n > 0
    print s[n]
    n = n - s[n]

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 = -00
    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 (q,s)

矩阵链乘法

1. 最优子结构： $m[i,j] = \begin{cases} & 0 \text{ if } i=j\\ & min_{i\leqslant k\leqslant j} (m[i,k]+m[k+1,j]+p_{i-1}p_{k}p_{j}) \text{ if } i < j \end{cases}$,原问题的最优解包含两个个相关子问题，但这两个相关子问题是独立的
2. 具体实现，使用自底向上———$\Theta(n^3)$。

matrix-chain-orger(p)

n = p.length - 1
let m[1...n,1...n] and s[1...n-1,2...n] be new arrays
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           #结束位置，j-i+1 = l
        m[i,j] = 00
        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

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]+1,j)
   pritn ")"

最长公共子序列（LCS）

1. 最优子结构：
   
2. 递推关系式
3. 具体实现，使用自底向上———$\Theta(mn)$。

lcs-length(X,Y)

m = X.length
n = Y.length
let b[1...m,1...n] and c[0...m,0...n] be new tables
for i = 1 to m 
    c[i,0] = 0
for j = 0 to n
    c[0,j] = 0
for i = 1 to m
    for j = 1 to n
        if X[i] == Y[j]
            c[i,j] = c[i-1,j-1] + 1
            b[i,j] = 0
        else if c[i-1,j] >= c[i-1,j]
            c[i,j] = c[i-1,j]
            b[i,j] = 1
        else 
            c[i,j] = c[i,j-1]
            b[i,j] = -1
return c and b

print-lcs(b,X,i,j)

if i == 0 or j == 0
    return
if b[i,j] == 0
    print-lcs(b,X,i-1,j-1)
    print x[i]
else if b[i,j] == 1
    print-lcs(b,X,i-1,j)
else 
     print-lcs(b,X,i,j-1)

最优二叉搜索树 optimal bst

1. 最优子结构：最优bst的子树是最优的

2. 递推关系式： $e[i,j] = \begin{cases} & q_{i-1} \text{ if } j = i-1 \\ & min_{i\leqslant r\leqslant j} (e[i,r-1]+e[r+1,j]+\omega(i,j)) \text{ if } i \leqslant j \end{cases}$

   其中$\omega(i,j)=\omega(i,r-1)+\omega(r+1,j)+p_{r}$
   此处需要注意的是多加的概率项，这是因为把一棵树作为嫁接到另一棵树的根结点时，该子树每个结点的高度要加1

3. 具体实现，使用自底向上———$\Theta(n^3)$。

optimal-bst(p,q,n)

let e[1...n+1,0...n] and w[1...n+1,0...n] and root[1...n,1...n]
for i = 1 to n+1
    e[i,i-1] = q[i-1]
    w[i,i-1] = q[i-1]
for l = 1 to n
    for i = 1 to n-l+1
        j = i + l - 1
        e[i,j] = 00
        w[i,j] = w[i,j-1] + p[i] + q[j]
        for r = i to j
            t = e[i,r-1]+e[r+1,j]+w(i,j)
            if t < r[i,j]
                e[i,j] = t
                root[i,j] = r
return e and root

construct-optimal-bst(root)

r = root[1,n]
print "k"r "is the root"
construct-opt-subtree(1,r-1,r,"left",root)
construct-opt-subtree(r+1,n,r,"right",root)

construct-opt-subtree(i,j,r,dir,root)

if i <= j
    t = root[i,j]
    print "k"t "is" dir "child of k"r
   construct-opt-subtree(1,t-1,t,"left",root)
construct-opt-subtree(t+1,n,t,"right",root) 

习题

to be continued

代码实现

java