最長(zhǎng)公共子序列問(wèn)題LCS

參考解答

動(dòng)態(tài)規(guī)劃算法可有效地解此問(wèn)題。下面我們按照動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)的各個(gè)步驟來(lái)設(shè)計(jì)一個(gè)解此問(wèn)題的有效算法。

1.最長(zhǎng)公共子序列的結(jié)構(gòu)

解最長(zhǎng)公共子序列問(wèn)題時(shí)最容易想到的算法是窮舉搜索法，即對(duì)X的每一個(gè)子序列，檢查它是否也是Y的子序列，從而確定它是否為X和Y的公共子序列，并 且在檢查過(guò)程中選出最長(zhǎng)的公共子序列。X的所有子序列都檢查過(guò)后即可求出X和Y的最長(zhǎng)公共子序列。X的一個(gè)子序列相應(yīng)于下標(biāo)序列{1, 2, …, m}的一個(gè)子序列，因此，X共有2^m個(gè)不同子序列，從而窮舉搜索法需要指數(shù)時(shí)間。

事實(shí)上，最長(zhǎng)公共子序列問(wèn)題也有最優(yōu)子結(jié)構(gòu)性質(zhì)，因?yàn)槲覀冇腥缦露ɡ恚?/p>

定理: LCS的最優(yōu)子結(jié)構(gòu)性質(zhì)

設(shè)序列X=<x₁, x₂, …, x_m>和Y=<y₁, y₂, …, y_n>的一個(gè)最長(zhǎng)公共子序列Z=<z₁, z₂, …, z_k>，則：

1. 若x_m=y_n，則z_k=x_m=y_n且Z_k-1是X_m-1和Y_n-1的最長(zhǎng)公共子序列；
2. 若x_m≠y_n且z_k≠x_{m ，}則Z是X_m-1和Y的最長(zhǎng)公共子序列；
3. 若x_m≠y_n且z_k≠y_n ，則Z是X和Y_n-1的最長(zhǎng)公共子序列。

其中X_m-1=<x₁, x₂, …, x_m-1>，Y_n-1=<y₁, y₂, …, y_n-1>，Z_k-1=<z₁, z₂, …, z_k-1>。

證明

1. 用反證法。若z_k≠x_m，則<z₁, z₂, …, z_k ,x_m >是X和Y的長(zhǎng)度為k十1的公共子序列。這與Z是X和Y的一個(gè)最長(zhǎng)公共子序列矛盾。因此，必有z_k=x_m=y_n。由此可知Z_k-1是X_m-1和Y_n-1的一個(gè)長(zhǎng)度為k-1的公共子序列。若X_m-1和Y_n-1有一個(gè)長(zhǎng)度大于k-1的公共子序列W，則將x_m加在其尾部將產(chǎn)生X和Y的一個(gè)長(zhǎng)度大于k的公共子序列。此為矛盾。故Z_k-1是X_m-1和Y_n-1的一個(gè)最長(zhǎng)公共子序列。
2. 由于z_k≠x_m，Z是X_m-1和Y的一個(gè)公共子序列。若X_m-1和Y有一個(gè)長(zhǎng)度大于k的公共子序列W，則W也是X和Y的一個(gè)長(zhǎng)度大于k的公共子序列。這與Z是X和Y的一個(gè)最長(zhǎng)公共子序列矛盾。由此即知Z是X_m-1和Y的一個(gè)最長(zhǎng)公共子序列。
3. 與 2.類(lèi)似。

這個(gè)定理告訴我們，兩個(gè)序列的最長(zhǎng)公共子序列包含了這兩個(gè)序列的前綴的最長(zhǎng)公共子序列。因此，最長(zhǎng)公共子序列問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

2.子問(wèn)題的遞歸結(jié)構(gòu)

由最長(zhǎng)公共子序列問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)可知，要找出X=<x₁, x₂, …, x_m>和Y=<y₁, y₂, …, y_n>的最長(zhǎng)公共子序列，可按以下方式遞歸地進(jìn)行：當(dāng)x_m=y_n時(shí)，找出X_m-1和Y_n-1的最長(zhǎng)公共子序列，然后在其尾部加上x(chóng)_m(=y_n)即可得X和Y的一個(gè)最長(zhǎng)公共子序列。當(dāng)x_m≠y_n時(shí)，必須解兩個(gè)子問(wèn)題，即找出X_m-1和Y的一個(gè)最長(zhǎng)公共子序列及X和Y_n-1的一個(gè)最長(zhǎng)公共子序列。這兩個(gè)公共子序列中較長(zhǎng)者即為X和Y的一個(gè)最長(zhǎng)公共子序列。

由此遞歸結(jié)構(gòu)容易看到最長(zhǎng)公共子序列問(wèn)題具有子問(wèn)題重疊性質(zhì)。例如，在計(jì)算X和Y的最長(zhǎng)公共子序列時(shí)，可能要計(jì)算出X和Y_n-1及X_m-1和Y的最長(zhǎng)公共子序列。而這兩個(gè)子問(wèn)題都包含一個(gè)公共子問(wèn)題，即計(jì)算X_m-1和Y_n-1的最長(zhǎng)公共子序列。

與矩陣連乘積最優(yōu)計(jì)算次序問(wèn)題類(lèi)似，我們來(lái)建立子問(wèn)題的最優(yōu)值的遞歸關(guān)系。用c[i,j]記錄序列X_i和Y_j的最長(zhǎng)公共子序列的長(zhǎng)度。其中X_i=<x₁, x₂, …, x_i>，Y_j=<y₁, y₂, …, y_j>。當(dāng)i=0或j=0時(shí)，空序列是X_i和Y_j的最長(zhǎng)公共子序列，故c[i,j]=0。其他情況下，由定理可建立遞歸關(guān)系如下：

3.計(jì)算最優(yōu)值

直接利用(2.2)式容易寫(xiě)出一個(gè)計(jì)算c[i,j]的遞歸算法，但其計(jì)算時(shí)間是隨輸入長(zhǎng)度指數(shù)增長(zhǎng)的。由于在所考慮的子問(wèn)題空間中，總共只有θ(m*n)個(gè)不同的子問(wèn)題，因此，用動(dòng)態(tài)規(guī)劃算法自底向上地計(jì)算最優(yōu)值能提高算法的效率。

計(jì)算最長(zhǎng)公共子序列長(zhǎng)度的動(dòng)態(tài)規(guī)劃算法LCS_LENGTH(X,Y)以序列X=<x₁, x₂, …, x_m>和Y=<y₁, y₂, …, y_n>作為輸入。輸出兩個(gè)數(shù)組c[0..m ,0..n]和b[1..m ,1..n]。其中c[i,j]存儲(chǔ)X_i與Y_j的最長(zhǎng)公共子序列的長(zhǎng)度，b[i,j]記錄指示c[i,j]的值是由哪一個(gè)子問(wèn)題的解達(dá)到的，這在構(gòu)造最長(zhǎng)公共子序列時(shí)要用到。最后，X和Y的最長(zhǎng)公共子序列的長(zhǎng)度記錄于c[m,n]中。

Procedure LCS_LENGTH(X,Y);

begin

m:=length[X];

n:=length[Y];

for i:=1 to m do c[i,j]:=0;

for j:=1 to n do c[0,j]:=0;

for i:=1 to m do

for j:=1 to n do

if x[i]=y[j] then

begin

c[i,j]:=c[i-1,j-1]+1;

b[i,j]:="↖";

end

else if c[i-1,j]≥c[i,j-1] then

begin

c[i,j]:=c[i-1,j];

b[i,j]:="↑";

end

else

begin

c[i,j]:=c[i,j-1];

b[i,j]:="←"

end;

return(c,b);

end;

由于每個(gè)數(shù)組單元的計(jì)算耗費(fèi)Ο(1)時(shí)間，算法LCS_LENGTH耗時(shí)Ο(mn)。

4.構(gòu)造最長(zhǎng)公共子序列

由算法LCS_LENGTH計(jì)算得到的數(shù)組b可用于快速構(gòu)造序列X=<x₁, x₂, …, x_m>和Y=<y₁, y₂, …, y_n>的最長(zhǎng)公共子序列。首先從b[m,n]開(kāi)始，沿著其中的箭頭所指的方向在數(shù)組b中搜索。當(dāng)b[i,j]中遇到"↖"時(shí)，表示X_i與Y_j的最長(zhǎng)公共子序列是由X_i-1與Y_j-1的最長(zhǎng)公共子序列在尾部加上x(chóng)_i得到的子序列；當(dāng)b[i,j]中遇到"↑"時(shí)，表示X_i與Y_j的最長(zhǎng)公共子序列和X_i-1與Y_j的最長(zhǎng)公共子序列相同；當(dāng)b[i,j]中遇到"←"時(shí)，表示X_i與Y_j的最長(zhǎng)公共子序列和X_i與Y_j-1的最長(zhǎng)公共子序列相同。

下面的算法LCS(b,X,i,j)實(shí)現(xiàn)根據(jù)b的內(nèi)容打印出X_i與Y_j的最長(zhǎng)公共子序列。通過(guò)算法的調(diào)用LCS(b,X,length[X],length[Y])，便可打印出序列X和Y的最長(zhǎng)公共子序列。

Procedure LCS(b,X,i,j);

begin

if i=0 or j=0 then return;

if b[i,j]="↖" then

begin

LCS(b,X,i-1,j-1);

print(x[i]); {打印x[i]}

end

else if b[i,j]="↑" then LCS(b,X,i-1,j) 

else LCS(b,X,i,j-1);

end; 

在算法LCS中，每一次的遞歸調(diào)用使i或j減1，因此算法的計(jì)算時(shí)間為O(m+n)。

例如，設(shè)所給的兩個(gè)序列為X=<A，B，C，B，D，A，B>和Y=<B，D，C，A，B，A>。由算法LCS_LENGTH和LCS計(jì)算出的結(jié)果如圖2所示。

圖2   算法LCS的計(jì)算結(jié)果

5.算法的改進(jìn)

對(duì)于一個(gè)具體問(wèn)題，按照一般的算法設(shè)計(jì)策略設(shè)計(jì)出的算法，往往在算法的時(shí)間和空間需求上還可以改進(jìn)。這種改進(jìn)，通常是利用具體問(wèn)題的一些特殊性。

例如，在算法LCS_LENGTH和LCS中，可進(jìn)一步將數(shù)組b省去。事實(shí)上，數(shù)組元素c[i,j]的值僅由c[i-1,j-1]，c[i-1, j]和c[i,j-1]三個(gè)值之一確定，而數(shù)組元素b[i,j]也只是用來(lái)指示c[i,j]究竟由哪個(gè)值確定。因此，在算法LCS中，我們可以不借助于數(shù) 組b而借助于數(shù)組c本身臨時(shí)判斷c[i,j]的值是由c[i-1,j-1]，c[i-1,j]和c[i,j-1]中哪一個(gè)數(shù)值元素所確定，代價(jià)是Ο(1)時(shí)間。既然b對(duì)于算法LCS不是必要的，那么算法LCS_LENGTH便不必保存它。這一來(lái)，可節(jié)省θ(mn)的空間，而LCS_LENGTH和LCS所需要的時(shí)間分別仍然是Ο(mn)和Ο(m+n)。不過(guò)，由于數(shù)組c仍需要Ο(mn)的空間，因此這里所作的改進(jìn)，只是在空間復(fù)雜性的常數(shù)因子上的改進(jìn)。

另外，如果只需要計(jì)算最長(zhǎng)公共子序列的長(zhǎng)度，則算法的空間需求還可大大減少。事實(shí)上，在計(jì)算c[i,j]時(shí)，只用到數(shù)組c的第i行和第i-1行。因此，只要用2行的數(shù)組空間就可以計(jì)算出最長(zhǎng)公共子序列的長(zhǎng)度。更進(jìn)一步的分析還可將空間需求減至min(m, n)。