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

《算法设计-最长公共子序列.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、最长公共子序列（LCS）算法一．算法要求及分析1.算法要求：利用b[i,j]，设计一个算法求出全部的LCS；利用”会计方法”，分析所编算法的时间复杂度的最坏情况。2.算法分析：该部分思路同课件二．算法详细设计为了求出全部的LCS,需要设计两个功能函数：LCS_L和LCS_Output，函数LCS_L实现计算LCS长度及每个子问题的由来；函数LCS_Output用递归方法实现输出所有LCS。具体设计实现思路：1.声明全局变量二维动态数组C和b。数组C记录所要求的LCS的长度；数组b记录C[i,j]是通过哪一个子问题的值求得的。定义枚举类型记录不同

2、的遍历方向。2.用动态规划法实现功能函数LCS_L，得出数组C和b。函数实现思路：首先动态分配和初始化二维数组C和b，然后计算出C和b。根据X[i]和Y[j]的关系，计算得出C[i,j]：若X[i]=Y[j]，则执行C[i,j]←C[i-1,j-1]+1且b[i][j]=ual；若X[i]！=Y[j]，则分为三种情况：若C[i-1,j]>C[i,j-1]则C[i,j]取C[i-1,j]且b[i][j]=up;若C[i-1,j]

3、j]取C[i-1,j]且b[i][j]=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.主函数给出不同的

4、测试数据输出相应的最长公共子序列长度和所有的最长公共子序列。一．算法流程图开始1.功能函数LCS_L详细流程图开始动态分配二维数组C和b定义int型变量i,j初始化数组C的第0行和第0列i

5、束1.功能函数LCS_Output详细流程图开始i>=0&&j>=0?NYlen当前值等于LCS的长度？输出一个LCSYNb[i][j]==ual?Y记录当前值；利用回溯方法，使i-1,j-1递归功能函数LCS_Output；Nb[i][j]==up?Y使i-1递归调用功能函数LCS_Output；b[i][j]==le?N使j-1递归调用功能函数LCS_Output；YN使i-1递归函数LCS_Output；使j-1递归函数LCS_Output；结束一．测试结果通过四组数据（见程序）测试均得到正确结果，截图如下：一．分析和总结1.结果分析：第

6、一组数据为课件上的例题，结果正确；第二组数据为无最长公共子序列例题，结果正确；第三组数据为较长较多的公共子序列例题，结果正确；第四组数据为一个但多次有重复的最长公共子序列例题，结果正确。2.时间复杂度分析：显然用于求解出数组C和b的功能函数LCS_L时间复杂度O(m×n);由功能函数LCS_Output可知，求出所有的LCS实际上根据搜索不同的方向递归遍历出所有符合要求的序列，故时间复杂度取决于遍历的路径数。遍历的路径数目分为：最好情况下，即m=n并且一直沿着对角线方向搜索，时间复杂度为O(n)；最坏的情况下，即两个序列不存在最长公共子序列，此

7、时数组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的时间复杂度是。一．源代码#include

8、usingnamespacestd;intlen=0;//回溯时记录当前LCS数组的长度char*lcs;//用于保存一个最长公共