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

最长公共子序列

问题描述

1. 概念解释
   1. 子序列：给定一个序列$X=&lt;x_{1},x_{2},...,x_{m}&gt;$X=<x1​,x2​,...,xm​>,另一个序列$Z=&lt;z_{1},z_{2},...,z_{k}&gt;$Z=<z1​,z2​,...,zk​>满足如下条件时称为$X$X的子序列，即存在一个严格递增的$X$X的下标序列$&lt;i_{1},i_{2},i_{3},...,i_{k}&gt;$<i1​,i2​,i3​,...,ik​>,对所有$j=1,2,...,k$j=1,2,...,k,满足$x_{i_{j}}=z_{j}$xij​​=zj​。
   2. 公共子序列：给定两个序列$X$X和$Y$Y，如果$Z$Z既是$X$X的子序列，又是$Y$Y的子序列，则称之为$X$X和$Y$Y的公共子序列。
2. 最长公共子序列问题（longest-common-subsequence problem ，简称LCS问题）
   给定两个序列$X=&lt;x_{1},x_{2},...,x_{m}&gt;$X=<x1​,x2​,...,xm​>和$Y=&lt;y_{1},y_{2},...,y_{n}&gt;$Y=<y1​,y2​,...,yn​>，求$X$X和$Y$Y长度最大的公共子序列。

问题求解

3. 是否可以使用动态规划？
   1. 是否满足最优子结构？
      1. 给出一个定义：前缀—给定一个序列$X=&lt;x_{1},x_{2},...,x_{m}&gt;$X=<x1​,x2​,...,xm​>，对于$i_{1},i_{2},i_{3},...,i_{m}$i1​,i2​,i3​,...,im​，定义$X$X的第$i$i前缀为$X_{i}=&lt;x_{1},x_{2},...,x_{i}&gt;$Xi​=<x1​,x2​,...,xi​>。
      2. 给出一个定理：（LCS的最优子结构），令$X=&lt;x_{1},x_{2},...,x_{m}&gt;$X=<x1​,x2​,...,xm​>和$Y=&lt;y_{1},y_{2},...,y_{n}&gt;$Y=<y1​,y2​,...,yn​>为两个序列，$Z=&lt;z_{1},z_{2},...,z_{k}&gt;$Z=<z1​,z2​,...,zk​>为$X$X和$Y$Y的任意LCS。
         a. 如果$x_{m}=y_{n}$xm​=yn​，则$Z_{k}=x_{m}=y_{n}$Zk​=xm​=yn​且$Z_{k-1}$Zk−1​是$X_{m-1}$Xm−1​和$Y_{n-1}$Yn−1​的一个LCS。
         b.如果$x_{m}≠y_{n}$xm​̸​=yn​,那么如果$z_{k}≠x_{m}$zk​̸​=xm​，则$Z$Z是$X_{m-1}$Xm−1​和$Y$Y的一个LCS。
         c. 如果$x_{m}≠y_{n}$xm​̸​=yn​,那么如果$z_{k}≠y_{n}$zk​̸​=yn​，则$Z$Z是$X$X和$Y_{n-1}$Yn−1​的一个LCS。
         由此，我们可以看出，LCS问题满足最优子结构。
   2. 是否满足子问题重叠？
      显然，在求解$X=&lt;x_{1},x_{2},...,x_{m}&gt;$X=<x1​,x2​,...,xm​>和$Y=&lt;y_{1},y_{2},...,y_{n}&gt;$Y=<y1​,y2​,...,yn​>的一个LCS时，需要求解器子问题，且子问题存在重复的部分，所以满足子问题重叠的特征。

刻画最长公共子序列特征

4. 由上述定理中最优子结构性质，可得递归公式：
   

计算LCS长度

5. 从上述公式可以看出，可以使用递归方式解决问题，但是因为子问题个数只有$O(mn)$O(mn)个，所以可以采用自底向上的动态规划问题。以下为自底向上的动态规划问题的伪代码，其中过程LCS-LENGTH接受两个序列$X=&lt;x_{1},x_{2},...,x_{m}&gt;$X=<x1​,x2​,...,xm​>和$Y=&lt;y_{1},y_{2},...,y_{n}&gt;$Y=<y1​,y2​,...,yn​>为输入。它将$c[i,j]$c[i,j]的值保存在表$c[0..m,0..n]$c[0..m,0..n]中，并按行主次序计算表项。过程还维护一个表$b[1..m,1..n]$b[1..m,1..n],帮助构造最优解。$b[i,j]$b[i,j]指向的表项对应计算$c[i,j]$c[i,j]时所选择的子问题的最优解。过程返回表b和表c,$c[m,n]$c[m,n]保存了$X$X和$Y$Y的LCS的长度。

LCS-LENGTH(X,Y)
m=X.length // 获得m的长度
n=Y.length
let b[1..m,1..n] and c[0..m,0..n] be new tables//新建二维数组b和c,b用于保存构建最长公共子序列的线索，c用于记录最长公共子序列的长度
for i = 0 to m//若其中一个子序列长度为0，则显然最长子序列长度为0
	c[i,0] = 0
for j = 0 to n
	c[0,j] = 0
for i = 1 to m//自底向上，按行主次序计算表项c,并找出最长公共子序列
	for j =1 to n
		if xi == yj//若序列对应位置相同，则子序列长度+1
			c[i,j] = c[i-1,j-1]+1
			b[i,j] = "↖"//保存重构子序列的线索，“↖”表示对应的两个序列i和j的位置为公共序列
		elseif c[i-1,j]≥c[i,j-1]//找出最长公共子序列
			c[i,j] = c[i-1,j]
			b[i,j] = "↑"//“↑”表示公共元素要想上寻找，即i-1
		else c[i,j] = c[i,j-1]//“←”表示公共元素要向左寻找，即j-1
			b[i,j] = "←"
return c and b

举例来说，如图所示：

构造LCS

6. 利用LCS-LENGTH返回的表b快速构造$X=&lt;x_{1},x_{2},...,x_{m}&gt;$X=<x1​,x2​,...,xm​>和$Y=&lt;y_{1},y_{2},...,y_{n}&gt;$Y=<y1​,y2​,...,yn​>的LCS，只需要按照如上所描述的方案即可逆序一次构造出LCS的所有元素（因为在找最大公共子序列时逻辑上就是逆序寻找的），以下给出递归函数，按正确的顺序打印出$X$X和$Y$Y的一个LCS。

PRINT-LCS(b,X,i,j)
	if i==0 or j ==0
		return
	if b[i,j] == "左上"
		PRINT-LCS(b,X,i-1,j-1)
		print Xi
	elseif b[i,j] == "↑"
		PRINT-LCS(b,X,i-1,j)
	else PRINT-LCS(b,X,i,j-1)

7. 算法改进：我们发现可以直接通过$c[i,j]$c[i,j]s所依赖的$c[i-1,j],c[i,j-1],c[i-1,j-1]$c[i−1,j],c[i,j−1],c[i−1,j−1]判断出计算$c[i,j]$c[i,j]时使用了这三项中的哪一项。因此我们可以用一个类似PRINT-LCS的过程在$O(m+n)$O(m+n)时间内完成重构LCS的工作，而不必使用表b。以下给出该方法的伪代码：

ENHANCE-PRINT-LCS(c,X,i,j)
	if c[i,j] > c[i-1,j] and c[i,j] > c[i,j-1]
		print Xi
		ENHANCE-PRINT-LCS(c,X,i-1,j-1)
	elseif c[i,j] == c[i-1,j]
		ENHANCE-PRINT-LCS（c,X,i-1,j）
	else
		ENHANCE-PRINT-LCS(c,X,i,j-1)

以下给出java实现的具体代码：

import java.util.Scanner;

public class LCS_LENGTH {
   public static void main(String[] args) {
       Scanner scanner = new Scanner(System.in);
       int keep = 1;//用于探测是否循环计算
       do{
           System.out.println("请输入第一个序列A");
           String A = scanner.next();
           char[] a1 = A.toCharArray();//将字符串变成数组
           System.out.println("请输入第二个序列B");
           String B = scanner.next();
           char[] b1 = B.toCharArray();
           //为了阅读方便，将输入的两个数组的长度都+1，且数组的第一个值为'0'
           int m = a1.length+1;
           int n = b1.length+1;
           char[] a = new char[m];
           char[] b = new char[n];
           a[0] ='0';
           b[0]='0';
           //数组的复制
           for(int i =1;i<m;i++){
               a[i]= a1[i-1];
           }
           for(int i =1;i<n;i++){
               b[i]= b1[i-1];
           }
           int[][] c = new int[m][n];//c用于保存当两个序列的长度为i和j时，最大子序列长度
           //设置当其中一个序列为空序列时，最大子序列长度为0
           for(int  i = 0;i<m;i++){
               c[i][0] = 0;
           }
           for(int i = 0;i<n;i++){
               c[0][i] = 0;
           }
           //自底向上计算最大子序列长度
           for(int i = 1;i<m;i++){//按行求解
               for(int j = 1;j<n;j++){
                   if(a[i]==b[j]){//若当前元素相等，则最大子序列长度+1
                       c[i][j] = c[i-1][j-1]+1;
                   }
                   //否则，选择较长的那一组序列
                   else if(c[i-1][j]>=c[i][j-1]){
                       c[i][j] = c[i-1][j];
                   }
                   else{
                       c[i][j] = c[i][j-1];
                   }
               }
           }
           System.out.println("A与B的一个最大公共子序列长度: "+c[m-1][n-1]+" ,且最大公共子序列为：");
           ENHANCE_PRINT_LCS(c,a,m-1,n-1);//重构最长子序列

           System.out.println("\n继续输入请输入1");
           keep = scanner.nextInt();
       }while( keep == 1);
   }
   //递归输出最长子序列
   public static void ENHANCE_PRINT_LCS(int[][] c,char[] a,int i,int j){
       if(i>=1&&j>=1&&c[i][j]> c[i-1][j]&&c[i][j]>c[i][j-1]){
           ENHANCE_PRINT_LCS(c,a,i-1,j-1);
           System.out.print(a[i]+" ");
       }else if(i>=1&&c[i][j]==c[i-1][j]){
           ENHANCE_PRINT_LCS(c,a,i-1,j);
       }else if(j>=1){
           ENHANCE_PRINT_LCS(c,a,i,j-1);
       }
   }
}

以下为测试部分：

以上为动态规划求解最长公共子序列的总结。