动态规划法（十）最长公共子序列（LCS）问题

你的名字 2022-05-22 01:11 173阅读 0赞

## 问题介绍 ##

给定一个序列X=<x1,x2,....,xm>  X =< x 1 , x 2 , . . . . , x m > ，另一个序列Z=<z1,z2,....,zk>  Z =< z 1 , z 2 , . . . . , z k > 满足如下条件时称为X的**子序列**：存在一个严格递增的X的下标序列<i1,i2,...,ik>  < i 1 , i 2 , . . . , i k > <script type="math/tex" id="MathJax-Element-3"> </script>，对所有的  j=1,2,...,k  j = 1 , 2 , . . . , k 满足  xij=zj.  x i j = z j .   
  给定两个序列  X  X 和Y Y,如果  Z  Z 同时是X X和  Y  Y 的子序列，则称Z Z是  X  X 和Y Y的 **公共子序列**。 **最长公共子序列（LCS）问题**指的是：求解两个序列  X  X 和Y Y的长度最长的公共子序列。 **例如**，序列  X=<A,B,C,B,D,A,B>  X =< A , B , C , B , D , A , B > 和  Y=<B,D,C,A,B,A>  Y =< B , D , C , A , B , A > 的最长公共子序列为  <B,C,B,A>  < B , C , B , A > <script type="math/tex" id="MathJax-Element-18"> </script>，长度为4。  
  本文将具体阐释如何用动态规划法（Dynamic Programming）来求解最长公共子序列（LCS）问题。

## 算法分析 ##

### 1. LCS的子结构 ###

给定一个序列X=<x1,x2,....,xm>  X =< x 1 , x 2 , . . . . , x m > ，对i=0,1,...,m  i = 0 , 1 , . . . , m ，定义X  X 的第i前缀为Xi=<x1,x2,....,xi> X i=<x 1,x 2, . . . . ,x i>,其中X0  X 0 为空序列。  
  （**LCS的子结构**）令X=<x1,x2,....,xm>  X =< x 1 , x 2 , . . . . , x m > 和Y=<y1,y2,....,yn>  Y =< y 1 , y 2 , . . . . , y n > 为两个序列，Z=<z1,z2,....,zk>  Z =< z 1 , z 2 , . . . . , z k > 为X  X 和Y Y的任意LCS，则：

1.  如果xm=yn,  x m = y n , 则zk=xm=yn  z k = x m = y n 且Zk−1  Z k − 1 是Xm−1  X m − 1 和Yn−1  Y n − 1 的一个LCS。
2.  如果xm≠yn,  x m ≠ y n , 则zk≠xm  z k ≠ x m 意味着Zk−1  Z k − 1 是Xm−1  X m − 1 和Y  Y 的一个LCS。
3.  如果xm≠yn, x m≠y n,则zk≠yn  z k ≠ y n 且Zk−1  Z k − 1 是X  X 和Yn−1 Yn − 1的一个LCS。

### 2. 构造递归解 ###

在求X=<x1,x2,....,xm>  X =< x 1 , x 2 , . . . . , x m > 和Y=<y1,y2,....,yn>  Y =< y 1 , y 2 , . . . . , y n > 的一个LCS时，需要求解一个或两个子问题：如果xm=yn  x m = y n ，应求解Xm−1  X m − 1 和Yn−1  Y n − 1 的一个LCS，再将xm=yn  x m = y n 追加到这个LCS的末尾，就得到X  X 和Y Y的一个LCS；如果xm≠yn  x m ≠ y n ，需求解Xm−1  X m − 1 和Y  Y 的一个LCS与X X和Yn−1  Y n − 1 的一个LCS，两个LCS较长者即为X  X 和Y Y的一个LCS。当然，可以看出，LCS问题容易出现重叠子问题，这时候，就需要用动态规划法来解决。  
  定义c\[i,j\]  c \[ i , j \] 表示Xi  X i 和Yj  Y j 的LCS的长度。如果i=0  i = 0 或j=0  j = 0 ，则c\[i,j\]=0.  c \[ i , j \] = 0. 利用LCS的子结构，可以得到如下公式：

c\[i,j\]=⎧⎩⎨⎪⎪0,若i=0或j=0c\[i−1,j−1\]\+1,若i,j>0且xi=yjmax(c\[i,j−1\],c\[i−1,j\]),若i,j>0且xi≠yj  c \[ i , j \] = \{ 0 , 若 i = 0 或 j = 0 c \[ i − 1 , j − 1 \] + 1 , 若 i , j > 0 且 x i = y j max ( c \[ i , j − 1 \] , c \[ i − 1 , j \] ) , 若 i , j > 0 且 x i ≠ y j

### 3. 计算LCS的长度 ###

计算LCS长度的伪代码为LCS-LENGTH. 过程LCS-LENGTH接受两个子序列X=<x1,x2,....,xm>  X =< x 1 , x 2 , . . . . , x m > 和Y=<y1,y2,....,yn>  Y =< y 1 , y 2 , . . . . , y n > 为输入。它将c\[i,j\]  c \[ i , j \] 的值保存在表c  c 中，同时，维护一个表b b，帮助构造最优解。过程LCS-LENGTH的伪代码如下：

LCS-LENGTH(X, Y):
    m = X.length
    n = Y.length
    let b[1...m, 1...n] and c[0...m, 0...n] be new table
    
    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 x[i] == y[j]
               c[i,j] = c[i-1, j-1]+1
               b[i,j] = 'diag'
    
            elseif 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

### 4. 寻找LCS ###

为了寻找X  X 和Y Y的一个LCS， 我们需要用到LCS-LENGTH过程中的表b  b ，只需要简单地从b\[m,n\] b \[ m , n \]开始，并按箭头方向追踪下去即可。当在表项b\[i,j\]  b \[ i , j \] 中遇到一个’diag’时，意味着xi=yj  x i = y j 是LCS的一个元素。按照这种方法，我们可以按逆序依次构造出LCS的所有元素。伪代码PRINT-LCS如下：

PRINT-LCS(b, X, i, j):
        if i == 0 or j == 0
            return
        if b[i,j] == 'diag'
            PRINT-LCS(b, X, i-1, j-1)
            print x[i]
        elseif b[i,j] == 'up':
            PRINT-LCS(b, X, i-1, j)
        else
            PRINT-LCS(b, X, i, j-1)

## 程序实现 ##

有了以上对LCS问题的算法分析，我们不难写出具体的程序来实现它。下面将会给出Python代码和Java代码，供读者参考。  
  完整的Python代码如下：

import numpy as np
    
    # using dynamic programming to solve LCS problem
    # parameters: X,Y -> list
    def LCS_LENGTH(X, Y):
        m = len(X) # length of X
        n = len(Y) # length of Y
    
        # create two tables, b for directions, c for solution of sub-problem
        b = np.array([[None]*(n+1)]*(m+1))
        c = np.array([[0]*(n+1)]*(m+1))
    
        # use DP to sole LCS problem
        for i in range(1, m+1):
            for j in range(1, n+1):
                if X[i-1] == Y[j-1]:
                    c[i,j] = c[i-1,j-1]+1
                    b[i,j] = 'diag'
                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'
        #print(b)
        #print(c)
        return b,c
    
    # print longest common subsequence of X and Y
    def print_LCS(b, X, i, j):
    
        if i == 0 or j == 0:
            return None
        if b[i,j] == 'diag':
            print_LCS(b, X, i-1, j-1)
            print(X[i-1], end=' ')
        elif b[i,j] == 'up':
            print_LCS(b, X, i-1, j)
        else:
            print_LCS(b, X, i, j-1)
    
    X = 'conservatives'
    Y = 'breather'
    
    b,c = LCS_LENGTH(X,Y)
    print_LCS(b, X, len(X), len(Y))

输出结果如下：

e a t e

完整的Java代码如下：

package DP_example;
    
    import java.util.Arrays;
    import java.util.List;
    
    public class LCS {
        // 主函数
        public static void main(String[] args) {
            // 两个序列X和Y
            List<String> X = Arrays.asList("A","B","C","B","D","A","B");
            List<String> Y = Arrays.asList("B","D","C","A","B","A");
    
            int m = X.size(); //X的长度
            int n = Y.size(); // Y的长度
            String[][] b = LCS_length(X, Y); //获取维护表b的值
    
            print_LCS(b, X, m, n); // 输出LCS
        }
    
        /* 函数LCS_length：获取维护表b的值 传入参数： 两个序列X和Y 返回值： 维护表b */
        public static String[][] LCS_length(List X, List Y){
            int m = X.size(); //X的长度
            int n = Y.size(); // Y的长度
            int[][] c = new int[m+1][n+1];
            String[][] b = new String[m+1][n+1];
    
            // 对表b和表c进行初始化
            for(int i=1; i<m+1; i++){
                for(int j=1; j<n+1; j++){
                    c[i][j] = 0;
                    b[i][j] = "";
                }
            }
    
            // 利用自底向上的动态规划法获取b和c的值
            for(int i=1; i<m+1; i++){
                for(int j=1; j<n+1; j++){
                    if(X.get(i-1) == Y.get(j-1)){
                        c[i][j] = c[i-1][j-1]+1;
                        b[i][j] = "diag";
                    }
                    else if(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 b;
        }
    
        // 输出最长公共子序列
        public static int print_LCS(String[][] b, List X, int i, int j){
    
            if(i == 0 || j == 0)
                return 0;
    
            if(b[i][j].equals("diag")){
                print_LCS(b, X, i-1, j-1);
                System.out.print(X.get(i-1)+" ");
            }
            else if(b[i][j].equals("up"))
                print_LCS(b, X, i-1, j);
            else
                print_LCS(b, X, i, j-1);
    
            return 1;
        }
    }

输出结果如下：

B C B A

## 参考文献 ##

1.  算法导论（第三版） 机械工业出版社
2.  [https://www.geeksforgeeks.org/longest-common-subsequence/][https_www.geeksforgeeks.org_longest-common-subsequence]

***注意：***本人现已开通两个微信公众号： 因为Python（微信号为：python\_math）以及轻松学会Python爬虫（微信号为：easy\_web\_scrape）， 欢迎大家关注哦~~

[https_www.geeksforgeeks.org_longest-common-subsequence]: https://www.geeksforgeeks.org/longest-common-subsequence/