摘要:最長公共子序列問題指的是求解兩個序列和的長度最長的公共子序列。當然,可以看出,問題容易出現(xiàn)重疊子問題,這時候,就需要用動態(tài)規(guī)劃法來解決。
問題介紹
??給定一個序列$X=
??給定兩個序列$X$和$Y$,如果$Z$同時是$X$和$Y$的子序列,則稱$Z$是$X$和$Y$的公共子序列。最長公共子序列(LCS)問題指的是:求解兩個序列$X$和$Y$的長度最長的公共子序列。例如,序列$X={A,B,C,B,D,A,B}$和$Y={B,D,C,A,B,A}$的最長公共子序列為${B,C,B,A}$,長度為4。
??本文將具體闡釋如何用動態(tài)規(guī)劃法(Dynamic Programming)來求解最長公共子序列(LCS)問題。
??給定一個序列$X=
??(LCS的子結構)令$X=
如果$x_m=y_n,$則$z_k=x_m=y_n$且$Z_{k-1}$是$X_{m-1}$和$Y_{n-1}$的一個LCS。
如果$x_m eq y_n,$則$z_k eq x_m$意味著$Z_{k-1}$是$X_{m-1}$和$Y$的一個LCS。
如果$x_m eq y_n,$則$z_k eq y_n$且$Z_{k-1}$是$X$和$Y_{n-1}$的一個LCS。
2. 構造遞歸解??在求$X=
??定義$c[i,j]$表示$X_i$和$Y_j$的LCS的長度。如果$i=0$或$j=0$,則$c[i,j]=0.$利用LCS的子結構,可以得到如下公式:
$$ c[i,j]=left{ egin{array}{lr} 0,qquad 若i=0或j=0 c[i-1, j-1]+1,qquad 若i,j>0且x_i=y_j max(c[i, j-1], c[i-1, j]),qquad 若i,j>0且x_i eq y_j end{array} ight. $$
3. 計算LCS的長度??計算LCS長度的偽代碼為LCS-LENGTH. 過程LCS-LENGTH接受兩個子序列$X=
LCS-LENGTH(X, Y): m = X.length n = Y.length let b[1...m, 1...n] and c[0...m, 0...n] be new table for i = 1 to m c[i, 0] = 0 for j = 1 to n c[0, j] = 0 for i = 1 to m for j = 1 to n if x[i] == y[j] c[i,j] = c[i-1, j-1]+1 b[i,j] = "diag" elseif c[i-1, j] >= c[i, j-1] c[i,j] = c[i-1, j] b[i,j] = "up" else c[i,j] = c[i, j-1] b[i,j] = "left" return c and b4. 尋找LCS
??為了尋找$X$和$Y$的一個LCS, 我們需要用到LCS-LENGTH過程中的表$b$,只需要簡單地從$b[m, n]$開始,并按箭頭方向追蹤下去即可。當在表項$b[i,j]$中遇到一個"diag"時,意味著$x_i=y_j$是LCS的一個元素。按照這種方法,我們可以按逆序依次構造出LCS的所有元素。偽代碼PRINT-LCS如下:
PRINT-LCS(b, X, i, j): if i == 0 or j == 0 return if b[i,j] == "diag" PRINT-LCS(b, X, i-1, j-1) print x[i] elseif b[i,j] == "up": PRINT-LCS(b, X, i-1, j) else PRINT-LCS(b, X, i, j-1)程序實現(xiàn)
??有了以上對LCS問題的算法分析,我們不難寫出具體的程序來實現(xiàn)它。下面將會給出Python代碼和Java代碼,供讀者參考。
??完整的Python代碼如下:
import numpy as np # using dynamic programming to solve LCS problem # parameters: X,Y -> list def LCS_LENGTH(X, Y): m = len(X) # length of X n = len(Y) # length of Y # create two tables, b for directions, c for solution of sub-problem b = np.array([[None]*(n+1)]*(m+1)) c = np.array([[0]*(n+1)]*(m+1)) # use DP to sole LCS problem for i in range(1, m+1): for j in range(1, n+1): if X[i-1] == Y[j-1]: c[i,j] = c[i-1,j-1]+1 b[i,j] = "diag" elif c[i-1,j] >= c[i, j-1]: c[i,j] = c[i-1,j] b[i,j] = "up" else: c[i,j] = c[i,j-1] b[i,j] = "left" #print(b) #print(c) return b,c # print longest common subsequence of X and Y def print_LCS(b, X, i, j): if i == 0 or j == 0: return None if b[i,j] == "diag": print_LCS(b, X, i-1, j-1) print(X[i-1], end=" ") elif b[i,j] == "up": print_LCS(b, X, i-1, j) else: print_LCS(b, X, i, j-1) X = "conservatives" Y = "breather" b,c = LCS_LENGTH(X,Y) print_LCS(b, X, len(X), len(Y))
輸出結果如下:
e a t e
??完整的Java代碼如下:
package DP_example; import java.util.Arrays; import java.util.List; public class LCS { // 主函數(shù) public static void main(String[] args) { // 兩個序列X和Y ListX = Arrays.asList("A","B","C","B","D","A","B"); List Y = Arrays.asList("B","D","C","A","B","A"); int m = X.size(); //X的長度 int n = Y.size(); // Y的長度 String[][] b = LCS_length(X, Y); //獲取維護表b的值 print_LCS(b, X, m, n); // 輸出LCS } /* 函數(shù)LCS_length:獲取維護表b的值 傳入?yún)?shù): 兩個序列X和Y 返回值: 維護表b */ public static String[][] LCS_length(List X, List Y){ int m = X.size(); //X的長度 int n = Y.size(); // Y的長度 int[][] c = new int[m+1][n+1]; String[][] b = new String[m+1][n+1]; // 對表b和表c進行初始化 for(int i=1; i = c[i][j-1]){ c[i][j] = c[i-1][j]; b[i][j] = "up"; } else{ c[i][j] = c[i][j-1]; b[i][j] = "left"; } } } return b; } // 輸出最長公共子序列 public static int print_LCS(String[][] b, List X, int i, int j){ if(i == 0 || j == 0) return 0; if(b[i][j].equals("diag")){ print_LCS(b, X, i-1, j-1); System.out.print(X.get(i-1)+" "); } else if(b[i][j].equals("up")) print_LCS(b, X, i-1, j); else print_LCS(b, X, i, j-1); return 1; } }
輸出結果如下:
B C B A參考文獻
算法導論(第三版) 機械工業(yè)出版社
https://www.geeksforgeeks.org...
注意:本人現(xiàn)已開通兩個微信公眾號: 因為Python(微信號為:python_math)以及輕松學會Python爬蟲(微信號為:easy_web_scrape), 歡迎大家關注哦~~
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/41852.html
摘要:最長公共子序列問題指的是求解兩個序列和的長度最長的公共子序列。當然,可以看出,問題容易出現(xiàn)重疊子問題,這時候,就需要用動態(tài)規(guī)劃法來解決。 問題介紹 ??給定一個序列$X=$,另一個序列$Z=$滿足如下條件時稱為X的子序列:存在一個嚴格遞增的X的下標序列${i_1,i_2,...,i_k}$,對所有的$j=1,2,...,k$滿足$x_{i_j}=z_j.$??給定兩個序列$X$和$Y$...
摘要:若且,則是和的最長公共子序列若且,則是和的最長公共子序列。遞歸結構容易看到最長公共子序列問題具有子問題重疊性質。例如,在計算和的最長公共子序列時,可能要計算出和及和的最長公共子序列。 雖是讀書筆記,但是如轉載請注明出處 http://segmentfault.com/blog/exploring/ .. 拒絕伸手復制黨 本章講解: 1. LCS(最長公共子序列)O(n^2)的時間復雜...
摘要:最長公共子序列動態(tài)規(guī)劃問題,局部最小單元兩值是否相等,相等則從對角線上個位置處的數(shù)值,繼續(xù)狀態(tài)延續(xù)不相等則從上下兩個過去的位置找值保持延續(xù),在上下兩個過去位置中保持著之前的最長子序列。 最長公共子序列 動態(tài)規(guī)劃問題,局部最小單元:兩值是否相等,相等則從對角線上個位置處的數(shù)值+1,繼續(xù)狀態(tài)延續(xù); 不相等則從上下兩個過去的位置找值保持延續(xù),在上下兩個過去位置中保持著之前的最長子序列。 ...
摘要:但不是和的最長公共子序列,而序列和也均為和的最長公共子序列,長度為,而和不存在長度大于等于的公共子序列。最長公共子序列給定序列和,從它們的所有公共子序列中選出長度最長的那一個或幾個。為和的最長公共子序列長度。 最長公共子序列(Longest Common Subsequence LCS)是從給定的兩個序列X和Y中取出盡可能多的一部分字符,按照它們在原序列排列的先后次序排列得到。LCS問...
摘要:遇到問題查查,看看,大神的講解問問島胖君下面是我最近整理出來的關于字符串的文章的怎么翻譯匯集目錄非常希望強化博客的功能,比如分類,置頂。 雖是讀書筆記,但是如轉載請注明出處 http://segmentfault.com/blog/exploring/ .. 拒絕伸手復制黨 最近在看算法和語言,基本屬于看知識 --> java實現(xiàn) --> 整理blog 這個路線。 遇到問題查查st...
閱讀 1061·2023-04-26 02:02
閱讀 2401·2021-09-26 10:11
閱讀 3553·2019-08-30 13:10
閱讀 3743·2019-08-29 17:12
閱讀 720·2019-08-29 14:20
閱讀 2187·2019-08-28 18:19
閱讀 2230·2019-08-26 13:52
閱讀 954·2019-08-26 13:43