个人博客

秦琦琛

0%

最长公共子序列问题-动态规划

发表于 更新于 分类于

最长公共子序列问题-动态规划

一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X={x1,x2,…,xm}，则另一序列Z={z1, z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1, i2,…, ik}使得对于所有j=1,2,…, k，有: zj=xij。例如，序列Z={B,C, D,B}是序列X={A,B,C,B,D,A,B}的子序列，相应的递增下标序列为{2,3,5,7}。

给定两个序列X和Y，当另一个序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。

例如，若X={A,B,C,B,D,A,B}，Y={B, D,C,A,B,A}，则序列{B,C,A}是X和Y的一个公共子序列，但它不是X和Y的一个最长公共子序列。序列{B,C,B,A}也是X和Y的一个公共子序列，其长度为4，而且它是X和Y的最长公共子序列，因为X和Y没有长度大于4的公共子序列。

穷举搜索法是最容易想到的算法，对X的所有子序列，检查它是否也是Y的子序列。从而确定它是否为X和Y的公共子序列。并且在检查过程中记录最长的公共子序列。X的所有子序列都检查过后即可求出X和Y的最长公共子序列。X的每个子序列相应于下标集{1,2, …,m}的一个子集，因此有2m个不同子序列，从而穷举搜索法需要指数时间。

事实上，最长公共子序列问题具有最优子结构性质。

设序列X={x1,x2, …, xm}和Y={y1,y2, …,yn}的最长公共子序列为Z={z1,z2, …,zk},则

①若xm=yn， 则zk=xm=yn, 且Zk-1是Xm-1和Yn-1的最长公共子序列。

②若xm≠yn,且zk≠xm，则Z是Xm-1 和Y的最长公共子序列。

③若xm#yn且zk#yn，则Z是X和Yn-1的最长公共子序列。 其中，Xm-1={x1,x2, …，xm-1}，Yn-1={y1,y2, …，yn-1}，Zn-1={z1,z2, …，zk-1}。

​ 由最长公共子序列问题的最优子结构性质可知,要找出X={x1,x2,…,xm}和Y={y1, y2,…,yn}的最长公共子序列，可按以下方式递归地进行:

1.当xm=yn,时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm (xm=yn)，即可得X和Y的最长公共子序列。

2.当xm≠yn,时，必须解两个子问题，即找出Xm-1和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列。这两个公共子序列中较长者即为X和Y的最长公共子序列。

​ 由此递归结构容易看到，最长公共子序列问题具有子问题重叠性质，即计算Xm-1和Yn-1的最长公共子序列。

​ 首先建立子问题最优值的递归关系,用c[i][j]记录序列Xi和Yj的最长公共子序列的长度。其中，Xi={x1,x2,…,xi}:Yj={y1,y2,…,yj}，当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。

​ 所以，此时c[i][j]=0。其他情况下，由最优子结构性质可建立递归关系如下:

image-20211228115331927

image-20211228115357621

image-20211228115408695

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
int **c 存放最长公共子序列长度
int **b 存放最长公共子序列 节点
**/
void DP_Length(int m,  int n, char *x, char *y, int **c, int **b){
    int i , j ;
    for( i = 0 ; i < m ; i ++ ){
        c[i][0] = 0 ;
    }
    for( j = 0 ; j < n ; j ++ ){
        c[0][j] = 0 ;
    }
    for( i = 1 ; i <= m ; i ++ ){
        for( j = 1 ; j <= n ; j ++ ){
            if( x[i] == y[j] ){
                c[i][j] = c[i-1][j-1] + 1 ;
                b[i][j] = 1 ;
            }else if( c[i-1][j] > c[i][j-1] ){
                c[i][j] = c[i-1][j] ;
                b[i][j] = 2 ;
            }else{
                c[i][j] = c[i][j-1] ;
                b[i][j] = 3 ;
            }
        }
    }
}

void Print_Length(int i , int j , char *x , int **b){
    if( i == 0 || j == 0 ){
        return ;
    }
    if( b[i][j] == 1 ){
        Print_Length(i-1,j-1,x,b);
        cout<<x[i];
    }else if( b[i][j] == 2 ){
        Print_Length(i-1,j,x,b);
    }else{
        Print_Length(i,j-1,x,b);
    }
}