以下內(nèi)容純是為了熟悉《算法導(dǎo)論》中的內(nèi)容，高手可略過，其中涉及的書本內(nèi)容的版權(quán)歸原作者、譯者、出版社所有

　　==================================================================

　　求最長公共子序列，一個典型的 動態(tài)規(guī)劃題 和 字符串處理算法，寫在這里是希望自己以后能多來看看和改改，溫故而知新，有時間的話再加入c/c++代碼。

　　下面進入正題：

　　%% 什么是子序列？概念有點暈，不過拿來學(xué)習(xí)怎么來精確表達一種內(nèi)容挺好 %%

　　一個給定序列的子序列就是該給定序列中去掉零個或者多個元素。以形式化的方式來說，給定一個序列X=<x₁, x₂, ..., x_m>，另一個序列Z=<z₁, z₂, ..., z_k>是X的一個子序列，如果存在X的一個嚴格遞增下標(biāo)序列<i₁, i₂, ..., i_k>，使得對所有的j=1, 2, ..., k，有Xi_j=z_j。例如，Z=<B, C, D, B>是X=<A, B, C, B, D, A, B>的一個子序列，相應(yīng)的下標(biāo)序列為<2, 3, 5, 7>。

　　%% 什么是（最長）公共子序列？概念還是有點暈 %%

　　給定兩個序列X和Y，稱序列Z是X和Y的公共子序列，如果Z既是X的一個子序列又是Y的一個子序列。例如，如果X=<A, B, C, B, D, A, B>，Y=<B, D, C, A, B, A>，則序列<B, C, A>即為X和Y的一個公共子序列。但是序列<B, C, A>不是X和Y的一個最長公共子序列(Longest-Common-Subsequence, LCS)，因為它的長度等于3，而同為X和Y的公共子序列<B, C, B, A>其長度等于4。序列<B, C, B, A>是X和Y的一個LCS，序列<B, D, A, B>也是，因為沒有長度為5或更大的公共子序列。

　　在最長子序列問題中，給定了兩個序列X=<x₁, x₂, ..., x_m>和Y=<y₁, y₂, ..., y_n>，希望找出X和Y的最大長度公共子序列。

　　步驟1：描述一個最長公共子序列

　　%% 枚舉方法沒試過 %%

　　解決LCS問題的一種強力方法是枚舉出X的所有子序列，然后逐一檢查看其是否為Y的子序列，并隨時記錄發(fā)現(xiàn)的最長子序列。X的每個子序列對應(yīng)于X的下標(biāo)集{1, 2, ..., m}的一個子集。X共有2^m個子序列，因此這種方法需要指數(shù)時間，這對長序列來說是不實際的。

　　%% 可以想想“最優(yōu)子結(jié)構(gòu)性質(zhì)”是怎么描述的 %%

　　然而LCS問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，下面的定理說明了這一點。我們將看到，子問題的自然類對應(yīng)于兩個輸入序列的成對“前綴”。（%% 自然類是什么？ %%）準確的說，給定一個序列X=<x₁, x₂, ..., x_m>，對i=0, 1, ..., m，定義X的第i個前綴為X_i=<x₁, x₂, ..., x_i>。例如，如果X=<A, B, C, B, D, A, B>，則X₄=<A, B, C, B>，而X₀空序列。

　　%% 最長公共子序列的最優(yōu)子結(jié)構(gòu)的準確描述 %%

　　定理(LCS的最優(yōu)子結(jié)構(gòu))：

　　設(shè)X=<x₁, x₂, ..., x_m>和Y=<y₁, y₂, ..., y_n>為兩個序列，并設(shè)Z=<z₁, z₂, ..., z_k>為X和Y的任意一個LCS。

　　%% LCS可能不只有一個，如a,b,c和a,c,b %%

　　%% 從x_m，y_n開始比較，是為了遞歸定義 %%

　　1) 如果x_m=y_n，那么z_k=x_m=y_n而且Z_k-1是X_m-1和Y_n-1的一個LCS。

　　2) 如果x_m≠y_n，那么z_k≠x_m蘊含Z是X_m-1和Y的一個LCS。

　　3) 如果x_m≠y_n，那么z_k≠y_n蘊含Z是X和Y_n-1的一個LCS。

　　1,2,3證明略。 %% 證明是《算法導(dǎo)論》里比較繁瑣的一塊內(nèi)容，不過仔細看看過程很精彩 %%

　　步驟2：一個遞歸解

　　%% 重疊子問題在動態(tài)規(guī)劃中很常見 %%

　　由上述定理可以知道，在找X=<x₁, x₂, ..., x_m>和Y=<y₁, y₂, ..., y_n>的一個LCS時，可能要檢查一個或兩個子問題。如果x_m=y_n，必須找出X_m-1和Y_n-1的一個LCS。將x_m=y_n添加到這個LCS上，可以產(chǎn)生X和Y的一個LCS。如果x_m≠y_n，就必須解決兩個子問題：找出X_m-1和Y的一個LCS，以及找出X和Y_n-1的一個LCS。這兩個LCS中，較長的就是X和Y的一個LCS，因為這些情況涉及了所有的可能，其中一個最優(yōu)的子問題解必須被使用在X和Y的一個LCS中。

　　可以很容易地看出LCS問題中的重疊子問題性質(zhì)。為找出X和Y的一個LCS，可能需要找出X和Y_n-1的一個LCS以及X_m-1和Y的一個LCS。但這兩個子問題都包含著找X_m-1和Y_n-1的一個LCS的子子問題。還有許多其他的子問題共享子子問題。

　　%% 遞歸式看著容易理解，要自己寫的時候老是記不起來 %%

　　像在矩陣鏈乘法問題中一樣，LCS問題的遞歸解涉及到建立一個最優(yōu)解的值的遞歸式。定義c[i, j]為序列X_i和Y_i的一個LCS長度。如果i=0或j=0，其中一個的序列長度為0，因此LCS的長度為0。由LCS問題的最優(yōu)子結(jié)構(gòu)可得遞歸式

　　c[i, j] = 0　　　　　　　　　　　　　 如果 i=0 或 j=0

　　　　　= c[i-1, j-1] + 1　　　　　　　如果 i, j>0 和 x_i=y_i%% 第i個字符滿足條件，加到子序列中，長度加1 %%

　　　　　= max( c[i, j-1], c[i-1, j] )　　如果 i, j>0 和?x_i≠y_i%% 第i個字符不一樣了，根據(jù)前面的計算結(jié)果來比較哪個長一點，再取值%%

　　%% 下面的這個“子問題因為原問題的條件而被排除”沒怎么明白，是條件不同考慮的子問題不同？ %%

　　觀察這個遞歸公式，問題的一個條件限制了我們可能考慮的子問題。當(dāng)x_i=y_i時，可以而且應(yīng)該考慮尋找X_i-1和Y_i-1的LCS的子問題。否則，應(yīng)另外考慮尋找X_i和Y_j-1以及X_i-1和Y_j的LCS的兩個子問題。在前面已經(jīng)討論的動態(tài)規(guī)劃算法（裝配線調(diào)度和矩陣鏈乘法）中，沒有任何子問題因為原問題的條件而被排除。尋找LCS不是唯一的因為問題的條件而排除子問題的動態(tài)規(guī)劃算法。例如，編輯距離也具有這個特征。

　　步驟3：計算LCS的長度

　　%% 自底向上的方法，一般是多重循環(huán) %%

　　根據(jù)公式，可以很容易地寫出一個指數(shù)時間的遞歸算法，來計算兩個序列的LCS的長度。因為只有Θ(mn)個不同的子問題，所以可以用動態(tài)規(guī)劃來自底向上計算解。

　　%% c表用來記錄LCS的長度，b表用來跟蹤當(dāng)前選擇的最優(yōu)解，方便結(jié)束時構(gòu)造出來LCS %%

　　過程LCS-LENGTH以兩個序列X=<x₁, x₂, ..., x_m>和Y=<y₁, y₂, ..., y_n>為輸入。它把c[i, j]值填入一個按行計算表項的表c[0..m, 0..n]中。（也就是，c的第一行從左到右填入，然后開始第二行，等等）。它還維護表b[0..m, 0..n]以簡化最優(yōu)解的構(gòu)造。從直覺上看，b[i, j]指向一個表項，對應(yīng)于在計算c[i, j]時所選擇的最優(yōu)子問題的解。該程序返回表b和c；c[m, n]包含X和Y的一個LCS的長度。

　　%% 有了遞歸式，代碼就簡單了，說明先定義遞歸式有多重要 %%

　　偽代碼如下：

　　

View Code 1 //LCS-LENGTH(X, Y) 2 // 3 // m <- length[X] 4 // n <- length[Y] 5 // 構(gòu)造邊界 6 // for i <- 1 to m 7 // do c[i, 0] <- 0 8 // for j <- 0 to n 9 // do c[0, j] <- 0 10 // 自底向上，選擇最優(yōu)結(jié)果 11 // for i <- 1 to m 12 // do for j <- 1 to n 13 // 不同條件，不同選擇 14 // do if xi = yj 15 // then c[i, j] <- c[i-1, j-1] + 1 16 // b[i, j] <- left-up //指向左上方 17 // else if c[i-1, j] >= c[i, j-1] 18 // then c[i, j] <- c[i-1, j] 19 // b[i, j] <- up //指向上方 20 // else c[i, j] <- c[i, j-1] 21 // b[i, j] <- left //指向左邊 22 // return c and b

?

　　下圖給出了在序列X=<A, B, C, B, D, A, B>和Y=<B, D, C, A, B, A>上，由LCS-LENGTH計算出的表。這個程序的運行時間為O(mn)，因為每個表項的計算時間為O(1)。

　　

　　步驟4：構(gòu)造一個LCS

　　%% 箭頭表示方法很形象 %%

　　有LCS-LENGTH返回的表b可以被用來快速構(gòu)造X=<x₁, x₂, ..., x_m>和Y=<y₁, y₂, ..., y_n>的一個LCS。首先從b[m, n]處開始，沿著箭頭在表格中跟蹤下去。每當(dāng)在表項b[i, j]中遇到left-up時，即意味著x_i=y_j是LCS的一個元素。這種方法是按照反序來找LCS的每一個元素的。下面的遞歸過程按正常的前序輸出X和Y的一個LCS。初始調(diào)用為PRINT-LCS(b, X, length[X], length[Y])。

　　%% 這個遞歸打印結(jié)果也很好 %%

　　偽代碼如下：

　　

View Code 1 // PRINT-LCS(b, X, i, j) 2 // 3 // if i=0 or j=0 4 // then return 5 // if b[i, j] = left-up //指向左上方 6 // then PRINT-LCS(b, X, i-1, j-1) 7 // print xi 8 // else if b[i, j] = up //指向上方 9 // then PRINT-LCS(b, X, i-1, j) 10 // else PRINT-LCS(b, X, i, j-1) //指向左邊

?

　　對圖中的表b，此程序輸出“B C B A”。因為在遞歸的每個階段i和j至少有一個要減小，故該過程的運行時間為O(m+n)。

　　改進代碼

　　一旦設(shè)計出某個算法之后，常常可以在時間或者空間上對該算法做些改進。對直觀的動態(tài)規(guī)劃算法來說尤其如此，有些改變可以簡化代碼并改進一些常數(shù)因子，但并不會帶來算法性能方面的漸進改善。其他一些改變則可以在時間和空間上有相當(dāng)大的漸進節(jié)省。

　　%% 完全去掉表b（箭頭表）沒試過這種方法。 %%

　　例如，我們可以完全去掉表b。每個表項c[i, j]僅依賴于另外三個c表項：c[i-1, j-1]，c[i-1, j]和c[i, j-1]。給定c[i, j]的值，我們可以在O(1)時間內(nèi)確定這三個值中的哪一個被用來計算c[i, j]的，而不檢查表b。這樣，利用一個類似于PRINT-LCS的過程，在O(m+n)時間內(nèi)即可重構(gòu)一個LCS。（練習(xí)中要求偽代碼）。雖然用這種方法節(jié)省了Θ(mn)空間，但計算一個LCS時所需要的輔助空間并沒有漸進地減少，因為表c總是需要占據(jù)Θ(mn)空間的。

　　%% 漸進空間需求？ 計算長度的話，表c實際上是只有兩行有用，也沒試過這種方法，不過要構(gòu)造LCS還是需要一定的輔助信息 %%

　　然而，我們能減少LCS-LENGTH的漸進空間需求，因為它一次只需表c的兩行：正在被計算的一行和前面一行（實際上，僅需略多于表c一行的空間就可以計算一個LCS的長度。）。如果僅要求出一個LCS的長度，則這種改進是有用的；如果要重構(gòu)一個LCS的元素，則小的表無法包含足夠的信息來使我們在O(m+n)時間內(nèi)重新執(zhí)行以前各步。

?

轉(zhuǎn)載于:https://www.cnblogs.com/futuredo/archive/2012/10/14/2723279.html

總結(jié)

以上是生活随笔為你收集整理的【啃不完的算法导论】- 动态规划 - 最长公共子序列（概念篇）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。