動態(tài)規(guī)劃法求解最長公共子序列(共8頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 公共子序列問題 徐康一算法設(shè)計 假設(shè)有兩個序列X和Y，假設(shè)X和Y分別有m和n個元素，則建立一個二維數(shù)組C(m+1)*(n+1)，記錄Xi與Yj的LCS的長度。將Ci,j分為三種情況： 若i =0 或j =0時，Ci,j=0； 若i,j>0且Xi=Yj，Ci,j=Ci-1,j-1+1； 若i,j>0且XiYj,Ci,j=maxCi-1,j,Ci,j-1。 再使用一個m*n的二維數(shù)組b，bi,j記錄Ci,j的來向: 若Xi=Yj，則Bi,j中記入“”，記此時bi,j = 1； 若XiYj且Ci-1,j > Ci,j-1，則bi,j中記入“”，記此時Bi

2、,j = 2； 若XiYj且Ci-1,j < Ci,j-1，則bi,j中記入“”，記此時Bi,j = 3； 若XiYj且Ci-1,j = Ci,j-1，則bi,j中記入“”或“”，記此時Bi,j = 4；得到了兩個數(shù)組C和B，設(shè)計遞歸輸出LCS(X,Y)的算法： LCS_Output(Direction, X, i, j, len,LCS) If i=0 or j=0 將LCS保存至集合LCS_SET中 then return; If bi,j=1 then /*Xi=Yj*/ LCS_Output(b,X,i-1,j-1)； 將Xi保存至LCSlen-i； else if bi,j=2

3、 then /*Xi¹Yj且Ci-1,j>Ci,j-1*/ LCS_Output(b,X,i-1,j) else if bi,j=3 then /*Xi¹Yj且Ci-1,j<Ci,j-1*/ LCS_Output(b,X,i,j-1) else if bi,j=4 then /*Xi¹Yj且Ci-1,j=Ci,j-1*/ LCS_Output(b,X,i-1,j) LCS_Output(b,X,i,j-1) 2 算法時間復(fù)雜度分析 由上述對算法的分析得知，求輔助數(shù)組C和B所消耗的時間復(fù)雜度為O（mn），而查找所有的公共子序列的時間復(fù)雜度取決于所遍歷的路

4、徑，而路徑是由算法遞歸的方向決定的。顯然，最好的情況是m=n并且B中的所有值都為1（按斜對角線方向搜索），此時時間復(fù)雜度為O（n）。當X和Y序列不存在公共子序列時為算法的最壞情況，因為此時C數(shù)組的所有元素都為0，B在每一個節(jié)點都要沿著兩個不同的方向搜索，即每次都要調(diào)用兩次LCS_Output,當調(diào)用到i=0或j=0時返回，直到搜索完整個m*n數(shù)組才結(jié)束。該時間復(fù)雜度就是計算從點（m,n）到i=0或j=0的所有路徑。建立如上圖的直角坐標系，設(shè)點S（m，n）,軸上的坐標點P1(1,0) 到Pm(m,0)，軸上的系列坐標點Q1(0,1) 到Qn(0,n)。因為是搜索路徑的邊界上的點，點不能直接到達點

5、，點也不能直接到達，所以點到和的路徑數(shù)等價于到點和點的路徑數(shù)，又因為點到路徑數(shù)為，設(shè)總路徑數(shù)為，則有3 程序流程圖如下所示4 程序源碼package Homework2;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.HashSet;import java.util.Set;public class LCS int C;int B;Set LCS_SET = new HashSet(); /使用集合去重public int LCS

6、Length(char X, char Y) /返回公共子序列長度int m = X.length;int n = Y.length;C = new intX.lengthY.length;B = new intX.lengthY.length;for (int i = 0; i < m; i+) Ci0 = 0;Bi0 = 0;for (int j = 0; j < n; j+) C0j = 0;B0j = 0;for (int i = 1; i < m; i+) for (int j = 1; j < n; j+) if (Xi = Yj) Cij = Ci - 1

7、j - 1 + 1;Bij = 1; else if (Ci - 1j > Cij - 1) Cij = Ci - 1j;Bij = 2; else if (Ci - 1j < Cij - 1) Cij = Cij - 1;Bij = 3; else Cij = Ci - 1j;Bij = 4;return Cm - 1n - 1;public void LCS_Output(int Direction, char X, int i, int j, int len,char LCS) int lcslen = len;if (i = 0 | j = 0) LCS_SET.add(S

8、tring.valueOf(LCS);return;if (Bij = 1) LCSlen - 1 = Xi;len-;LCS_Output(B, X, i - 1, j - 1, len, LCS); else if (Bij = 2) LCS_Output(B, X, i - 1, j, len, LCS); else if (Bij = 3) LCS_Output(B, X, i, j - 1, len, LCS); else if (Bij = 4) LCS_Output(B, X, i - 1, j, len, LCS);LCS_Output(B, X, i, j - 1, len,

9、 LCS);/* * param args */public static void main(String args) throws IOException / TODO Auto-generated method stubchar X, Y;BufferedReader buf = null;buf = new BufferedReader(new InputStreamReader(System.in);System.out.println("請輸入一個序列");X = buf.readLine().toCharArray();char X_temp = new ch

10、arX.length + 1;for (int i = 0; i < X.length; i+) X_temp0 = ' 'X_tempi + 1 = Xi;System.out.println("請輸入一個序列");Y = buf.readLine().toCharArray();char Y_temp = new charY.length + 1;for (int i = 0; i < Y.length; i+) Y_temp0 = ' 'Y_tempi + 1 = Yi;System.out.print("X=&q

11、uot;);for (char x : X) System.out.print(x);System.out.println();System.out.print("Y=");for (char y : Y) System.out.print(y);System.out.println();LCS lcs = new LCS();int len = lcs.LCSLength(X_temp, Y_temp);char LCS = new charlen;int m = X.length;int n = Y.length;System.out.println("最長公共子序列長度為:" + len); / 輸出最長子序列長度System.out.print("