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

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

2、,j = 2； 若XiYj且Ci-1,j < Ci,j-1，則bi,j中記入“”，記此時(shí)Bi,j = 3； 若XiYj且Ci-1,j = Ci,j-1，則bi,j中記入“”或“”，記此時(shí)Bi,j = 4；得到了兩個(gè)數(shù)組C和B，設(shè)計(jì)遞歸輸出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 算法時(shí)間復(fù)雜度分析 由上述對算法的分析得知，求輔助數(shù)組C和B所消耗的時(shí)間復(fù)雜度為O（mn），而查找所有的公共子序列的時(shí)間復(fù)雜度取決于所遍歷的路

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

5、，點(diǎn)也不能直接到達(dá)，所以點(diǎn)到和的路徑數(shù)等價(jià)于到點(diǎn)和點(diǎn)的路徑數(shù)，又因?yàn)辄c(diǎn)到路徑數(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("請輸入一個(gè)序列");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("請輸入一個(gè)序列");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("