《最长公共子序列问题(最)》由会员分享，可在线阅读，更多相关《最长公共子序列问题(最)（5页珍藏版）》请在金锄头文库上搜索。
1、算法作业:LCS 问 题作业要求：设计一个算法求出两个序列的所有LCS,分析最坏情况，用“会计方法”证明利用bij求出所有LCS的算法在最坏情况下时间复杂度为0(6 )n+m1、算法思路： 根据最长公共子序列问题的性质，即经过分解后的子问题具有高度重复性，并且具有最优子结构 性质，采用动态规划法求解问题。设X=X, x2, . , xn, Y=y, y2,，y，首先引入二维数组Cij 记录X.和Y.的LCS的长度，定义Cij如下： nm0， i = 0 或 j = 0C i j - Ci -1 j-1 +1 ,i,j 0且x i = y jmax C i-1 j, C i j-1, i, j
2、0且 xi 丰 y j为了构造出LCS，还需要使用一个二维数组bmn，bij记录Cij是通过哪个子问题的值求得 的，以决定搜索的方向，欲求出所有的LCS，定义数组b如下：设 1-对角线方向;2-向上;3-向左;4-向上或向左若 X.=Y.,b. = 1,若 Ci-ljvij-l,则 bij = 2, 若 Ci-1jij-1,则 bij = 3, 若 Ci-1j=ij-1,则 bij = 4, 根据以上辅助数组C和b的定义，算法首先需要求出这两个数组，Cmn中记录的最长公共子序列 的长度，b中记录了查找子序列元素的搜索方向。利用C和b的信息，Find_All_LCS可以采用回溯法求出所有的LCS
3、。基本思路如下：使用一个辅 助数组记录每次调用Find_All_LCS得到的LCS中的元素，每次递归调用一次Find_All_LCS，进入一 个新的执行层，首先要判断当前处理的两个子序列长度是否大于等于0 ，若不满足，则该层的递归结 束，返回上一层；然后再判断当前得到的子序列是否等于数组C中求出的最长公共子序列长度，若等 于，则说明算法执行到此已经得到一个LCS，按序输出；若不等于，此时根据数组b中记录的搜索方 向继续搜索，特别要说明的是，当 bi.=4 时，即要向上或向左，需要对这两个方向分别调用 Find_All_LCS，保证沿着这两个方向上LCS元素不被漏掉，都可以搜索到；若bij=1，
4、即沿对角线 方向搜索前进时，此时元素Xi为LCS中的元素，存放至辅助数组中去，同时将当前已经求得的LCS 长度增1,当递归调用Find_All_LCS从bij=1处时，需要回溯一步，搜索其它路径上可能为LCS中 的元素。当所有的可能路径都已经搜索完，算法结束。对于某些情况会输出重复的LCS，这是因为算法在沿不同路径搜索时可能会出现相同的LCS序列。2、时间复杂度分析由上述对Find_All_LCS算法的分析可知，求出所有的LCS实际上是根据搜索的方向信息遍历所 有的路径找出满足条件的元素集合。因此，除求解辅助数组C和b所用的O(mn+m+n)的执行时间外， Find_All_LCS的时间复杂度
5、取决于所遍历路径数。而路径数是由搜索方向决定的。显然算法在最好的 情况下，即m=n并且b中所有的值都指示沿着对角线方向搜索，时间复杂度为O(n).相反，当X和Y 序列不存在公共子序列时为算法的最坏情况，此时C中所有值都等于0,数组b中所有的值都指示要 分别沿两个不同的方向(向左或向上)搜索，这种情况下每处理一次Xi,Yj时总是要沿两个方向分 另IJ调用Find_All_LCS,遇到i=0或j=0时返回，直到搜索完所有的可能路径才结束，最坏情况下的搜 索矩阵如下图所示：由此可知，要确定最坏情况的时间复杂度，就是要计算出从点(m,n)到i=0或j=0 (除(i, j)= (0, 0)外)的所有路径
6、。求解转化为组合数学中的路径数问题。建立一个直角坐标系如上图中所示，对于坐标系 中 的 点 可 以 沿 向 上 或 向 左 两 个 方 向 前 进 ， 设 点 S(m,n) , x 轴 上 的 坐 标 点P (1,0), P (2,0),P(i,0 ), P (m,0)，y 轴上的系列坐标点 Q (0,1), Q (0,2),Q (0, j),Q (0,n),其12imy12jn因为P和Q是搜索路径的边界上的点，点P不能直接到达点P，点Q 也不能直接到达Q，所以 ij卄1ij+1j点S(m,n)到P, P，,P，,P和Q , Q，,Q，,Q 的路径数等价于S(m,n)到点 12 i m12 j
7、 nP(1,1),P (2,1) , P.(i,l), , P.(mJ)和点 Q (1,1),Q (1,2),.,Q (1, j),.,Q (1,n)的路径数，又因为 12im12jn点(m, n)到(i, j)路径数为Cn-i，设总路径数为t，则有m+n-i - jt =C n-im -1 + n -ii=1+ lLCm- jn-1+ m- jj=1根据组合数学的基本知识可得：t =C n-i+C mjm-1+ n -in -1+ m - jj=1+ Cn-2+.+ C1 + C0n+m-2n+m-3mm-1)+Gm-1+ Cm-2+ . + C1 + C 0 )n + m - 2n + m
8、 - 3nn -1= C n-1 + C m-1 = C n-1 + C n n+m-1n+m-1n+m-1n+m-1= C n = C mn+mn+m注:参考卢开澄编著的组合数学(第3版)P34-P38最坏情况下算法搜索的所有路径为从S到P,P ,.,P,.,P和Q ,Q ,.,Q ,.,Q的所有路径数Cm，因 12 i m 12 j nn + m此算法在最坏情况下的时间复杂度为O(Cm ).n + m3、算法实现/*文件名：FindLongestCommonSequence.cpp 说明：求出两个序列中所有的最长公共子序列 日期:2005/10/12*/#include viostream
9、#include vstring.h#define MAXSIZE 100using namespace std;int CMAXSIZEMAXSIZE; 记录序列 X 和 Y 的 LCS 的长度int BMAXSIZEMAXSIZE;记录二维数组C是通过哪一个子问题的值求得的，以决定搜索的方向:1-对角线方向；2-向上;3-向左;4-向上或向左char LCSMAXSIZE;int len = 0;/* 函数名:LCS_Len功能:自底向上进行递推计算Cij,并确定B中的搜索方向若 i =0 或 j =0 则 Cij = 0;若 i,j 0 且 xi = yj则 Cij = Ci-1j-1
10、+ 1;若 i,j 0 且 xi!= yj则 Cij = maxCi-1j,Cij-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+ ) Ci0 = 0; for(int j = 1; j n; j+ ) C0j = 0; for(i = 1;i = m; i+ )for(j = 1; j Cij-1) Cij = Ci-1j;Bij = 2;else if ( Ci-1j =0 & j=0)if(len = l
11、cslen)/如果当前lcs的长度等于已知的LCS的长度则输出子序列for( int k = len - 1 ; k = 0 ; k-)cout LCSk;cout n;elseif(Directionij = 1)LCScurlen = Xi;len+;子序列长度加1Find_All_LCS(Direction, X, i-1, j-1, curlen + 1, lcslen);/沿 对角线方向搜索 len-; 回溯else if(Directionij = 2)Find_All_LCS(Direction, X, i-1, j, curlen, lcslen);else if(Direct
12、ionij = 3)Find_All_LCS(Direction, X, i, j-1, curlen, lcslen);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()char *x, *y;x = ABCBDAB;/O单元未用,下标从1开始y = BDCABA;int m = (int)strlen(x)-1;int n = (int)strlen(y)-1;int lcslen;cout x = x endl;cout y = y endl;cout The longest common sequence as following: endl;LCS_Len(x, y); lcslen = Cmn;Find_All_LCS(B, x, m, n, 0, lcslen);cout OK!; return 0;
