Algorithm Design and Analysis - Dynamic programming

Jiawen Zhang Oct 18, 2018

Main message: 1. 把子问题的求解想象成多步求解过程 2. 子问题的最优解可以组合成原问题的最优解 3. Programming：tabular可以被用于避免子问题的重复计算

联动： Dynamic Programming 动态规划算法

Dynamic programming VS. Divide-and-conquer

动态规划算法一般被用于解决优化问题。需满足以下几个特点：

原问题可以被分解成更小的子问题
具有最优子结构性质，即最优解可以通过结合子问题的最优解得到。

与通用的分治法框架不同，动态规划算法通常枚举所有可能的分解策略。子问题的重复计算可以通过“programming”避免。

Matrix Chain Multiplication problem 矩阵的链式乘法

INPUT:A sequence of n matrices \(A_1, A_2 , ..., A_n\); matrix A i has dimension \(p_{i-1} \times p_i\)

OUTPUT:Fully parenthesizing the product \(A_1, A_2 , ..., A_n\) in a way to minimize the number of scalar multiplications. ***

\[A_1 = \left[\begin{matrix} 1 & 2 \end{matrix}\right] A_2 = \left[ \begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{matrix} \right] A_3 =\left[\begin{matrix} 1 & 2 & 3 & 4\\ 4 & 5 & 6 & 7\\7 & 8 & 9 & 10\end{matrix} \right]\]

Solutions:

\(((A_1)(A_2))(A_3) : (1 \times 2 \times 3) + (1 \times 3 \times 4)\)

\((A_1)((A_2)(A_3)) : (2 \times 3 \times 4) + (1 \times 2 \times 4)\)

我们要如何选取矩阵相乘的顺序来使乘的次数最小呢？

若枚举所有可能的解法，时间复杂度是指数级的。我们可以将其想象成一个多步决策，将加括号看成子问题。我们使用OPT(i,j)来表示子问题，原问题可以通过计算OPT(1,n)解决。由于最优子结构性质，我们可以通过计算子问题的最优解计算出原问题的最优解。

\[OPT(1,n) = OPT(1,k) + OPT(k+1,n) + p_1p_{k+1}p_{n+1}\] 我们可以通过枚举所有可能的解来获得第一步决策。

Trials

Trial 1

RECURSIVE MATRIX CHAIN(i, j)
    if i == j then 
        return 0; 
    end if 
    OPT(i, j) = +∞; 
    for k = i to j − 1 do 
        q = RECURSIVE MATRIX CHAIN(i, k) 
            + RECURSIVE MATRIX CHAIN(k + 1, j) + p_(i−1) p_k p_j ; 
        if q < OPT(i, j) then 
            OPT(i, j) = q; 
        end if 
    end for 
    return OPT(i, j);

最优解：RECURSIVE MATRIX CHAIN(1, n)

然而，这种方式需要花费指数时间\(O(n^2)\)，且有大量的重复计算。我们可以开一个二维数组来存储subsolution，之后查表即可。

Trial 2

MEMORIZE_MATRIX_CHAIN(i, j) 
    if OPT[i, j] != NULL then 
        return OPT(i, j); 
    end if 
    if i == j then 
        OPT[i, j] = 0; 
        else 
        for k = i to j − 1 do 
            q = MEMORIZE MATRIX CHAIN(i, k) 
                +MEMORIZE MATRIX CHAIN(k + 1, j) 
                    +p i−1 p k p j ; 
            if q < OPT[i, j] then 
                OPT[i, j] = q; 
            end if 
        end for 
    end if 
    return OPT[i, j];

原问题可以通过调用MEMORIZE_MATRIX_CHAIN(1, n)并将所有OPT[i,j]设为NULL来解决。时间复杂度为\(O(n^3)\)

Trial 3

更快的一种解决方式：自底向上迭代

MATRIX CHAIN MULTIPLICATION(p 0 , p 1 , ..., p n )
    for i = 1 to n do 
        OPT(i, i) = 0; 
    end for 
    for l = 2 to n do 
        for i = 1 to n − l + 1 do 
            j = i + l − 1; 
            OPT(i, j) = +∞; 
            for k = i to j − 1 do
                q = OPT(i, k) + OPT(k + 1, j) + p i−1 p k p j ; 
                if q < OPT(i, j) then 
                    OPT(i, j) = q; 
                    S(i, j) = k; 
                end if 
            end for 
        end for 
    end for 
    return OPT(1, n);

解题顺序：红 \(\Rightarrow\) 绿 \(\Rightarrow\) 橙 \(\Rightarrow\) 蓝，自底而上，先列出所有子问题

step 1：

OPT[1,2],OPT[2,3],OPT[3,4]

step 2： \[OPT[1,3] = min \left\{ \begin{aligned} OPT[1,2] + OPT[3,3] + p_0 \times p_2 \times p_3 \\ OPT[1,1] + OPT[2,3] + p_0 \times p_1 \times p_3 \end{aligned} \right.\] Thus, SPLITTER[1,2] = 2.

\[OPT[1,3] = min \left\{ \begin{aligned} OPT[2,2] + OPT[3,4] + p_1 \times p_2 \times p_4 \\ OPT[2,3] + OPT[4,4] + p_1 \times p_3 \times p_4 \end{aligned} \right.\] Thus, SPLITTER[2,4] = 3.

step 3： \[OPT[1,3] = min \left\{ \begin{aligned} OPT[1,1] + OPT[2,4] + p_0 \times p_1 \times p_4 \\ OPT[1,2] + OPT[3,4] + p_0 \times p_2 \times p_4 \\ OPT[1,3] + OPT[4,4] + p_0 \times p_3 \times p_4 \end{aligned} \right.\] Thus, SPLITTER[1,4] = 3.

在此方法中，只有子问题的最优解被计算，因此没有经过遍历，不是指数级的复杂度。

Backtracking

从OPT[1,n]开始回溯每一个决策阶段。

Step 1: \((A_1A_2A_3)(A_4)\)

Step 2: \(((A_1A_2)(A_3))(A_4)\)

Step 3: \((((A_1)(A_2)(A_3))(A_4)\)

0/1 KNAPSACK problem 0/1背包问题

INPUT: A set of items \(S = \{1, 2, ..., n\}\). Item i has weight \(w_i\) and value \(v_i\) . A total weight limit W; OUTPUT: A subset of items to maximize the total value with total weight below W. *** 这里的0和1表示我们可以选择一个物品(1)或者放弃它(0)，我们不能选择物品的一部分。

我们可以将将最优解表示为：\(OPT({1,2,...,i},w)\)

最优子结构： \[OPT({1,2,...,n},W) = max \left\{\begin{array}{lr}OPT({1,2,...,n-1},W) \\OPT({1,2,...,n-1},W-w_n) + v_n\end{array}\right.\]

Knapsack(n, W)
    for w = 1 to W do 
        OPT[0, w] = 0; 
    end for 
    for i = 1 to n do 
        for w = 1 to W do 
            OPT[i, w] = max{OPT[i−1, w], vi +OPT[i−1, w−wi]}; 
        end for 
    end for

我们使用OPT[I,w]来表示OPT({1,2,...,i},w).

step 1：

Initially all OPT[0, w] = 0.

step 2：

\[OPT[1, 2] = max\{ OPT[0, 2], OPT[0, 0] + V_1 \} =2\]

step 3：

\[OPT[2, 4] = max\{ OPT[1, 4], OPT[1, 2] + V_2\} =4\]

step 4：

\[OPT[3, 3] = max\{OPT[2, 3], OPT[2, 0] + V_3\} =3\]

backtracking

\[OPT[3, 6] = max{ OPT[2, 6](= 4), OPT[2, 3] + V_3 (= 2 + 3)} =5\]

Decision: Select item 3

\[OPT[2, 3] = max{ OPT[1, 3](= 2), OPT[1, 1] + V_2 (= 0 + 2)} =2\]

Decision: Select item 2

时间复杂度：\(O(nW)\)

若将items看做是集合（recursion over sets），将花费指数倍的时间；但是若将items先进行排序（recursion over sequences），花费的时间为\(O(nW)\)。

Sequence Alignment problem

Alignment is introduced to describe the generating process of an erroneous word from the correct word using a series of INS/DEL/MUTATION operations.

要比较两个序列，我们首先在合适的地方引入空格-。使得两个序列的长度相同，即\(|S' = T'|\)

对齐的字符可能有三种情况： 1. S'[i] = "-" : S'[i] is simply a DELETION of T'[i]. 2. T'[i] = "-" : S'[i] is simply an INSERTION. 3. Otherwise, S'[i] is a copy of T'[i] (with possible MUTATION).

我们可以用以下方式来给s(a,b)打分： 1. Match: +1 , e.g. s('C' ,'C' ) = 1. 2. Mismatch: -1, e.g. s('E' , 'A' ) = −1. 3. Insertion/Deletion: -3, e.g. s('C' , '-' ) = −3.

使用对齐，我们可以找到最相似的来源，并且同样两个序列，通过不同的插入空格的方式我们可以得到不同的值。

INPUT:Two sequences S and T, |S| = m, and |T| = n; OUTPUT:To identify an alignment of S and T that maximizes a pre-deﬁned scoring function. *** 这里也有三种需要考虑的情况： 1. \(S_m\) comes from \(T_n\):S从T产生 2. \(S_m\) is an INSERTION：若S的最后一个字母多敲了 3. \(S_m\) comes from T[1..n − 1]：若S少敲了

note:蓝色框表示子问题

因此，我们可以将子问题的一般式设计为S的前缀(S[1..i])和T的的前缀(T[1..j])。最优解可以被表示为OPT(i,j). \[OPT(i,j) = max \left\{\begin{array}{lr}s(S_i,T_j) + OPT(i-1, j-1) \\s('-',T_j) + OPT(i, j-1) \\s(S_i,'-') + OPT(i-1, j)\end{array}\right.\]

Needleman-Wunsch(S, T)
    for i = 0 to m; do   \\简单的初始化，为了方便计算
        OPT[i, 0] = −3 ∗ i; 
    end for 
    for j = 0 to n; do 
        OPT[0, j] = −3 ∗ j; 
    end for 
    for i = 1 to m do 
        for j = 1 to n do 
            \\从三个单元里各自取了一些分，取最大
            OPT[i,j]=max{OPT[i−1,j−1]+s(Si,Tj),OPT[i-1,j]−3,OPT[i,j−1]−3};  
        end for 
    end for 
    return OPT[m, n] ;

之后通过回溯找到最优对齐方式（开一个表格方便回溯）：

在实践中，有许多中对齐方式可以达到与最优比对相似的效果，被称作次优比对。次优比对可以分为两类：1)类似的次优比对，2)不同的次优比对。

为了找到类似的次优对齐，我们使用采样技术追溯动态编程矩阵，即，不是在每个步骤采用最高得分选项，而是基于三个选项的值进行概率选择。e.g.将4以一定的概率回到之前的三个点，找一百回，用聚类的算法找到聚类中心。（最robust）

优化

若输入的数据很大（e.g.输入了两篇文章）这个算法面临了三个问题： 1. 占用空间太大 2. 用时太长 3. Local

Space eﬃcient algorithm:

Reducing the space requirement from O(mn) to O(m + n) (D. S. Hirschberg, 1975).

若只计算分数而不记录对齐信息，占用的空间很小。因为我们仅需占用2个数组。绿色数组：已填，蓝色数组：待填，一旦把蓝色的数组填完，绿色的数组就没用了。白色的部分都不需要存。

Prefix Space Efficient Alignment(S, T, score)
    for i = 0 to m do 
        score[i] = −3 ∗ i;   \\绿色数组
    end for 
    for i = 1 to m do 
        newscore[0] = 0;      \\蓝色数组
        for j = 1 to n do 
            newscore[j] = max{score[j − 1] + s(S i , T j ), score[j] 3, newscore[j − 1] − 3}; 
        end for 
        for j = 1 to n do 
            score[j] = newscore[j]; 
        end for 
    end for 
    return score[n];

相应地，我们也可以使用S和T的后缀获得分数和对齐方式。

但是这种方式无法回溯对齐信息。因此，一种更聪明的方式是我们可以将S分为两半(where \(S_{\frac{m}{2}}\)is aligned to,denoted as q)，分别计算对齐信息。 \[OPT(S,T) = OPT(S[1...\frac{m}{2}],T[1..q])+OPT(S[\frac{m}{2}+1..m],T[q+1..n])\]

Linear Space Alignment( S, T )
    Allocate two arrays f and b; each array has a size of m Prefix Space Efficient Alignment(S[1.. m ], T, f); 
    Suffix Space Efficient Alignment(S[ m + 1..m], T, b); 
    Let q = argmaxi (f[i] + b[i]); 
    Free arrays f and b; 
    Record aligned-position < m/2 , q > in an array A; 
    Linear Space Alignment(S[1.. m ], T[1..q]); 
    Linear Space Alignment(S[ m + 1..m], T[q + 1..n]); 
    return A;

先把S分为恰好左一半（前缀，forward）和右一半（后缀，backward），拿'OCUR'与T的总体作比较.从图中可以看出，分数一定是由S前一半的上半部分和后一半的下半部分产生。

由此，所需的空间仅为\(O(m+n)\).

Time complexity

我们可以发现，足够相似的是对角线，因此我们可以只关心条带内。 Banded DP仅需花费\(O(\alpha n)\)的时间复杂度。它为线性的算法，比原来快得多，条带外的部分我们可以不用考虑。

Local

全局比对：识别两个完整序列之间的相似性。

局部对齐：我们通常希望找到相似的段（子序列）。局部对齐的目的是识别两个序列的相似区段。其他区域可以被视为独立的，因此形成“随机匹配”。

通过增加额外的概率来改变递归： \[OPT(i,j) = max \left\{\begin{array}{lr}0 \\s(S_i,T_j) + OPT(i-1, j-1) \\s('-',T_j) + OPT(i, j-1) \\s(S_i,'-') + OPT(i-1, j)\end{array}\right.\] 其中0对应一个新的对齐。它与旧的对齐无关。

与从右下角回溯不同，这里从最大的项开始回溯，13为相似的终点，右下角的7为相似+不同。