CLRS15 动态规划

2017-05-20 | 阅读：次

介绍

动态规划和分治方法相思，都是通过组合子问题的解来求解原问题。
动态规划适用于子问题重叠的情况。
动态规划通常用来求解最优化问题。

15.1 钢条切割

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

CUT-ROD(p, n)
    if n == 0
        return 0
    q = -INFINITE
    for i = 1 to n
        q = max(q, p[i] + CUT-ROD(p, n-i))
    return q
这种做法考差了所有2^(n-1)种可能切割方案，故为指数运行时间。
它反复求解相同的子问题。

动态规划有两种等价的实现方法：自底向上法和带备忘的自顶向下法。第一种通常具有更小的系数。

MEMOIZED-CUT-ROD(p, n)
    let r[0..n] be a new array
    for i = 0 to n
        r[i] = -INFINITE
    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 = -INFINITE
        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 = -INFINITE
        for i = 1 to j
            q = max(q, p[i] + r[j-i])
        r[j] = q
    return r[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 = -INFINITE
        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

PRINT-CUT-ROD-SOLUTION(p, n)
    (r, s) = EXTENDED-BOTTOM-UP-CUT-ROD(p, n)
    while n > 0
        print s[n]
        n -= s[n]

练习15.1-1 由公式15.3和初始条件T(0)=1，证明公式15.4成立。

用induction证喽~

练习15.1-2 证明下面的贪心策略不能总是得到最优切割方案。

让n=4就行了。

练习15.1-3 对钢条切割问题进行一点修改，每次切割需要付出固定的成本c.

修改后这个问题还是具有最优子结构。

BOTTOM-UP-CUT-ROD(p, n)
    let r[0..n] be a new array
    r[0] = 0
    for j = 1 to n
        q = p[n]
        for i = 1 to j-1
            q = max(q, p[i] + r[j-i] - c)
        r[j] = q
    return r[n]

练习15.1-4 修改MEMOIZED-CUT-ROD,使之也返回切割方案。

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

MEMOIZED-CUT-ROD-AUX(p, n, r, s)
    if r[n] >= 0
        return r[n]
    if n == 0
        q = 0
    else q = -INFINITE
        for i = 1 to n
            if p[i] + MEMOIZED-CUT-ROD-AUX(p, n-i, r, s) > q
                q = p[i] + MEMOIZED-CUT-ROD-AUX(p, n-i, r, s)
                r[i] = q
                s[i] = i
    r[n] = q
    return r[n], s

练习15.1-5 设计一个O(n)时间的动态规划算法计算第n个斐波那契数。

FIBONACCI(n)
    let dp[1..n] be a new array
    dp[1] = 0
    dp[2] = 1
    for i = 3 to n
        dp[i] = dp[i-1] + dp[i-1]
    return dp[n]

图中有O(n)个顶点和边。

FIBONACCI(n)
    let dp[1..n] be a new array
    for i = 1 to n
        dp[i] = -INFINITE
    return FIBONACCI-AUX(n, dp)

FIBONACCI-AUX(n, dp)
    if n == 1
        q = 0
    elif n == 2
        q = 1
    else
        q = FIBONACCI-AUX(n-1, dp) + FIBONACCI-AUX(n-2, dp)
    dp[n] = q
    return q

矩阵链乘法

完全括号化：它是单一矩阵，或者是两个完全括号化的矩阵乘积链的积，且已外加括号。
对矩阵链加括号的方式会对乘积运算的代价产生巨大影响。
矩阵链乘法问题：给定n个矩阵的链，Ai的规模为pi-1*pi，求完全括号化方案，使得计算乘积A1A2…An所需标量乘法次数最少。
一个非平凡的矩阵链乘法问题实例的任何解都需要划分链，而任何最优解都是由子问题实例的最优解构成的。
问题重叠的性质是应用动态规划的另一个标识(第一个标识是最优子结构)。

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 = l to n-l+1
            j=i+l-1
            m[i,j] = INFINITE
            for k = i to j-1
                q = m[i,k]+m[k+1,j]+pi-1*pk*pj
                if q < m[i,j]
                    m[i,j]=q
                    s[i,j]=k
    return m and s

运行时间为O(n^3)

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

练习15.2-1 Find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is [5, 10, 3, 12, 5, 50, 6].

(A1(A2A3))((A4A5)A6)

练习15.2-2 Give a recursive algorithm MATRIX-CHAIN-MULTIPLY(A, s, i, j) that actually performs the optimal matrix-chain multiplication, given the sequence of matrices [A1, A2, …, An], the s table computed by MATRIX-CHAIN-ORDER, and the indices i and j. (The initial call would be MATRIX-CHAIN-MULTIPLY(A, s, 1, n).)

MATRIX_CHAIN_MULTIPLY(A, s, i, j)
    if i == j
        return A[i]
    if j == i + 1
        return A[i] * A[j]
    else
        B1 = MATRIX_CHAIN_MULTIPLY(A, s, i, s[i,j])
        B2 = MATRIX_CHAIN_MULTIPLY(A, s, s[i,j]+1, j)
        return B1 * B2

练习15.2-3 Use the substitution method to show that the solution to the recurrence (15.11) is Ω(2^n).

Catalan numbers

练习15.2-4 对输入链常读为n的矩阵链乘法问题，描述子问题图: 它包含多少顶点？包含多少边？这些边分别连接哪些顶点？

n^2/2个顶点
每个顶点i+j条边
和为O(n^3)

练习15.2-5 Let R(i, j) be the number of times that table entry m[i, j] is referenced while computing other table entries in a call of MATRIX-CHAIN-ORDER. Show that the total number of references for the entire table is (Hint: You may find equation (A.3) useful.)

http://cs.boisestate.edu/~jhyeh/teach/cs242_spring04/h4_sol.pdf

练习15.2-6 Show that a full parenthesization of an n-element expression has exactly n - 1 pairs of parentheses.

用induction.

动态规划原理

应用动态规划方法求解的最优化问题应该具备的两个要素：最优子结构和子问题重叠。
如果一个问题的最优解饱含其子问题的最优解，我们就称此问题具有最优子结构性质。(最优子结构也可能适合应用贪心策略)
粗略分析动态规划算法运行时间: 子问题数乘以每个子问题需要做的选择数。 (在子问题图里，每个顶点对应一个字问题，顶点的边对应选择数)
子问题无关性质 最长简单路径问题缺乏最优子结构性质。子问题必须是无关的。
递归调用树中反复出现相同的子问题时，使用动态规划能极大地提高效率。
重构最优解 通常将每个子问题的选择存在一个表中。

MEMOIZED-MATRIX-CHAIN(p)
    n = p.length - 1
    let m[1..n,1..n] be a new table
    for i = 1 to n
        for j = i to n
            m[i,j] = INFINITE
    return LOOKUP-CHAIN(m, p, 1, n)

LOOKUP-CHAIN(m, p, i, j)
    if m[i,j] < INFINITE
        return m[i,j]
    if i == j
        m[i,j] = 0
    else for k = i to j-1
        q = LOOKUP-CHAIN(m, p, i, k) + LOOKUP-CHAIN(m, p, k+1, j) + pi-1*pk*pj
        if q < m[i,j]
            m[i,j] = q
    return m[i, j]

练习15.3-1 Which is a more efficient way to determine the optimal number of multiplications in a matrix- chain multiplication problem: enumerating all the ways of parenthesizing the product and computing the number of multiplications for each, or running RECURSIVE-MATRIX- CHAIN? Justify your answer.

两个都是指数阶。

练习15.3-2 Draw the recursion tree for the MERGE-SORT procedure from Section 2.3.1 on an array of 16 elements. Explain why memoization is ineffective in speeding up a good divide-and- conquer algorithm such as MERGE-SORT.

因为子问题不重叠。

练习15.3-3 Consider a variant of the matrix-chain multiplication problem in which the goal is to parenthesize the sequence of matrices so as to maximize, rather than minimize, the number of scalar multiplications. Does this problem exhibit optimal substructure?

有的。

练习15.3-4 As stated, in dynamic programming we first solve the subproblems and then choose which of them to use in an optimal solution to the problem. Professor Capulet claims that it is not always necessary to solve all the subproblems in order to find an optimal solution. She suggests that an optimal solution to the matrix-chain multiplication problem can be found by always choosing the matrix Ak at which to split the subproduct Ai Ai+1 Aj (by selecting k to minimize the quantity pi-1 pk pj) before solving the subproblems. Find an instance of the matrix-chain multiplication problem for which this greedy approach yields a suboptimal solution.

随便找个反例就行，应该会很多。

练习15.3-5 假设每种钢条长度i最多允许切割出li段长度为i的钢条，则最优子结构性质不成立。

就跟最长路径一样的道理。可能两个最优子问题解组合起来不是合法的原问题解。

练习15.3-6 Imagine that you wish to exchange one currency for another. You realize that instead of directly exchanging one currency for another, you might be better off making a series of trades through other currencies, winding up with the currency you want. Suppose that you can trade n different currencies, numbered 1,2, … , n, where you start with currency 1 and wish to wind up with currency n. You are given, for each pair of currencies i and j , an exchange rate rij , meaning that if you start with d units of currency i , you can trade for drij units of currency j . A sequence of trades may entail a commission, which depends on the number of trades you make. Let ck be the commission that you are charged when you make k trades. Show that, if ck = 0 for all k = 1,2, … , n, then the problem of finding the best sequence of exchanges from currency 1 to currency n exhibits optimal substructure. Then show that if commissions ck are arbitrary values, then the problem of finding the best sequence of exchanges from currency 1 to currency n does not necessarily exhibit optimal substructure.

明显具有最优子结构性质。
最优子问题的解组合不一定能得到最优答案。

15.4 最长公共子序列

子序列就是将序列中零个或多个元素去掉之后得到的结果。
两个序列的LCS包含两个序列前缀的LCS，因此具有最优子结构性质。

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 = 1 to n
        c[0, j] = 0
    for i = 1 to m
        for j = 1 to n
            if xi == yj
                c[i,j] = c[i-1,j-1]+1
                b[i,j] = "UP-LEFT"
            elif c[i-1,j] >=c[i,j-1]
                c[i,j] = c[i-1,j]
                b[i,j] = "UP"
            else c[i,j] = c[i,j-1]
                b[i,j] = "LEFT"
    return c and b

PRINT-LCS(b, X, i, j)
    if i == 0 and j == 0
        return 
    if b[i, j] = "UP-LEFT"
        PRINT-LCS(b, X, i-1, j-1)
        print xi
    elif b[i,j] = "UP"
        PRINT-LCS(b, X, i-1, j)
    else PRINT-LCS(b, X, i, j-1)

练习15.4-1 Determine an LCS of <1, 0, 0, 1, 0, 1, 0, 1> and <0, 1, 0, 1, 1, 0, 1, 1, 0>.

<1,0,0,1,1,0>或者<1,0,1,0,1,0>

练习15.4-2 Show how to reconstruct an LCS from the completed c table and the original sequences X = <x1, x2, …, xm> and Y = <y1, y2, …, yn> in O(m +n) time, without using the b table.

PRINT-LCS(c, X, i, j)
    if i == 0 or j == 0
        return
    if c[i-1, j] == c[i, j-1]
        PRINT-LCS(c, X, i-1, j-1)
        print xi
    elif c[i-1, j] == >= c[i, j-1]
        PRINT-LCS(c, X, i-1, j)
    else
        PRINT-LCS(c, X, i, j-1)

练习15.4-3 Give a memoized version of LCS-LENGTH that runs in O(mn) time.

MEMOIZED-LCS-LENGTH(X, Y)
    m = X.length
    n = Y.length
    let dp[0..m, 0..n] be new table
    for i = 0 to m
        for j = 0 to n
            dp[i][j] = -1
    return LCS-LENGTH-AUX(X, Y, dp, m, n)

LCS-LENGTH-AUX(X, Y, dp, i, j)
    if dp[i][j] >= 0
        return dp[i][j]
    elif i == 0 or j == 0
        p = 0
    elif X[i] == Y[j]
        p = 1 + LCS-LENGTH-AUX(X, Y, dp, i-1, j-1)
    else 
        p = max(LCSLCS-LENGTH-AUX(X, Y, dp, i, j-1),
                LCS-LENGTH-AUX(X, Y, dp, i-1, j))
    dp[i][j] = p
    return p

练习15.4-4 Show how to compute the length of an LCS using only 2 · min(m, n) entries in the c table plus O(1) additional space. Then show how to do this using min(m, n) entries plus O(1) additional space

因为计算一个项时，只需要上一行和当前行的前一个元素，所以min(m,n)个表项和O(1)额外空间就行了。

练习15.4-5 Give an O(n^2)-time algorithm to find the longest monotonically increasing subsequence of a sequence of n numbers.

这个题的解法好赞
先将序列X排序，得到X'
然后寻找X和X'的LCS,就是答案。
运行时间为O(nlgn)+O(n^2) = O(n^2)

练习15.4-6 Give an O(n lg n)-time algorithm to find the longest monotonically increasing sub-sequence of a sequence of n numbers. (Hint: Observe that the last element of a candidate subsequence of length i is at least as large as the last element of a candidate subsequence of length i - 1. Maintain candidate subsequences by linking them through the input sequence.)

http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/
方法好奇妙

15.5 最优二叉搜索树

希望频繁出现的元素被置于靠近根的位置。在给定单词出现频率的前提下，应该如何组织一棵二叉搜索树，使得所有搜索操作访问的结点总数最少？
最优二叉搜索树不一定是高度最矮的，而且概率最高的关键字也不一定出现在根结点。

OPTIMAL-BST(p, q, n)
    let e[1..n+1, 0..n], w[1..n+1, 0..n] and root[1..n, 1..n] be new tables
    for i = 1 to n + 1
        e[i, i-1] = qi-1
        w[i, i-1] = qi-1
    for l = 1 to n
        for i = 1 to n - l + 1
            j = i + l - 1
            e[i, j] = INFINITE
            w[i, j] = w[i, j-1] + pj + qj
            for r = i to j
                t = e[i, r-1] + e[r+1, j] + w[i, j]
                if t < e[i, j]
                    e[i, j] = t
                    root[i, j] = r
    return e and root

运行时间Theta(n^3): 因为三重for循环，每层n

练习15.5-1 Write pseudocode for the procedure CONSTRUCT-OPTIMAL-BST(root) which, given the table root, outputs the structure of an optimal binary search tree. For the example in Figure 15.8, your procedure should print out the structure as follow.

看起来不难实现，下次有力气了再写。

练习15.5-2 Determine the cost and structure of an optimal binary search tree for a set of n = 7 keys with the following probabilities。

运行代码喽~

练习15.5-3 Suppose that instead of maintaining the table w[i, j], we computed the value of w(i, j) directly from equation (15.17) in line 8 of OPTIMAL-BST and used this computed value in line 10. How would this change affect the asymptotic running time of OPTIMAL-BST?

对算法渐进性没有影响。

练习15.5-4 Knuth [184] has shown that there are always roots of optimal subtrees such that root[i, j - 1] ≤ root[i, j] ≤ root[i + 1, j] for all 1 ≤ i < j ≤ n. Use this fact to modify the OPTIMAL-BST procedure to run in Θ(n2) time.

unsolved.

思考题

15-1 有向无环图的最长简单路径

很明显，设s和t最长简单路径上有一个结点m，则s..m是m..t均是最长简单路径。
因此符合最优子结构，也易看出符合子问题重叠。

先将每个结点的值设为负无穷，将s的值设为0
然后对于每个能从s直接到达的点i,如果s的值+权重大于i,更新i, 对于每个i进行类似操作...
用一个队列来维护要更新的结点，每次遇到一个结点，就将从它能直接到达的结点入待更新队列
这样一直进行下去，因为是无环图，所以队列总会空
队列空时结点t的值就是最长加权简单路径

PS: 我的做法并没有用动态规划
(等看到图算法了再想想有没有更好的做法)

15-2 最长回文子序列

def longest_palindrome_subsequence(s):
    res = [[0] * len(s) for _ in range(len(s))]
    single = [""]
    lps_aux(s, res, 0, len(s)-1, single)
    return generate_palindrome(s, res, single)
    
def lps_aux(s, res, i, j, single):
    if i > j:
        single[0] = ""
        return 0
    if res[i][j] > 0: return res[i][j]
    if i == j: 
        res[i][j] = 1
        single[0] = s[i]
        return 1
    res[i][j] = lps_aux(s, res, i+1, j, single)
    k = i + s[i:j+1].rfind(s[i])
    if k != i and lps_aux(s, res, i+1, k-1, single) + 2 > res[i][j]:
        res[i][j] = lps_aux(s, res, i+1, k-1, single) + 2
    return res[i][j]

def generate_palindrome(s, res, single):
    palindrome = []
    i, j = 0, len(res)-1
    while i < j:
        if res[i][j] == res[i+1][j]: pass
        elif res[i][j] - 2 in res[i+1]: 
            res[i][j] += 2
            palindrome.append(s[i])
            j = i + s[i:j+1].rfind(s[i]) - 1
        i += 1
    palindrome = palindrome + [single[0]] + palindrome[::-1]
    return "".join(palindrome)
        

print(longest_palindrome_subsequence("dabccccdd"))