動(dòng)態(tài)規(guī)劃解最長(zhǎng)公共子序列(共6頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上動(dòng)態(tài)規(guī)劃解最長(zhǎng)公共子序列 一、 問題描述與分析經(jīng)常遇到一些復(fù)雜的問題，有時(shí)我們將待求解問題分解成若干個(gè)子問題，先求解子問題，然后從這些子問題的解得到原問題的解。由于分解到的子問題往往不是獨(dú)立的，用一個(gè)表來記錄所有已解決的子問題的答案，這樣就得到了原問題的解，這就是動(dòng)態(tài)規(guī)劃法的基本思想。一個(gè)給定序列的子序列是在該序列中刪去若干元素后得到的序列。給定兩個(gè)序列X和Y，當(dāng)另一序列Z即是X的子序列又是Y的子序列時(shí)，稱Z是序列X和Y的公共子序列。在公共子序列中長(zhǎng)度最長(zhǎng)的則是最長(zhǎng)公共子序列。窮舉搜索法是最容易想到的解題算法。對(duì)X的所有子序列，檢查它是否也是Y的子序列，從而確定它是否

2、是X和Y的公共子序列。并且在檢查過程中記錄最長(zhǎng)的公共子序列。X的所有子序列都檢查過后即可求出X和Y的最長(zhǎng)公共子序列。事實(shí)上，最長(zhǎng)公共子序列問題具有最優(yōu)子結(jié)構(gòu)的結(jié)構(gòu)性質(zhì)。二、 算法設(shè)計(jì)1. 最長(zhǎng)公共子序列的結(jié)構(gòu)設(shè)序列X=x1,x2,xm和Y=y1,y2,yn的最長(zhǎng)公共子序列為Z=z1,z2,zk，則1) 若xm=yn，則zk=xm=yn，且Zk-1是Xm-1和Yn-1的最長(zhǎng)公共子序列；2) 若xmyn 且zkxm，則Z是Xm-1和Y的最長(zhǎng)公共子序列；3) 若xmyn 且zkyn，則Z是X和Yn-1的最長(zhǎng)公共子序列。其中，Xm-1=x1,x2,xm-1; Yn-1=y1,y2,yn-1; Zk-1

3、=z1,z2,zk-1。證明： 1) 用反證法。若zkxm，則z1,z2,zk,xm是X和Y的長(zhǎng)度為k+1的公共子序列。這與Z是X和Y的最長(zhǎng)公共子序列矛盾。因此，必有zk=xm=yn。由此可知Zk-1是Xm-1和Yn-1的長(zhǎng)度為k-1的公共子序列。若Xm-1和Yn-1有長(zhǎng)度大于k-1的公共子序列W，則將xm加在其尾部產(chǎn)生X和Y的長(zhǎng)度大于k的公共子序列。此為矛盾。故Zk-1是Xm-1和Yn-1的最長(zhǎng)公共子序列。2) 由于zkxm，Z是Xm-1和Y的公共子序列。若Xm-1和Y有長(zhǎng)度大于k的公共子序列W，則W也是X和Y的長(zhǎng)度大于k的公共子序列。這與Z是X和Y的最長(zhǎng)公共子序列矛盾。由此即知，Z是Xm-

4、1和Y的公共子序列。3) 證明與（2）類似。2. 子問題的遞歸結(jié)構(gòu)由最長(zhǎng)公共子序列的問題的最優(yōu)子結(jié)構(gòu)可知，當(dāng)xm=yn時(shí)，找出是Xm-1和Yn-1的最長(zhǎng)公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的最長(zhǎng)公共子序列。當(dāng)xmyn時(shí)，必須解兩個(gè)子問題，即找出Xm-1和Y的一個(gè)最長(zhǎng)公共子序列及X和Yn-1的一個(gè)最長(zhǎng)公共子序列。這兩個(gè)公共子序列中較長(zhǎng)者即為X和Y的最長(zhǎng)公共子序列。由此遞歸結(jié)構(gòu)容易看到最長(zhǎng)公共子序列問題具有子問題重疊性質(zhì)。首先建立子問題最優(yōu)值的遞歸關(guān)系。用Cij記錄序列Xi和Yj的最長(zhǎng)公共子序列的長(zhǎng)度。其中Xi=x1,x2,xm；Yj=y1,y2,yn。當(dāng)i=0或j=0時(shí)，空序列

5、是Xi和Yj的最長(zhǎng)公共子序列，故此時(shí)Cij=0。在其他情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：Cij= 0 i=0，j=0 ci-1j-1+1 i，j>0；xi =yj maxcij-1，ci-1j i，j>0；xi yj 3. 例子：求兩字符序列的最長(zhǎng)公共字符子序列問題描述：字符序列的子序列是指從給定字符序列中隨意地（不一定連續(xù)）去掉若干個(gè)字符（可能一個(gè)也不去掉）后所形成的字符序列。令給定的字符序列X=x1,x2,xm，序列Y=y1,y2,yn是X的子序列，存在X的一個(gè)嚴(yán)格遞增下標(biāo)序列i0，i1，ik-1，使得對(duì)所有的j=0，1，k-1，有xi=yj。例如，X=“BACDCA

6、”，Y=“ABDCA”是X的一個(gè)子序列?？紤]最長(zhǎng)公共子序列問題如何分解成子問題，設(shè)A=a0，a1，am-1，B=b0，b1，bm-1，并Z=z0，z1，zm-1為它們的最長(zhǎng)公共子序列。不難證明有以下性質(zhì)：1) 如果am-1=bn-1，則若zk-1=am-1=bn-1，得z0，z1，zm-1是a0，a1，am-1和b0，b1，bm-1的一個(gè)最長(zhǎng)公共子序列；2) 如果am-1bn-1，則若zk-1am-1，得z0，z1，zm-1是a0，a1，am-2和b0，b1，bm-1的一個(gè)最長(zhǎng)公共子序列；3) 如果am-1bn-1，則若zk-1bn-1，得z0，z1，zm-1是a0，a1，am-1和b0，b1

7、，bm-2的一個(gè)最長(zhǎng)公共子序列。這樣，在找A和B的公共子序列時(shí)，如有am-1=bn-1，則進(jìn)一步解決一個(gè)子問題，找a0，a1，am-1和b0，b1，bm-1的一個(gè)最長(zhǎng)公共子序列；如果zk-1bn-1，則要解決兩個(gè)子問題，找出a0，a1，am-2和b0，b1，bm-1的一個(gè)最長(zhǎng)公共子序列和找出a0，a1，am-1和b0，b1，bm-2的一個(gè)最長(zhǎng)公共子序列，再取兩者中較長(zhǎng)者作為A和B的最長(zhǎng)公共子序列。引進(jìn)一個(gè)二維數(shù)組cij，用cij記錄Xi與Yj的LCS 的長(zhǎng)度，bij記錄 cij，是通過哪一個(gè)子問題的值求得的，以決定搜索的方向。我們是自底向上進(jìn)行遞推計(jì)算，那么在計(jì)算cij之前，ci-1j-1，c

8、i-j與cij-1均已計(jì)算出來。此時(shí)我們根據(jù)xi=yj還是xiyj，就可以計(jì)算出cij?；厮葺敵鲎铋L(zhǎng)公共子序列過程：jABDCAi000000B00211131313A01112121221C01212122122D01212212222C01212223133A01112223241則輸出結(jié)果為：BDCA由于每次調(diào)用至少向上或向左（或向上向左同時(shí)）移動(dòng)一步，故最多調(diào)用(m + n)次就會(huì)遇到i = 0或j = 0的情況，此時(shí)開始返回。返回時(shí)與遞歸調(diào)用時(shí)方向相反，步數(shù)相同，故算法時(shí)間復(fù)雜度為Om+n。4. 得出算法：計(jì)算最優(yōu)化：cij存儲(chǔ)Xi與Yj的最長(zhǎng)公共子序列的長(zhǎng)度，bij記錄 cij的值

9、是由那一個(gè)子問題得到的。問題的最優(yōu)值，即X和Y的最長(zhǎng)公共子序列的長(zhǎng)度記錄于cmn中。void LcsLength(char x, char y, int m, int n, int c, int b) for(int i = 0; i <= m; i+)ci0 = 0; for(int j = 1; j <= n; j+)c0j = 0;for(i = 1; i<= m; i+)for(j = 1; j <= n; j+) if(xi-1 = yj-1) cij = ci-1j-1 + 1; bij = 1; else if(ci-1j >= cij-1) cij

10、 = ci-1j; bij = 2; else cij = cij-1; bij = 3; 在算法Lcslength中，由于每個(gè)數(shù)組單元的計(jì)算耗費(fèi)O1,故算法耗時(shí)Omn。構(gòu)造最長(zhǎng)公共子序列：從bmn開始，依其值在數(shù)組b中搜索。當(dāng)bij=1時(shí)，表示Xi和Yj的最長(zhǎng)公共子序列是由Xi-1和Yj-1的最長(zhǎng)公共子序列在尾部加上xi所得到的子序列；當(dāng)bij=2時(shí)，表示Xi和Yj的最長(zhǎng)公共子序列與Xi-1和Yj的最長(zhǎng)公共子序列相同；bij=3時(shí)，表示Xi和Yj的最長(zhǎng)公共子序列與Xi和Yj-1的最長(zhǎng)公共子序列相同。void LCS(int b, char x, int i, int j) if(i = 0

11、| j = 0) return; if(bij = 1) LCS(b, x, i-1, j-1); printf("%c", xi-1); else if(bij = 2) LCS(b, x, i-1, j); else LCS(b, x, i, j-1);在算法LCS中，每一次遞歸調(diào)用使i或j減1，因此算法的計(jì)算時(shí)間為Om+n。三、 算法實(shí)現(xiàn)#include <stdio.h>#include <string.h>void LCSLength(char x20, char y20, int m, int n, int c2020, int b202

12、0) int i,j; for(i = 0; i <= m; i+) ci0 = 0; for(j = 1; j <= n; j+) c0j = 0; for(i = 1; i<= m; i+) for(j = 1; j <= n; j+) if(xi-1 = yj-1) cij = ci-1j-1 + 1; bij = 1; else if(ci-1j >= cij-1) cij = ci-1j; bij = 2; else cij = cij-1; bij = 3; void LCS(int b2020, char x20, int i, int j) if(

13、i = 0 | j = 0) return; if(bij = 1) LCS(b, x, i-1, j-1); printf("%c", xi-1); else if(bij = 2) LCS(b, x, i-1, j); else LCS(b, x, i, j-1);int main() char x20,y20;printf("請(qǐng)輸入第一組序列： "); gets(x);printf("請(qǐng)輸入第二組序列： ");gets(y); int b2020,c2020; int m, n; m = strlen(x); n = strle

14、n(y); LCSLength(x, y, m, n, c, b); LCS(b, x, m, n); printf("n長(zhǎng)度為：%dn",cmn); return 0;四、 算法分析與改進(jìn)在算法Lcslength中，由于每個(gè)數(shù)組單元的計(jì)算耗費(fèi)O1,故算法耗時(shí)Omn。在算法LCS中，每一次遞歸調(diào)用使i或j減1，因此算法的計(jì)算時(shí)間為Om+n。算法可以進(jìn)一步改進(jìn)：在算法Lcslength和Lcs中，可進(jìn)一步將數(shù)組b省去。對(duì)于數(shù)組cij，可以不借助于數(shù)組b而僅借助于c本身，在O1時(shí)間內(nèi)確定cij的值是由ci-1j-1，ci-1j和cij-1中哪一個(gè)值所確定的。因此，可以寫一個(gè)類似于Lcs的算