资源预览内容
第1页 / 共5页
第2页 / 共5页
第3页 / 共5页
第4页 / 共5页
第5页 / 共5页
亲,该文档总共5页全部预览完了,如果喜欢就下载吧!
资源描述
算法作业: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 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。基本思路如下:使用一个辅 助数组记录每次调用Find_All_LCS得到的LCS中的元素,每次递归调用一次Find_All_LCS,进入一 个新的执行层,首先要判断当前处理的两个子序列长度是否大于等于0 ,若不满足,则该层的递归结 束,返回上一层;然后再判断当前得到的子序列是否等于数组C中求出的最长公共子序列长度,若等 于,则说明算法执行到此已经得到一个LCS,按序输出;若不等于,此时根据数组b中记录的搜索方 向继续搜索,特别要说明的是,当 bi.=4 时,即要向上或向左,需要对这两个方向分别调用 Find_All_LCS,保证沿着这两个方向上LCS元素不被漏掉,都可以搜索到;若bij=1,即沿对角线 方向搜索前进时,此时元素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的时间复杂度取决于所遍历路径数。而路径数是由搜索方向决定的。显然算法在最好的 情况下,即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)外)的所有路径。求解转化为组合数学中的路径数问题。建立一个直角坐标系如上图中所示,对于坐标系 中 的 点 可 以 沿 向 上 或 向 左 两 个 方 向 前 进 , 设 点 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 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 - 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#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 + 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 = lcslen)/如果当前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(Directionij = 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;
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号