<rt id="bn8ez"></rt>
<label id="bn8ez"></label>

  • <span id="bn8ez"></span>

    <label id="bn8ez"><meter id="bn8ez"></meter></label>

    [轉(zhuǎn)]LCS

    Posted on 2008-06-16 14:47 xan 閱讀(206) 評論(0)  編輯  收藏 所屬分類: Algorithms

    最長公共子序列問題LCS

    參考解答

    動態(tài)規(guī)劃算法可有效地解此問題。下面我們按照動態(tài)規(guī)劃算法設(shè)計的各個步驟來設(shè)計一個解此問題的有效算法。

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

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

    事實上,最長公共子序列問題也有最優(yōu)子結(jié)構(gòu)性質(zhì),因為我們有如下定理:

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

    設(shè)序列X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>的一個最長公共子序列Z=<z1, z2, …, zk>,則:

    1. 若xm=yn,則zk=xm=yn且Zk-1是Xm-1和Yn-1的最長公共子序列;
    2. 若xm≠yn且zk≠xm ,則Z是Xm-1和Y的最長公共子序列;
    3. 若xm≠yn且zk≠yn ,則Z是X和Yn-1的最長公共子序列。

    其中Xm-1=<x1, x2, …, xm-1>,Yn-1=<y1, y2, …, yn-1>,Zk-1=<z1, z2, …, zk-1>。

    證明

    1. 用反證法。若zk≠xm,則<z1, z2, …, zk ,xm >是X和Y的長度為k十1的公共子序列。這與Z是X和Y的一個最長公共子序列矛盾。因此,必有zk=xm=yn。由此可知Zk-1是Xm-1和Yn-1的一個長度為k-1的公共子序列。若Xm-1和Yn-1有一個長度大于k-1的公共子序列W,則將xm加在其尾部將產(chǎn)生X和Y的一個長度大于k的公共子序列。此為矛盾。故Zk-1是Xm-1和Yn-1的一個最長公共子序列。
    2. 由于zk≠xm,Z是Xm-1和Y的一個公共子序列。若Xm-1和Y有一個長度大于k的公共子序列W,則W也是X和Y的一個長度大于k的公共子序列。這與Z是X和Y的一個最長公共子序列矛盾。由此即知Z是Xm-1和Y的一個最長公共子序列。
    3. 與 2.類似。

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

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

    由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)可知,要找出X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>的最長公共子序列,可按以下方式遞歸地進行:當xm=yn時,找出Xm-1和Yn-1的最長公共子序列,然后在其尾部加上xm(=yn)即可得X和Y的一個最長公共子序列。當xm≠yn時,必須解兩個子問題,即找出Xm-1和Y的一個最長公共子序列及X和Yn-1的一個最長公共子序列。這兩個公共子序列中較長者即為X和Y的一個最長公共子序列。

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

    與矩陣連乘積最優(yōu)計算次序問題類似,我們來建立子問題的最優(yōu)值的遞歸關(guān)系。用c[i,j]記錄序列Xi和Yj的最長公共子序列的長度。其中Xi=<x1, x2, …, xi>,Yj=<y1, y2, …, yj>。當i=0或j=0時,空序列是Xi和Yj的最長公共子序列,故c[i,j]=0。其他情況下,由定理可建立遞歸關(guān)系如下:

     

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

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

    計算最長公共子序列長度的動態(tài)規(guī)劃算法LCS_LENGTH(X,Y)以序列X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>作為輸入。輸出兩個數(shù)組c[0..m ,0..n]和b[1..m ,1..n]。其中c[i,j]存儲Xi與Yj的最長公共子序列的長度,b[i,j]記錄指示c[i,j]的值是由哪一個子問題的解達到的,這在構(gòu)造最長公共子序列時要用到。最后,X和Y的最長公共子序列的長度記錄于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;

    由于每個數(shù)組單元的計算耗費Ο(1)時間,算法LCS_LENGTH耗時Ο(mn)。

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

    由算法LCS_LENGTH計算得到的數(shù)組b可用于快速構(gòu)造序列X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>的最長公共子序列。首先從b[m,n]開始,沿著其中的箭頭所指的方向在數(shù)組b中搜索。當b[i,j]中遇到"↖"時,表示Xi與Yj的最長公共子序列是由Xi-1與Yj-1的最長公共子序列在尾部加上xi得到的子序列;當b[i,j]中遇到"↑"時,表示Xi與Yj的最長公共子序列和Xi-1與Yj的最長公共子序列相同;當b[i,j]中遇到"←"時,表示Xi與Yj的最長公共子序列和Xi與Yj-1的最長公共子序列相同。

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

    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,因此算法的計算時間為O(m+n)。

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


    j
    0
    1
    2
    3
    4
    5
    6
    i

    yj
    B
    D
    C
    A
    B
    A


    0 xi

    0
    0
    0
    0
    0
    0










    1 A 0
    0
    0
    0
    1 1
    1












    2 B 0
    1 1 1
    1
    2 2










    3 C 0
    1
    1
    2 2
    2
    2










    4 B 0
    1
    1
    2
    2
    3 3









    5 D 0
    1
    2
    2
    2
    3
    3









    6 A 0
    1
    2
    2
    3
    3
    4









    7 B 0
    1
    2
    2
    3
    4
    5


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

    5.算法的改進

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

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

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


    只有注冊用戶登錄后才能發(fā)表評論。


    網(wǎng)站導(dǎo)航:
     

    posts - 36, comments - 2, trackbacks - 0, articles - 0

    Copyright © xan

    主站蜘蛛池模板: 在线观着免费观看国产黄| 国产大片91精品免费观看不卡| 日韩a级毛片免费视频| 67194在线午夜亚洲| av无码久久久久不卡免费网站 | 国拍在线精品视频免费观看| 亚洲国产日韩在线人成下载| 1000部无遮挡拍拍拍免费视频观看| 猫咪免费人成网站在线观看| 91亚洲精品视频| 国产伦精品一区二区免费| 57PAO成人国产永久免费视频| 亚洲国产精品网站久久| 一级全免费视频播放| 好吊妞788免费视频播放| 中文字幕精品亚洲无线码二区| 国产精品永久免费| 亚洲成a人片在线观看无码专区| 精品亚洲永久免费精品| 日韩高清在线高清免费| 青青草97国产精品免费观看| 亚洲欧洲∨国产一区二区三区| 成人性做爰aaa片免费看| 国产一区二区三区免费在线观看| 亚洲福利一区二区精品秒拍| 二个人看的www免费视频| 亚洲V无码一区二区三区四区观看| 亚洲av日韩aⅴ无码色老头| 久久ww精品w免费人成| 亚洲中字慕日产2021| 99久久99久久精品免费观看| 亚洲精品成人无码中文毛片不卡| 美女视频黄频a免费观看| 成熟女人牲交片免费观看视频| 免费福利在线观看| 亚洲精品无码不卡| 永久免费AV无码网站在线观看| 亚洲人成网网址在线看| 国产男女猛烈无遮挡免费视频 | 永久免费视频网站在线观看| 亚洲日韩精品无码专区加勒比|