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

1、算法作業(yè):LCS冋題作業(yè)要求：設計一個算法求出兩個序列的所有LCS，分析最壞情況，用“會計方法”證明利用bij求出所有l(wèi)cs的算法在最壞情況下時間復雜度為o(cmm)1、算法思路:根據最長公共子序列問題的性質，即經過分解后的子問題具有高度重復性，并且具有最優(yōu)子結構性質，采用動態(tài)規(guī)劃法求解問題。設 記錄Xi和Yj的LCS的長度，定義X=X1, X2,，Xn, Y=y 1, y2,，y m,首先引入二維數組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為了構造

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

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

4、經求得的LCS長度增1，當遞歸調用Find_All_LCS從bij=1處時，需要回溯一步，搜索其它路徑上可能為LCS中的元素。當所有的可能路徑都已經搜索完，算法結束。對于某些情況會輸出重復的LCS ,這是因為算法在沿不同路徑搜索時可能會出現相同的LCS序列。2、時間復雜度分析由上述對Find_All_LCS算法的分析可知，求出所有的LCS實際上是根據搜索的方向信息遍歷所有的路徑找出滿足條件的元素集合。因此，除求解輔助數組C和b所用的O(mn+m+n)的執(zhí)行時間外，Fin d_All_LCS的時間復雜度取決于所遍歷路徑數。而路徑數是由搜索方向決定的。顯然算法在最好的 情況下，即m=n并且b中所有

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

6、軸上的系列坐標點 QglgPN),Qj(O, j),Qn(O,n),其 中 1n ,1 乞 j 乞 m .因為P和Qj是搜索路徑的邊界上的點，點P*不能直接到達點P ,點Qj*也不能直接到達 Qj，所以點S(m, n)至U只，卩2,.轉，.局 和Q1,Q2,.,Qj,.,Qn的 路徑數 等價于S(m, n)到點P(1,1),P2(2,1) , R.(i.l), , Pm.(m1)和點 Qi(1,1),Q2(1,2),.,Qj(1, j),.,Qn(1,n)的路徑數，又因為點(m, n)到(i, j)路徑數為cm，設總路徑數為mm -jCn _1 m -j根據組合數學的基本知識可得: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最壞情況下算法搜索的所有路徑為從注:參考盧開澄編著的組合數學(第 3版)P34-P38S 到 R,P2,.,R,.,Pm 和 Q1,Q2,.,Qj,.,Qn 的所有路徑數 C 驚，因此算法在最壞情況下的時間復雜度為。(璃).3、算法實現/* 文件名： FindLon gestCom mon Seque nce.cpp 說明：求出兩個序列中所有的最長公共子序列 日期:2005/10/12*/

8、#in elude #in elude #define MAXSIZE 1OOusing n amespace std;int CMAXSIZEMAXSIZE ; /記錄序列 X 和 Y 的 LCS 的長度,以決定搜索的方向:1-int BMAXSIZEMAXSIZE;/記錄二維數組C是通過哪一個子問題的值求得的對角線方向；2-向上；3-向左;4-向上或向左char LCSMAXSIZE;int len = 0;/* 函數名：LCS_Len功能：自底向上進行遞推計算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) 輸入:兩個序列X和Y 輸出：二維數組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)如果當前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 遞歸調用Find_AII_LCS分別沿兩個不同的方向搜索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 單元未用,下標從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;