发布时间 : 星期一 文章最长公共子序列问题（最新）更新完毕开始阅读e29ba105bed5b9f3f90f1c83
算法作业：
LCS 问 题
作业要求：设计一个算法求出两个序列的所有LCS，分析最坏情况，用“会计方法”证明利用b[i][j]求出所有LCS的算法在最坏情况下时间复杂度为O(Cnm?m)
1、 算法思路：
根据最长公共子序列问题的性质，即经过分解后的子问题具有高度重复性，并且具有最优子结构
性质，采用动态规划法求解问题。设X={x1, x2, … , xn}, Y={y1, y2, … , ym}, 首先引入二维数组C[i][j]记录Xi和Yj的LCS的长度，定义C[i][j]如下：
C[i][j]??0，i?0或j?0 C[i?1][j?1]?1,i,j?0且xi?yjmax{C[i?1][j],C[i][j?1]},i,j?0且xi?yj
为了构造出LCS，还需要使用一个二维数组b[m][n]，b[i][j]记录C[i][j]是通过哪个子问题的值求得的，以决定搜索的方向，欲求出所有的LCS，定义数组b如下： 设1-对角线方向;2-向上;3-向左;4-向上或向左 若X[i]=Y[j],b[i][j] = 1,
若C[i-1][j]
根据以上辅助数组C和b的定义，算法首先需要求出这两个数组， C[m][n]中记录的最长公共子序列的长度，b中记录了查找子序列元素的搜索方向。
利用C和b的信息，Find_All_LCS可以采用回溯法求出所有的LCS。基本思路如下：使用一个辅助数组记录每次调用Find_All_LCS得到的LCS中的元素，每次递归调用一次Find_All_LCS，进入一个新的执行层，首先要判断当前处理的两个子序列长度是否大于等于0 ，若不满足，则该层的递归结束，返回上一层；然后再判断当前得到的子序列是否等于数组C中求出的最长公共子序列长度，若等于，则说明算法执行到此已经得到一个LCS，按序输出；若不等于，此时根据数组b中记录的搜索方向继续搜索，特别要说明的是，当b[i][j]=4时，即要向上或向左，需要对这两个方向分别调用Find_All_LCS，保证沿着这两个方向上LCS元素不被漏掉，都可以搜索到；若b[i][j]=1，即沿对角线方向搜索前进时，此时元素X[i]为LCS中的元素，存放至辅助数组中去，同时将当前已经求得的LCS长度增1，当递归调用Find_All_LCS从b[i][j]=1处时，需要回溯一步，搜索其它路径上可能为LCS中的元素。当所有的可能路径都已经搜索完，算法结束。 对于某些情况会输出重复的LCS，这是因为算法在沿不同路径搜索时可能会出现相同的LCS序列。 2、 时间复杂度分析
由上述对Find_All_LCS 算法的分析可知，求出所有的LCS实际上是根据搜索的方向信息遍历所
有的路径找出满足条件的元素集合。因此，除求解辅助数组C和b所用的O(mn+m+n)的执行时间外，Find_All_LCS的时间复杂度取决于所遍历路径数。而路径数是由搜索方向决定的。显然算法在最好的情况下，即m=n并且b中所有的值都指示沿着对角线方向搜索，时间复杂度为O(n). 相反，当X和Y序列不存在公共子序列时为算法的最坏情况，此时C中所有值都等于0，数组b中所有的值都指示要分别沿两个不同的方向（向左或向上）搜索，这种情况下每处理一次X[i],Y[j]时总是要沿两个方向分别调用Find_All_LCS，遇到i=0或j=0时返回，直到搜索完所有的可能路径才结束，最坏情况下的搜索矩阵如下图所示：
由此可知，要确定最坏情况的时间复杂度，就是要计算出从点(m,n)到i=0或j=0（除(i,j)=（0，0）外）的所有路径。求解转化为组合数学中的路径数问题。建立一个直角坐标系如上图中所示，对于坐标系中的点可以沿向上或向左两个方向前进，设点S(m,n),x轴上的坐标点
P1(1,0),P2(2,0),...,Pi(i,0),...,Pm(m,0)，y轴上的系列坐标点Q1(0,1),Q2(0,2),...,Qj(0,j),...,Qn(0,n),其
中1?i?n,1?j?m.
因为Pi和Qj是搜索路径的边界上的点，点Pi?1不能直接到达点Pi，点Qj?1也不能直接到达Qj，所以点S(m,n)到P1,P2,...,Pi,...,Pm和Q1,Q2,...,Qj,...,Qn的路径数等价于S(m,n)到点
P1'(1,1),P2'(2,1),.Pi.'(i.,1),,.Pm.'(.m,,1)和点Q1'(1,1),Q2'(1,2),...,Qj'(1,j),...,Qn'(1,n)的路径数，又因为
点(m,n)到(i,j)路径数为Cm?n?i?j，设总路径数为t，则有
nmn?im?1?n?in?it??Ci?1??Cj?1m?jn?1?m?j
根据组合数学的基本知识可得：
nmn?im?1?n?it??Ci?1n?1n?1n??Cj?1m?jn?1?m?j?Cn?m?2?Cn?m?3?...?Cm?Cm?1?Cn?m?2?Cn?m?3?...?Cn?Cn?1 ?Cn?m?1?Cn?m?1?Cn?m?1?Cn?m?1?Cn?m??Cn?mmm?1n?1n?n?210??m?1m?210?[注]：参考卢开澄编著的《组合数学（第3版）》P34-P38
最坏情况下算法搜索的所有路径为从S到P1,P2,...,Pi,...,Pm和Q1,Q2,...,Qj,...,Qn的所有路径数Cn?m，因此算法在最坏情况下的时间复杂度为O(Cn?m). 3、 算法实现
mm/*文件名：FindLongestCommonSequence.cpp 说明：求出两个序列中所有的最长公共子序列 日期:2005/10/12*/ #include
using namespace std;
int C[MAXSIZE][MAXSIZE] ; //记录序列X和Y的LCS的长度
int B[MAXSIZE][MAXSIZE] ;//记录二维数组C是通过哪一个子问题的值求得的,以决定搜索的方向:1-对角线方向;2-向上;3-向左;4-向上或向左
char LCS[MAXSIZE]; int len = 0;
/*函数名:LCS_Len
功能:自底向上进行递推计算C[i][j],并确定B中的搜索方向 若i =0 或 j =0 则C[i][j] = 0;
若i,j > 0且x[i] = y[j] 则C[i][j] = C[i-1][j-1] + 1;
若i,j > 0且x[i]!= y[j] 则C[i][j] = max{C[i-1][j],C[i][j-1]) 输入:两个序列X和Y 输出:二维数组B和C*/ void LCS_Len(char* X, char* Y) {
int m = strlen(X)-1; int n = strlen(Y)-1;
for(int i = 0; i < m; i++ ) C[i][0] = 0; for(int j = 1; 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][j-1]; B[i][j] = 3; C[i][j] = C[i-1][j]; B[i][j] = 2;
else if ( C[i-1][j] < C[i][j-1] )
else /*C[i-1][j] == C[i][j-1]*/
{
C[i][j] = C[i-1][j]; B[i][j] = 4; } }
/*
函数名:Fine_All_LCS
功能:回溯法递归输出所有的LCS 参数说明:
Direction : 记录搜索方向的二维数组，1-对角线方向;2-向上;3-向左;4-向上或向左 X : 一个序列
i,j : 待搜索的下标，初始值为两个序列的长度 len: 记录当前LCS的长度 lcslen: LCS的长度
LCS:记录当前得到的LCS字符*/
void Find_All_LCS(int Direction[MAXSIZE][MAXSIZE], char* X, int i, int j, int curlen, int lcslen) {
if(i>=0 && j>=0) {
if(len == lcslen)//如果当前lcs的长度等于已知的LCS的长度则输出子序列 {
for( int k = len - 1 ; k >= 0 ; k-- ) cout << LCS[k]; cout << \
}
} else {
if(Direction[i][j] == 1) { }
else if(Direction[i][j] == 2) { }
else if(Direction[i][j] == 3) { Find_All_LCS(Direction, X, i, j-1, curlen, lcslen);
Find_All_LCS(Direction, X, i-1, j, curlen, lcslen); LCS[curlen] = X[i];
len++; //子序列长度加1
Find_All_LCS(Direction, X, i-1, j-1, curlen + 1, lcslen);//沿对角线方向搜索 len--; //回溯
}
}
}
else //递归调用Find_All_LCS分别沿两个不同的方向搜索 { }
Find_All_LCS(Direction, X, i, j-1, curlen, lcslen); Find_All_LCS(Direction, X, i-1, j, curlen, lcslen);
}
int main() { }
4、 运行效果 运行效果演示：
char *x, *y;
x = \单元未用,下标从1开始 y = \
int m = (int)strlen(x)-1; int n = (int)strlen(y)-1; int lcslen;
cout << \cout << \
cout << \ LCS_Len(x, y);
lcslen = C[m][n];
Find_All_LCS(B, x, m, n, 0, lcslen); cout << \return 0;