首页 > 专题系列 > 算法分析 > 动态规划(4)-最长公共子序列
2014
03-01

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

继续用典型问题来讨论动态规划的两个特性(重叠子问题和最优子结构)。最长公共子序列(LCS)问题描述:

给定两个序列,找出在两个序列中同时出现的最长子序列的长度。一个子序列是出现在相对顺序的序列,但不一定是连续的。例如,“ABC”,“ABG”,“BDF”,“AEG”,“acefg“,..等都是”ABCDEFG“ 序列。因此,长度为n的字符串有2 ^ n个不同的可能的序列。

注意最长公共子串(Longest CommonSubstring)和最长公共子序列(LongestCommon Subsequence, LCS)的区别:子串(Substring)是串的一个连续的部分,子序列(Subsequence)则是从不改变序列的顺序,而从序列中去掉任意的元素而获得的新序列;更简略地说,前者(子串)的字符的位置必须连续,后者(子序列LCS)则不必。比如字符串acdfg同akdfc的最长公共子串为df,而他们的最长公共子序列是adf。LCS可以使用动态规划法解决。

这是一个典型的计算机科学问题,基础差异(即输出两个文件之间的差异文件比较程序),并在生物信息学有较多应用。

例子:
输入序列“ABCDGH”和“AEDFHR” 的LCS是“ADH”长度为3。
输入序列“AGGTAB”和“GXTXAYB”的LCS是“GTAB”长度为4。

这个问题的直观的解决方案是同时生成给定序列的所有子序列,找到最长匹配的子序列。此解决方案的复杂性是指数的。让我们来看看如何这个问题 (拥有动态规划(DP)问题的两个重要特性):

1)最优子结构:
设输入序列是X [0 .. m-1]和Y [0 .. n-1],长度分别为m和n。和设序列 L(X [0 .. m-1],Y[0 .. n-1])是这两个序列的LCS的长度。

以下为L(X [0 .. M-1],Y [0 .. N-1])的递归定义:

如果两个序列的最后一个元素匹配(即X [M-1] == Y [N-1])
L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])

如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-2])

例子:

1)考虑输入字符串“AGGTAB”和“GXTXAYB”。最后一个字符匹配的字符串。这样的LCS的长度可以写成:
L(“AGGTAB”, “GXTXAYB”) = 1 + L(“AGGTA”, “GXTXAY”)

2)考虑输入字符串“ABCDGH”和“AEDFHR。最后字符不为字符串相匹配。这样的LCS的长度可以写成:
L(“ABCDGH”, “AEDFHR”) = MAX ( L(“ABCDG”, “AEDFHR”), L(“ABCDGH”, “AEDFH”) )

因此,LCS问题有最优子结构性质!

2)重叠子问题:
以下是直接的递归实现,  遵循上面提到的递归结构。(有兴趣的读者可以按照前面讲的记忆化存储来实现)

/* 简单的递归实现LCS问题 */
#include<stdio.h>
#include<stdlib.h>

int max(int a, int b);

/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
int lcs( char *X, char *Y, int m, int n )
{
   if (m == 0 || n == 0)
     return 0;
   if (X[m-1] == Y[n-1])
     return 1 + lcs(X, Y, m-1, n-1);
   else
     return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
}

/* Utility function to get max of 2 integers */
int max(int a, int b)
{
    return (a > b)? a : b;
}

/* 测试上面的函数 */
int main()
{
  char X[] = "AGGTAB";
  char Y[] = "GXTXAYB";

  int m = strlen(X);
  int n = strlen(Y);

  printf("Length of LCS is %d\n", lcs( X, Y, m, n ) );

  getchar();
  return 0;
}

上面直接的递归方法的时间复杂度为O(2 ^ n).(在最坏的情况下。X和Y不匹配的所有字符即LCS的长度为0)。
按照到上述的实现,下面是对输入字符串“AXYT”和“AYZX”的部分递归树:

                         lcs("AXYT", "AYZX")
                       /                 \
         lcs("AXY", "AYZX")            lcs("AXYT", "AYZ")
         /            \                  /               \
lcs("AX", "AYZX") lcs("AXY", "AYZ")   lcs("AXY", "AYZ") lcs("AXYT", "AY")

在上述部分递归树,LCS(“AXY”,“AYZ”)被调用两次。如果我们绘制完整的递归树,那么我们可以看到,我们可以看到很多重复的调用。所以这个问题有重叠的子结构性质,可使用memoization的或打表来避免重新计算。下面是用动态规划(打表)解决LCS问题:

/ *动态规划实现的LCS问题* /
#include<stdio.h>
#include<stdlib.h>

int max(int a, int b);

/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
int lcs( char *X, char *Y, int m, int n )
{
   int L[m+1][n+1];
   int i, j;

   /* Following steps build L[m+1][n+1] in bottom up fashion. Note 
      that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
   for (i=0; i<=m; i++)
   {
     for (j=0; j<=n; j++)
     {
       if (i == 0 || j == 0)
         L[i][j] = 0;

       else if (X[i-1] == Y[j-1])
         L[i][j] = L[i-1][j-1] + 1;

       else
         L[i][j] = max(L[i-1][j], L[i][j-1]);
     }
   }

   /* L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] */
   return L[m][n];
}

/* Utility function to get max of 2 integers */
int max(int a, int b)
{
    return (a > b)? a : b;
}

/*测试上面的函数 */
int main()
{
  char X[] = "AGGTAB";
  char Y[] = "GXTXAYB";

  int m = strlen(X);
  int n = strlen(Y);

  printf("Length of LCS is %d\n", lcs( X, Y, m, n ) );

  getchar();
  return 0;
}

参考:http://www.algorithmist.com/index.php/Longest_Common_Subsequence

http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/


  1. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])

  2. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])

  3. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。