国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

動態規劃法(十)最長公共子序列(LCS)問題

Ashin / 1635人閱讀

摘要:最長公共子序列問題指的是求解兩個序列和的長度最長的公共子序列。當然,可以看出,問題容易出現重疊子問題,這時候,就需要用動態規劃法來解決。

問題介紹

??給定一個序列$X=$,另一個序列$Z=$滿足如下條件時稱為X的子序列:存在一個嚴格遞增的X的下標序列${i_1,i_2,...,i_k}$,對所有的$j=1,2,...,k$滿足$x_{i_j}=z_j.$
??給定兩個序列$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。
??本文將具體闡釋如何用動態規劃法(Dynamic Programming)來求解最長公共子序列(LCS)問題。

算法分析 1. LCS的子結構

??給定一個序列$X=$,對$i=0,1,...,m$,定義$X$的第i前綴為$X_i=$,其中$X_0$為空序列。
??(LCS的子結構)令$X=$和$Y=$為兩個序列,$Z=$為$X$和$Y$的任意LCS,則:

如果$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=$和$Y=$的一個LCS時,需要求解一個或兩個子問題:如果$x_m=y_n$,應求解$X_{m-1}$和$Y_{n-1}$的一個LCS,再將$x_m=y_n$追加到這個LCS的末尾,就得到$X$和$Y$的一個LCS;如果$x_m eq y_n$,需求解$X_{m-1}$和$Y$的一個LCS與$X$和$Y_{n-1}$的一個LCS,兩個LCS較長者即為$X$和$Y$的一個LCS。當然,可以看出,LCS問題容易出現重疊子問題,這時候,就需要用動態規劃法來解決。
??定義$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=$和$Y=$為輸入。它將$c[i, j]$的值保存在表$c$中,同時,維護一個表$b$,幫助構造最優解。過程LCS-LENGTH的偽代碼如下:

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 b
4. 尋找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)
程序實現

??有了以上對LCS問題的算法分析,我們不難寫出具體的程序來實現它。下面將會給出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 {
    // 主函數
    public static void main(String[] args) {
        // 兩個序列X和Y
        List X = 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
    }

    /*
    函數LCS_length:獲取維護表b的值
    傳入參數: 兩個序列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 
參考文獻

算法導論(第三版) 機械工業出版社

https://www.geeksforgeeks.org...

注意:本人現已開通兩個微信公眾號: 因為Python(微信號為:python_math)以及輕松學會Python爬蟲(微信號為:easy_web_scrape), 歡迎大家關注哦~~

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/69731.html

相關文章

  • 動態劃法最長公共序列LCS問題

    摘要:最長公共子序列問題指的是求解兩個序列和的長度最長的公共子序列。當然,可以看出,問題容易出現重疊子問題,這時候,就需要用動態規劃法來解決。 問題介紹 ??給定一個序列$X=$,另一個序列$Z=$滿足如下條件時稱為X的子序列:存在一個嚴格遞增的X的下標序列${i_1,i_2,...,i_k}$,對所有的$j=1,2,...,k$滿足$x_{i_j}=z_j.$??給定兩個序列$X$和$Y$...

    IamDLY 評論0 收藏0
  • 算法設計 - LCS 最長公共序列&&最長公共串 &&LIS 最

    摘要:若且,則是和的最長公共子序列若且,則是和的最長公共子序列。遞歸結構容易看到最長公共子序列問題具有子問題重疊性質。例如,在計算和的最長公共子序列時,可能要計算出和及和的最長公共子序列。 雖是讀書筆記,但是如轉載請注明出處 http://segmentfault.com/blog/exploring/ .. 拒絕伸手復制黨 本章講解: 1. LCS(最長公共子序列)O(n^2)的時間復雜...

    weizx 評論0 收藏0
  • 最長公共序列LCS

    摘要:最長公共子序列動態規劃問題,局部最小單元兩值是否相等,相等則從對角線上個位置處的數值,繼續狀態延續不相等則從上下兩個過去的位置找值保持延續,在上下兩個過去位置中保持著之前的最長子序列。 最長公共子序列 動態規劃問題,局部最小單元:兩值是否相等,相等則從對角線上個位置處的數值+1,繼續狀態延續; 不相等則從上下兩個過去的位置找值保持延續,在上下兩個過去位置中保持著之前的最長子序列。 ...

    UnixAgain 評論0 收藏0
  • javascript 最長公共序列

    摘要:但不是和的最長公共子序列,而序列和也均為和的最長公共子序列,長度為,而和不存在長度大于等于的公共子序列。最長公共子序列給定序列和,從它們的所有公共子序列中選出長度最長的那一個或幾個。為和的最長公共子序列長度。 最長公共子序列(Longest Common Subsequence LCS)是從給定的兩個序列X和Y中取出盡可能多的一部分字符,按照它們在原序列排列的先后次序排列得到。LCS問...

    Xufc 評論0 收藏0
  • 字符串處理文章outline

    摘要:遇到問題查查,看看,大神的講解問問島胖君下面是我最近整理出來的關于字符串的文章的怎么翻譯匯集目錄非常希望強化博客的功能,比如分類,置頂。 雖是讀書筆記,但是如轉載請注明出處 http://segmentfault.com/blog/exploring/ .. 拒絕伸手復制黨 最近在看算法和語言,基本屬于看知識 --> java實現 --> 整理blog 這個路線。 遇到問題查查st...

    Karuru 評論0 收藏0

發表評論

0條評論

Ashin

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<