[关闭]
@zqbinggong 2018-03-21T12:53:43.000000Z 字数 3072 阅读 430

chap15 动态规划

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

内容


动态规划的原理

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

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

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

钢条切割

  1. 最优子结构: ,原问题的最优解只包含一个相关子问题(自然满足划分的条件)
  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. 最优子结构: ,原问题的最优解包含两个个相关子问题,但这两个相关子问题是独立的
  2. 具体实现,使用自底向上———

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. 具体实现,使用自底向上———

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. 递推关系式:

    其中
    此处需要注意的是多加的概率项,这是因为把一棵树作为嫁接到另一棵树的根结点时,该子树每个结点的高度要加1

  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

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注