算法设计-最长公共子序列.doc

最长公共子序列（LCS）算法1 算法要求及分析1. 算法要求：利用bi,j，设计一个算法求出全部的LCS；利用”会计方法”，分析所编算法的时间复杂度的最坏情况。 2. 算法分析：该部分思路同课件2 算法详细设计为了求出全部的LCS,需要设计两个功能函数：LCS_L和LCS_Output，函数LCS_L实现计算LCS长度及每个子问题的由来；函数LCS_Output用递归方法实现输出所有LCS。具体设计实现思路：1. 声明全局变量 二维动态数组C和b。数组C记录所要求的LCS的长度；数组b记录Ci,j是通过哪一个子问题的值求得的。定义枚举类型记录不同的遍历方向。2. 用动态规划法实现功能函数LCS_L，得出数组C和b。函数实现思路：首先动态分配和初始化二维数组C和b，然后计算出C和b。根据Xi和Yj的关系，计算得出Ci,j：若Xi=Yj，则执行Ci,jCi-1,j-1+1且bij=ual；若Xi！=Yj，则分为三种情况： 若Ci-1,jCi,j-1则Ci,j取Ci-1,j且bij=up;若Ci-1,jCi,j-1则Ci,j取Ci,j-1且bij=le;若Ci-1,j=Ci,j-1则Ci,j取Ci-1,j且bij=uol;3. 根据C和b编写输出函数LCS_Output输出所有的LCS。函数实现思路：设置变量cur_len记录当前的数组下标，变量len保存当前LCS数组的元素个数。依次扫描二维数组b，从最后一个开始，根据b的值来判断递归方向：当b的值是ual时，LCS数组保存当前字符，len+，沿对角线递归（递归完成要回溯）；len等于LCS的长度时即找到一个LCS序列并输出；当b的值是up时，向上递归；当b的值是le时，向左递归；当b的值是uol时，要找出所有的LCS，故既要向左也要向上递归。4. 主函数给出不同的测试数据输出相应的最长公共子序列长度和所有的最长公共子序列。3 算法流程图开始1. 功能函数LCS_L详细流程图开始动态分配二维数组C和b定义int型变量i,j初始化数组C的第0行和第0列 i m ?N j =0 & j=0?N Ylen当前值等于LCS的长度 ？输出一个LCSY Nbij = ual ? Y记录当前值；利用回溯方法，使i-1,j-1递归功能函数LCS_Output； Nbij = up ? Y使i-1递归调用功能函数LCS_Output；bij = le ? N使j-1递归调用功能函数LCS_Output；Y N使i-1递归函数LCS_Output；使j-1递归函数LCS_Output； 结束4 测试结果通过四组数据（见程序）测试均得到正确结果，截图如下：5 分析和总结1. 结果分析：第一组数据为课件上的例题，结果正确；第二组数据为无最长公共子序列例题，结果正确；第三组数据为较长较多的公共子序列例题，结果正确；第四组数据为一个但多次有重复的最长公共子序列例题，结果正确。2. 时间复杂度分析：显然用于求解出数组C和b的功能函数LCS_L时间复杂度O(mn);由功能函数LCS_Output可知，求出所有的LCS实际上根据搜索不同的方向递归遍历出所有符合要求的序列，故时间复杂度取决于遍历的路径数。遍历的路径数目分为：最好情况下，即m=n并且一直沿着对角线方向搜索，时间复杂度为O(n)；最坏的情况下，即两个序列不存在最长公共子序列，此时数组C所有值为0，数组b所有的值都为uol（向上或者向左搜索）。最坏情况下的时间复杂度即是求出从点S（m，n）到i=0或者j=0(i=0且j=0除外)的所有的路径。Q(0,n) S（m,n）Q(0,1)P(1,0) P(m,0)建立坐标系如上图（此图中由点S向左或者向下遍历），坐标系中的点,轴上的坐标点，轴上的系列坐标点,其中.由于是搜索路径的边界上的点，点不能直接到达点，点也不能直接到达，所以点到和的路径数等价于到点和点的路径数，又因为点到路径数为，设总路径数为，则有故：故最坏的情况下，求出所有的LCS的时间复杂度是。6 源代码#include using namespace std;int len = 0;/回溯时记录当前LCS数组的长度char *lcs;/用于保存一个最长公共子序列int *C;/记录Xi与Yj的LCS的长度int *b;/记录Ci,j是通过哪一个子问题的值求得的enum ual,up,le,uol;/枚举记录方向分别为：左和上、上、左、左或上void LCS_L(char *X,char *Y,int m,int n)/求出各个bij和Cij的值C = new int *m;b = new int *m; for(int k=0;km;k+)Ck = new intn;bk = new intn;int i,j;for (i=0;im;i+) Ci0 = 0;for (j=0;jn;j+) C0j = 0;for (i=1;im;i+)for(j=1;j Cij-1)/向上Cij = Ci-1j;bij = up;else if(Ci-1j =0) & (j=0)if(len = lcs_len)/找出并输出一个LCSfor(int k=len-1;k=0;k-)coutlcsk ;coutendl;elseif(bij = ual)lcscur_len = Xi-1;len+;LCS_Output(b,X,i-1,j-1,cur_len+1,lcs_len);len-;else if(bij = up)LCS_Output(b,X,i-1,j,cur_len,lcs_len);else if(bij = le)LCS_Output(b,X,i,j-1,cur_len,lcs_len);elseLCS_Output(b,X,i-1,j,cur_len,lcs_len);LCS_Output(b,X,i,j-1,cur_len,lcs_len);if(lcs_len = 0) cout无endl;int main()/测试一char X = A,B,C,B,D,A,B;char Y = B,D,C,A,B,A;LCS_L(X,Y,8,7);int lcs_len1 = C76;coutLCS长度：lcs_len1endl;lcs = new charlcs_len1;LCS_Output(b,X,7,6,0,lcs_len1);/测试二char A = A,B,C,D;char B = a,b,c,d;LCS_L(A,B,5,5);int lcs_len2 = C44;coutLCS长度：lcs_len2endl;lcs =new charlcs_len2;LCS_Output(b,A,4,4,0,lcs_len2);/测试三char K = X,Y,Y,X,X,Y,Y,X,Y,X,X,X,Y;char H = X,Y,X,X,X,X,Y,Y,Y,Y,X,X;LCS_L(K,H,14,13);int lcs_len3 = C1312;coutLCS长度：lcs_len3endl;lcs = new charlcs_len3;LCS_Output(b,K,13,12,0,lcs_len3);/测试四char