最長公共子序列問題(最)

1、算法作業(yè):LCS冋題作業(yè)要求：設(shè)計(jì)一個(gè)算法求出兩個(gè)序列的所有LCS，分析最壞情況，用“會(huì)計(jì)方法”證明利用bij求出所有l(wèi)cs的算法在最壞情況下時(shí)間復(fù)雜度為o(cmm)1、算法思路:根據(jù)最長公共子序列問題的性質(zhì)，即經(jīng)過分解后的子問題具有高度重復(fù)性，并且具有最優(yōu)子結(jié)構(gòu)性質(zhì)，采用動(dòng)態(tài)規(guī)劃法求解問題。設(shè) 記錄Xi和Yj的LCS的長度，定義X=X1, X2,，Xn, Y=y 1, y2,，y m,首先引入二維數(shù)組Cij如下：CijCi j二0, i =0或 j =0C i _1 j _11 ,i,j 0 且x j = y jmax Ci -1 j, Ci j -1, i, j 0且 x- y j為了構(gòu)造

2、出LCS，還需要使用一個(gè)二維數(shù)組bmn , bij記錄Cij是通過哪個(gè)子問題的值求得的，以決定搜索的方向，欲求出所有的LCS，定義數(shù)組b如下：設(shè)1-對角線方向；2-向上;3-向左;4-向上或向左若 Xi=Yj,bij = 1,若 Ci-1jij-1,貝V bij = 3, 若 Ci-1j=ij-1, 則 bij = 4,根據(jù)以上輔助數(shù)組C和b的定義，算法首先需要求出這兩個(gè)數(shù)組,Cmn中記錄的最長公共子序列的長度，b中記錄了查找子序列元素的搜索方向。利用C和b的信息，F(xiàn)ind_AII_LCS可以采用回溯法求出所有的LCS?；舅悸啡缦拢菏褂靡粋€(gè)輔助數(shù)組記錄每次調(diào)用Find_All_LCS得到的L

3、CS中的元素，每次遞歸調(diào)用一次Find_All_LCS，進(jìn)入一個(gè)新的執(zhí)行層，首先要判斷當(dāng)前處理的兩個(gè)子序列長度是否大于等于0，若不滿足，則該層的遞歸結(jié)束，返回上一層；然后再判斷當(dāng)前得到的子序列是否等于數(shù)組C中求出的最長公共子序列長度，若等于，則說明算法執(zhí)行到此已經(jīng)得到一個(gè)LCS，按序輸出；若不等于，此時(shí)根據(jù)數(shù)組 b中記錄的搜索方向繼續(xù)搜索，特別要說明的是，當(dāng)bij=4 時(shí)，即要向上或向左，需要對這兩個(gè)方向分別調(diào)用Find_All_LCS，保證沿著這兩個(gè)方向上LCS元素不被漏掉，都可以搜索到；若 bij=1，即沿對角線方向搜索前進(jìn)時(shí)，此時(shí)元素Xi為LCS中的元素，存放至輔助數(shù)組中去，同時(shí)將當(dāng)前已

4、經(jīng)求得的LCS長度增1，當(dāng)遞歸調(diào)用Find_All_LCS從bij=1處時(shí)，需要回溯一步，搜索其它路徑上可能為LCS中的元素。當(dāng)所有的可能路徑都已經(jīng)搜索完，算法結(jié)束。對于某些情況會(huì)輸出重復(fù)的LCS ,這是因?yàn)樗惴ㄔ谘夭煌窂剿阉鲿r(shí)可能會(huì)出現(xiàn)相同的LCS序列。2、時(shí)間復(fù)雜度分析由上述對Find_All_LCS算法的分析可知，求出所有的LCS實(shí)際上是根據(jù)搜索的方向信息遍歷所有的路徑找出滿足條件的元素集合。因此，除求解輔助數(shù)組C和b所用的O(mn+m+n)的執(zhí)行時(shí)間外，F(xiàn)in d_All_LCS的時(shí)間復(fù)雜度取決于所遍歷路徑數(shù)。而路徑數(shù)是由搜索方向決定的。顯然算法在最好的 情況下，即m=n并且b中所有

5、的值都指示沿著對角線方向搜索，時(shí)間復(fù)雜度為O(n).相反，當(dāng)X和Y序列不存在公共子序列時(shí)為算法的最壞情況，此時(shí)C中所有值都等于 0,數(shù)組b中所有的值都指示要分別沿兩個(gè)不同的方向(向左或向上)搜索，這種情況下每處理一次Xi,Yj時(shí)總是要沿兩個(gè)方向分另鵬用Find_All_LCS，遇到i=0或j=0時(shí)返回，直到搜索完所有的可能路徑才結(jié)束，最壞情況下的搜 索矩陣如下圖所示：外)的所有路徑。求解轉(zhuǎn)化為組合數(shù)學(xué)中的路徑數(shù)問題。建立一個(gè)直角坐標(biāo)系如上圖中所示，對于坐標(biāo)系中的點(diǎn)可以沿向上或向左兩個(gè)方向前進(jìn)，設(shè)點(diǎn)S(m, n) , x軸上的坐標(biāo)點(diǎn)R(1,O),F2(2,O),R(i,O),Pm(m,O)，y

6、軸上的系列坐標(biāo)點(diǎn) QglgPN),Qj(O, j),Qn(O,n),其 中 1n ,1 乞 j 乞 m .因?yàn)镻和Qj是搜索路徑的邊界上的點(diǎn)，點(diǎn)P*不能直接到達(dá)點(diǎn)P ,點(diǎn)Qj*也不能直接到達(dá) Qj，所以點(diǎn)S(m, n)至U只，卩2,.轉(zhuǎn)，.局 和Q1,Q2,.,Qj,.,Qn的 路徑數(shù) 等價(jià)于S(m, n)到點(diǎn)P(1,1),P2(2,1) , R.(i.l), , Pm.(m1)和點(diǎn) Qi(1,1),Q2(1,2),.,Qj(1, j),.,Qn(1,n)的路徑數(shù)，又因?yàn)辄c(diǎn)(m, n)到(i, j)路徑數(shù)為cm，設(shè)總路徑數(shù)為mm -jCn _1 m -j根據(jù)組合數(shù)學(xué)的基本知識(shí)可得:nt八cm

7、J n _iCnmJi Aj A=遼 +0?益二 +. +cm +C；L 尸+。驚_3 +. + C： +0)-Cn-Cm4 _Cn -Cnn mn m 4n :m Jn mnm=Cn m = = C n m最壞情況下算法搜索的所有路徑為從注:參考盧開澄編著的組合數(shù)學(xué)(第 3版)P34-P38S 到 R,P2,.,R,.,Pm 和 Q1,Q2,.,Qj,.,Qn 的所有路徑數(shù) C 驚，因此算法在最壞情況下的時(shí)間復(fù)雜度為。(璃).3、算法實(shí)現(xiàn)/* 文件名： FindLon gestCom mon Seque nce.cpp 說明：求出兩個(gè)序列中所有的最長公共子序列 日期:2005/10/12*/

8、#in elude #in elude #define MAXSIZE 1OOusing n amespace std;int CMAXSIZEMAXSIZE ; /記錄序列 X 和 Y 的 LCS 的長度,以決定搜索的方向:1-int BMAXSIZEMAXSIZE;/記錄二維數(shù)組C是通過哪一個(gè)子問題的值求得的對角線方向；2-向上；3-向左;4-向上或向左char LCSMAXSIZE;int len = 0;/* 函數(shù)名：LCS_Len功能：自底向上進(jìn)行遞推計(jì)算Cij,并確定B中的搜索方向若 i =0 或 j =0 則 Cij = 0;若 i,j 0 且 xi = yj貝V Cij = C

9、i-1j-1 + 1;若 i,j 0 且 xi!= yj貝V Cij = maxCi-1j,Cij-1) 輸入:兩個(gè)序列X和Y 輸出：二維數(shù)組B和C*/void LCS_Le n(char* X, char* Y)int m = strlen(X)-1;int n = strle n(Y)-1;for(i nt i = 0; i m; i+ ) Ci0 = 0; for(i nt 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

10、=0)if(len = Icslen)如果當(dāng)前l(fā)es的長度等于已知的LCS的長度則輸出子序列for( int k = len - 1 ; k = 0 ; k-)cout LCSk;cout n;elseif(Directio nij = 1)LCScurIe n = Xi;len+;子序列長度加1Fin d_AII_LCS(Directio n, X, i-1, j-1, curlen + 1, Icsle n);沿對角線方向搜索len-;回溯else if(Directio nij = 2)Find_AII_LCS(Direction, X, i-1, j, curlen, Icslen);

11、else if(Directio nij = 3)Find_AII_LCS(Direction, X, i, j-1, curlen, Icslen);else 遞歸調(diào)用Find_AII_LCS分別沿兩個(gè)不同的方向搜索Find_AII_LCS(Direction, X, i, j-1, curlen, Icslen);Find_AII_LCS(Direction, X, i-1, j, curlen, Icslen);int mai n()char *x, *y;x = ABCBDAB;/O 單元未用,下標(biāo)從1開始y = BDCABA;int m = (int)strlen(x)-1;int n = (in t)strle n(-y)-1;int lcsle n;cout x = x en dl;cout y = y en dl;cout The Ion gest com mon seque nee as follow in g: en dl;LCS_Le n(x, y);lcsle n = Cm n;