归档 技术 呓语

动态规划(4)—算法导论(19)
2016年06月08日 22:32

1. 写在前面

在前三篇博客中，分别介绍了钢条切割问题，以及对动态规划问题做了一个小结。在这篇博客中，将继续介绍一个动态规划问题：最长公共子序列问题。

2. 提出问题

我们有时候会遇到比较两个字符串“相似度”的问题。例如，比较给定字符串X和Y的相似度，其中X = ABCBDAB，Y = BDCABA。根据需求的不同，“相似度”可以有不同的的定义。比如可以定义，若一个字符串是另一个字符串的子串，则它们相似；再比如，若我们只关心字符串中字符的出现的频率，则可定义，若一个字符串中各字符出现的频率与另一字符串中各字符出现的频率相同，则它们相似。

最长子序列（longest-common-subsequence，LCS） 便可看成是一种相似度的描述：若存在第三个字符串满足，它的所有字符在被比较的两个字符串中都以相同的顺序出现（但不必连续出现），则被比较的两个字符串相似，且第三个字符串越长，则认为被比较的两个字符串越相似，该字符串被称为被比较的两个字符串的最长子序列。

以前面的问题为例，比较X = ABCBDAB和Y = BDCABA的相似度。我们可以找到第三个字符串Z1 = BCA，它的每个字符在X和Y中都以下标递增的顺序出现过（在X中下标分别是<1,2,5><1, 2, 5>，在Y中是<0,2,3><0, 2, 3>），但Z1不是X和Y的最长公共子序列，因为存在更长的公共子序列 Z2 = BCBA 或 Z3 = BDAB。

下面给出最长子序列问题的形式化描述：

对于给定的子序列X=x1x2...xnX=x_1x_2...x_n和Y=y1y2...ynY = y_1y_2...y_n，找出一个最长的严格递增的X的下标序列i1i2...ini_1i_2...i_n，对所有的j=1,2,3,...,kj=1, 2, 3, ..., k，满足Xij=YjX_{i_j} = Y_j。

3. 解决问题

3.1 暴力求解

最简单算法是，直接考察字符串X的所有下标组合的可能性。对于长度为n的字符串，共需考察2n2^n种情况。因此暴力求解的运行时间是指数阶，对于较长的序列是不适用的。

3.2 动态规划

对于该问题，直觉告诉我们，可能可以使用动态规划来求解。

正如之前小结中给出的那样，一个问题能够使用动态规划方法来求解，必须满足两个必要条件：1. 最优子结构；2. 子问题折叠

3.2.1 最优子结构

令X=x1x2...xm,Y=y1y2...ynX=x_1x_2...x_m, Y = y_1y_2...y_n为两序列，Z=z1z2...zkZ=z_1z_2...z_k为X和Y的任意LCS，可得到如下结论：

  1. 如果xm=ynx_m = y_n，则zk=xm=ynz_k = x_m = y_n且Zk−1Z_{k-1}是Xm−1X_{m-1}和Yn−1Y_{n-1}的一个LCS；
  2. 如果xm≠ynx_m \neq y_n，则zk≠xmz_k \neq x_m意味着ZZ是Xm−1X_{m-1}和YY的一个LCS；
  3. 如果xm≠ynx_m \neq y_n，则zk≠ynz_k \neq y_n意味着ZZ是XX和Yn−1Y_{n-1}的一个LCS；

下面对如上结论做一下说明：

以上结论立即告诉我们，两个序列的LCS包含两个序列的前缀的LCS，因此LCS问题具有最优子结构性质。

3.2.2 子问题折叠

我们用c[i,j]c[i, j]表示xix_i和yiy_i的LCS的长度，对于如上结论，我们可用一个简单的递归式加以描述：

c[i,j]={0若i = 0或j = 0c[i−1,j−1]+1若i, j > 0且xi=yimax⁡(c[i,j−1],c[i−1,j])若i, j > 0且xi≠yic[i,j]=\begin{cases} 0&\text{若i = 0或j = 0}\\ c[i-1, j-1] + 1&\text{若i, j > 0且$x_i = y_i$}\\ \max(c[i, j-1], c[i-1, j])&\text{若i, j > 0且$x_i \neq y_i$}\\ \end{cases}

从递归中不难看出，LCS问题的许多子问题是被另外一些子问题共享的，即满足子问题折叠性质。

3.2.3 解决方案

有了3.2.1与3.2.2的分析，根据递归式，我们可以很容易的设计出一个动态规划算法来求解LCS问题。如下给出的是一个Java的实现方案（自底向上）：

/**
 * 计算c[i][j]
 */
public static int[][] step1(String x, String y) {
    if (x == null || x.isEmpty() || y == null || y.isEmpty()) {
        return null;
    }
    int[][] c = new int[x.length()+1][y.length()+1];
    // case1：i=0或j=0，c[i][j] = 0
    // 对于java，可以不做以下步骤，因为默认就已初始化为0
//        for (int i = 0; i < x.length(); i++) {
//            c[i][0] = 0;
//        }
//        for (int i = 0; i < y.length(); i++) {
//            c[0][i] = 0;
//        }
    // 自底向上求解
    for (int i = 1; i < x.length() + 1; i++) {
        for (int j = 1; j < y.length() + 1; j++) {
            // case2：若i, j > 0且x_i = y_i,则c[i, j] = c[i-1][j-1]+1
            if (x.charAt(i - 1) == y.charAt(j - 1)) {
                c[i][j] = c[i - 1][j - 1] + 1;
            } else {// case3：若i, j > 0且x_i = y_i,则c[i, j] = c[i-1][j-1]
                c[i][j] = Math.max(c[i][j - 1], c[i - 1][j]);
            }
        }
    }
    return c;
}

/**
 * 根据c[i][j]构造出LCS
 */
public static String step2(String x, int[][] c){
    if(c == null || c.length == 0 || c[0].length == 0){
        return null;
    }
    StringBuilder result = new StringBuilder();
    for (int i = c.length - 1, j = c[0].length - 1; i > 0 && j > 0;) {
        if(c[i][j] == c[i - 1][j]){
            i--;
        }else if(c[i][j] == c[i][j - 1]){
            j--;
        }else{
            result.append(x.charAt(i-1));
            i--;
            j--;
        }
    }
    return result.reverse().toString();
}

测试代码如下：

public static void main(String[] args) {
    int[][] c = step1("ABCBDAB", "BDCABA");
    String result = step2("ABCBDAB", c);
    System.out.println(result); // BCBA
}

3.2.4 时间效率

可以很容易看出，以上动态规划算法的时间效率为 Θ(mn)\Theta(mn)。

End