最长公共子序列问题(最)

算法作业:LCS问题作业要求：设计一个算法求出两个序列的所有LCS,分析最坏情况，用“会计方法”证明利用b[i][j]求出所有LCS的算法在最坏情况下时间复杂度为0(6)n+m1、 算法思路：根据最长公共子序列问题的性质，即经过分解后的子问题具有高度重复性，并且具有最优子结构性质，采用动态规划法求解问题。设X={X],x2,...,xn},Y={y],y2,…，y」，首先引入二维数组C[i][j]记录X.和Y.的LCS的长度，定义C[i][j]如下：n m0，i=0或j=0C[i][j]-{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[.]=Y[.],b[.][.]=1,若C[i-l][j]vi][j-l],则b[i][j]=2,若C[i-1][j]>[i][j-1],则b[i][j]=3,若C[i-1][j]=[i][j-1],则b[i][j]=4,根据以上辅助数组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][.]=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]时总是要沿两个方向分另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),其TOC\o"1-5"\h\z1 2 i m y 1 2 j n因为P和Q是搜索路径的边界上的点，点P不能直接到达点P，点Q也不能直接到达Q，所以i j 卄1 i j+1 j点S(m,n)到P,P，…,P，…,P和Q,Q，…,Q，…,Q的路径数等价于S(m,n)到点1 2im 1 2jnP'(1,1),P'(2,1),P'.(i,l),,P.'(mJ)和点Q'(1,1),Q'(1,2),...,Q'(1,j),...,Q'(1,n)的路径数，又因为1 2 i m 1 2 j n点(m,n)到(i,j)路径数为Cn-i ，设总路径数为t，则有m+n-i-jt= t= Cn-im-1+n-ii=1+lLCm-jn-1+m-jj=1根据组合数学的基本知识可得：t= Ct= Cn-i + Cm—jm-1+n-i n-1+m-jj=1+Cn-2 +...+C1+C0n+m-2 n+m-3 m m-1)+Gm-1 +Cm-2 +...+C1+C0)n+m-2 n+m-3 n n-1TOC\o"1-5"\h\z=Cn-1+Cm-1=Cn-1+Cnn+m-1 n+m-1 n+m-1 n+m-1=Cn==Cmn+m n+m［注］:参考卢开澄编著的《组合数学(第3版)》P34-P38最坏情况下算法搜索的所有路径为从S到P,P,...,P,...,P和Q,Q,...,Q,...,Q的所有路径数Cm，因1 2im1 2jn n+m此算法在最坏情况下的时间复杂度为O(Cm).n+m3、算法实现/*文件名：FindLongestCommonSequence.cpp说明：求出两个序列中所有的最长公共子序列日期:2005/10/12*/#includeviostream>#includevstring.h>#defineMAXSIZE100usingnamespacestd;intC[MAXSIZE][MAXSIZE];〃记录序列X和Y的LCS的长度intB[MAXSIZE][MAXSIZE];〃记录二维数组C是通过哪一个子问题的值求得的，以决定搜索的方向:1-对角线方向；2-向上;3-向左;4-向上或向左charLCS[MAXSIZE];intlen=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*/voidLCS_Len(char*X,char*Y){intm=strlen(X)-1;intn=strlen(Y)-1;for(inti=0;i<m;i++)C[i][0]=0;for(intj=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;}elseif(C[i-1][j]>C[i][j-1]){C[i][j]=C[i-1][j];B[i][j]=2;}elseif(C[i-1][j]<C[i][j-1]){C[i][j]=C[i][j-1];B[i][j]=3;}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字符*/voidFind_All_LCS(intDirection[MAXSIZE][MAXSIZE],char*X,inti,intj,intcurlen,intlcslen){if(i>=0&&j>=0){if(len==lcslen)//如果当前lcs的长度等于已知的LCS的长度则输出子序列{for(intk=len-1;k>=0;k--)cout<<LCS[k];cout<<"\n";}else{if(Direction[i][j]==1){LCS[curlen]=X[i];len++; 〃子序列长度加1Find_All_LCS(Direction,X,i-1,j-1,curlen+1,lcslen);//沿对角线方向搜索len--;〃回溯}elseif(Direction[i][j]==2){Find_All_LCS(Direction,X,i-1,j,curlen,lcslen);}elseif(Direction[i][j]==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);}}intmain(){char*x,*y;x="ABCBDAB";//O单元未用,下标从1开始y="BDCABA";intm=(int)strlen(x)-1;intn=(int)strlen(