天天看點
傳回

動态規劃解最長公共子序列問題1 最長公共子序列問題概述2 動态規劃求解最長公共子序列問題3 實作代碼4 測試結果

1 最長公共子序列問題概述

1.1 問題定義

序列 A = { a 1 , a 2 , . . . , a m } A=\{a_1,a_2,...,a_m\} A={a1​,a2​,...,am​}，序列 B = { b 1 , b 2 , . . . , b n } B=\{b_1,b_2,...,b_n\} B={b1​,b2​,...,bn​}。如果存在一個序列 C = { c 1 , c 2 , . . . , c k } C=\{c_1,c_2,...,c_k\} C={c1​,c2​,...,ck​}，其中 c i ∈ A , B c_i \in A,B ci​∈A,B ( i = 1 , 2 , . . . , k ) (i=1,2,...,k) (i=1,2,...,k)，且 c 1 , c 2 , . . . , c k c_1,c_2,...,c_k c1​,c2​,...,ck​在 A , B A,B A,B中出現的先後順序要保持一緻，則稱序列 C C C是序列 A A A和序列 B B B的公共子序列。

要求找出序列 A A A和序列 B B B的最長的公共子序列。

1.2 舉個栗子

序列 A = { 1 , 2 , 3 } A=\{1,2,3\} A={1,2,3}，序列 B = { 2 , 3 , 4 } B=\{2,3,4\} B={2,3,4}。

序列 A A A的子序列有： { 1 } , { 2 } , { 3 } , { 1 , 2 } , { 1 , 3 } , { 2 , 3 } , { 1 , 2 , 3 } \{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\} {1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}

序列 B B B的子序列有： { 2 } , { 3 } , { 4 } , { 2 , 3 } , { 2 , 4 } , { 3 , 4 } , { 2 , 3 , 4 } \{2\},\{3\},\{4\},\{2,3\},\{2,4\},\{3,4\},\{2,3,4\} {2},{3},{4},{2,3},{2,4},{3,4},{2,3,4}

序列 A A A和 B B B的公共子序列有： { 2 } , { 3 } , { 2 , 3 } \{2\},\{3\},\{2,3\} {2},{3},{2,3}

是以序列 A A A和 B B B的最長公共子序列是： { 2 , 3 } \{2,3\} {2,3}

2 動态規劃求解最長公共子序列問題

序列 A = { a 1 , a 2 , . . . , a m } A=\{a_1,a_2,...,a_m\} A={a1​,a2​,...,am​}，序列 B = { b 1 , b 2 , . . . , b n } B=\{b_1,b_2,...,b_n\} B={b1​,b2​,...,bn​}。

假設序列 C = { c 1 , c 2 , . . . , c k } C=\{c_1,c_2,...,c_k\} C={c1​,c2​,...,ck​}是兩個序列的最長公共子序列，則有以下推論：

  • 如果 a m = b n a_m=b_n am​=bn​，則 c k = a m = b n c_k=a_m=b_n ck​=am​=bn​，且序列 { c 1 , c 2 , . . . , c k − 1 } \{c_1,c_2,...,c_{k-1}\} {c1​,c2​,...,ck−1​}是序列 { a 1 , a 2 , . . . , a m − 1 } \{a_1,a_2,...,a_{m-1}\} {a1​,a2​,...,am−1​}和序列 { b 1 , b 2 , . . . , b n − 1 } \{b_1,b_2,...,b_{n-1}\} {b1​,b2​,...,bn−1​}的最長公共子序列
  • 如果 a m ≠ b n a_m\neq b_n am​​=bn​，且 c k ≠ a m c_k\neq a_m ck​​=am​，則 c k = b n c_k=b_n ck​=bn​，序列 { c 1 , c 2 , . . . , c k } \{c_1,c_2,...,c_{k}\} {c1​,c2​,...,ck​}是序列 { a 1 , a 2 , . . . , a m − 1 } \{a_1,a_2,...,a_{m-1}\} {a1​,a2​,...,am−1​}和序列 { b 1 , b 2 , . . . , b n } \{b_1,b_2,...,b_{n}\} {b1​,b2​,...,bn​}的最長公共子序列
  • 如果 a m ≠ b n a_m\neq b_n am​​=bn​，且 c k ≠ b n c_k\neq b_n ck​​=bn​，則 c k = a m c_k=a_m ck​=am​，序列 { c 1 , c 2 , . . . , c k } \{c_1,c_2,...,c_{k}\} {c1​,c2​,...,ck​}是序列 { a 1 , a 2 , . . . , a m } \{a_1,a_2,...,a_{m}\} {a1​,a2​,...,am​}和序列 { b 1 , b 2 , . . . , b n − 1 } \{b_1,b_2,...,b_{n-1}\} {b1​,b2​,...,bn−1​}的最長公共子序列

記 C [ i , j ] C[i,j] C[i,j]為序列 { a 1 , a 2 , . . . , a i } \{a_1,a_2,...,a_i\} {a1​,a2​,...,ai​}和序列 { b 1 , b 2 , . . . , b j } \{b_1,b_2,...,b_j\} {b1​,b2​,...,bj​}的最長公共子序列(LCS)的長度。根據上述推論，可以得到 C [ i , j ] C[i,j] C[i,j]的遞推公式：

C [ i , j ] = { 0 i = 0 或 j = 0 C [ i − 1 , j − 1 ] + 1 i , j > 0 , x i = y i m a x { C [ i , j − 1 ] , C [ i − 1 , j ] } x , j > 0 , x i ≠ y j C[i,j]=\left\{ \begin{array}{lcl} 0 & &{i=0 或 j=0}\\ C[i-1,j-1]+1 & &{i,j>0,x_i=y_i}\\ max\{C[i,j-1],C[i-1,j]\} & &{x,j>0,x_i\neq y_j} \end{array} \right. C[i,j]=⎩⎨⎧​0C[i−1,j−1]+1max{C[i,j−1],C[i−1,j]}​​i=0或j=0i,j>0,xi​=yi​x,j>0,xi​​=yj​​

在求最長公共子序列長度矩陣 C C C的時候，需要借助一個輔助矩陣 B B B來記錄求得 C [ i , j ] C[i,j] C[i,j]的過程：

B [ i , j ] = { 0 A [ i ] = B [ i ] 1 A [ i ] ≠ B [ i ] , C [ i − 1 , j ] > C [ i , j − 1 ] 2 A [ i ] ≠ B [ i ] , C [ i − 1 , j ] < C [ i , j − 1 ] 3 A [ i ] ≠ B [ i ] , C [ i − 1 , j ] = C [ i , j − 1 ] B[i,j]=\left\{ \begin{array}{lcl} 0 & &{A[i]=B[i]}\\ 1 & &{A[i]\neq B[i],C[i-1,j]>C[i,j-1]}\\ 2 & &{A[i]\neq B[i],C[i-1,j]<C[i,j-1]}\\ 3 & &{A[i]\neq B[i],C[i-1,j]=C[i,j-1]} \end{array} \right. B[i,j]=⎩⎪⎪⎨⎪⎪⎧​0123​​A[i]=B[i]A[i]​=B[i],C[i−1,j]>C[i,j−1]A[i]​=B[i],C[i−1,j]<C[i,j−1]A[i]​=B[i],C[i−1,j]=C[i,j−1]​

在求得最長公共子序列 C C C以及輔助矩陣 B B B之後，即可使用回溯法來得到所有的最長公共子序列。

3 實作代碼

3.1 LCS.h 

# ifndef _LCS_H
# define _LCS_H
# include <vector>
using namespace std;

/**
 *  序列類
 */
class Seq{
public:
    //資料指針
    int* data=nullptr;
    //資料長度
    int len=0;
    Seq(int* data,int len){
        this->data=data;
        this->len=len;
    }
};

// LCS類
class LCS{
private:
    //最長公共子序列長度矩陣
    int** C=nullptr;
    //輔助矩陣
    int** src=nullptr;

    //使用動态規劃方法計算C矩陣和src矩陣
    void writeTable(Seq* seq1,Seq* seq2);
    //使用回溯方法來得到所有的最長公共子序列
    void createSubSeq(Seq* seq1,vector<int>lcs , int i,int j,int MaxLen,vector<vector<int>>&LcsSet);

public:

    /**
     * 對外的接口
     * 輸入是兩個序列
     * 輸出是0-n條最長公共子序列
     */ 
    vector<vector<int>> getLCS(Seq* seq1,Seq* seq2);

};
#endif

3.2 LCS.cpp 

# include "LCS.h"
#include <cstdio>
# include <vector>
#include <algorithm>

using namespace std;


/**
 * 動态規劃法求最長公共子序列長度矩陣C以及輔助矩陣
 * 輸入是兩個序列
*/
void LCS::writeTable(Seq* seq1,Seq* seq2){
    // 此處有一個小技巧，擴充了一行一列，由于後面會出現C[i-1][j] C[i][j-1]，擴充一行一列可以避免下标出現-1
    int len1=seq1->len+1;
    int len2=seq2->len+1;
    //配置設定記憶體
    C=new int*[len1];
    src = new int*[len1];
    for(int i=0;i<len1;i++){
        C[i] = new int[len2];
        src[i] = new int[len2];
    }
    //計算C矩陣和輔助矩陣src
    for(int i=0;i<len1;i++){
        for(int j=0;j<len2;j++){
            if(i==0||j==0){ //自行擴充的一行一列，無意義
                C[i][j]=0;   //無實際用處
                src[i][j]=0; //無實際用處
            }else if(seq1->data[i-1]==seq2->data[j-1]){ 
                C[i][j]=C[i-1][j-1]+1;    
                src[i][j]=0; 
            }else{ 
                if(C[i-1][j]>C[i][j-1]){ 
                    C[i][j]=C[i-1][j];
                    src[i][j]=1;
                }else if(C[i-1][j]<C[i][j-1]){
                    C[i][j]=C[i][j-1];
                    src[i][j]=2;
                }else{
                    C[i][j]=C[i][j-1];
                    src[i][j]=3; 
                }
            }
        }
    }    
}

/**
 * 判斷子序列是否和已有的子序列重複
 * 輸入：LcsSet為已有的子序列集合，lcs為待加入的子序列
 * 輸出：若重複傳回true，否則false
 */
bool isRepeat(vector<vector<int>>LcsSet,vector<int>lcs){
    int flag=0;
    for(int i=0;i<LcsSet.size();i++){
        if(lcs.size()!=LcsSet.at(i).size()){
            return true;
        }
        for(int j=0;j<lcs.size();j++){
            if(lcs.at(j)!=LcsSet.at(i).at(j)){
               flag=1; 
            }
        }
        if(flag==0){
            return true;
        }
        flag=0;
    }
    return false;
}

/**
 * 使用回溯法來找出所有的最長公共子序列，此處使用輔助矩陣src完成，用到遞歸程式設計技巧
 * seq1是第一個序列，與C[i][j]的i對應；lcs是最長公共子序列；i,j是下标；Maxlen是最長公共子序列的長度；LcsSet是最長公共子序列的集合
 */
void LCS::createSubSeq(Seq* seq1,vector<int>lcs , int i,int j,int MaxLen,vector<vector<int>>&LcsSet){
    if(i==0||j==0){
        if(lcs.size()==MaxLen&&MaxLen>0){//已經回溯完成
            reverse(lcs.begin(),lcs.end()); //翻轉一下
            if(!isRepeat(LcsSet,lcs)){ //去重
                LcsSet.push_back(lcs); //加入
            }
        }
        return;
    }
    switch (src[i][j]){
    case 0://左上角
        lcs.push_back(seq1->data[i-1]); //seq1對應i
        createSubSeq(seq1,lcs,i-1,j-1,MaxLen,LcsSet);
        break;
    case 1://向上
        createSubSeq(seq1,lcs,i-1,j,MaxLen,LcsSet);
        break;
    case 2://左
        createSubSeq(seq1,lcs,i,j-1,MaxLen,LcsSet);
        break;
    case 3://左右皆可
        createSubSeq(seq1,lcs,i-1,j,MaxLen,LcsSet);
        createSubSeq(seq1,lcs,i,j-1,MaxLen,LcsSet);
        break;
    default:
        break;
    }
}


vector<vector<int>> LCS::getLCS(Seq* seq1,Seq* seq2){
    if(seq1->len==0||seq2->len==0||seq1->data==nullptr||seq2->data==nullptr){
        return vector<vector<int>>();
    }
    writeTable(seq1,seq2);

    vector<int> lcs;
    vector<vector<int>> LcsSet;
    createSubSeq(seq1,lcs,seq1->len,seq2->len,C[seq1->len][seq2->len],LcsSet);

    return LcsSet;
}

3.3 test.cpp 

#include "LCS.h"
#include <cstdio>
#include <vector>
using namespace std;


void test1(){
    LCS* lcs = new LCS();
    
    Seq seq1 = Seq(new int[7]{1,8,2,3,7,8,2},7);
    Seq seq2 = Seq(new int[9]{3,5,7,4,8,6,7,8,2},9);
    vector<vector<int>> LcsSet= lcs->getLCS(&seq1,&seq2);
    printf("nums of lcs : %d\n",LcsSet.size());
    for(int i=0;i<LcsSet.size();i++){
        for(int j=0;j<LcsSet.at(i).size();j++){
            printf("%d ",LcsSet.at(i).at(j));
        }
        printf("\n");
    }
}

int main(){
    test1();
    return 0;
}

3.4 Makefile 

FLAG= -std=c++11 
LIBS= 

act:test.o  LCS.o
	g++ -o act test.o LCS.o $(FLAG) $(LIBS)


test.o:test.cpp 
	g++ -c test.cpp  $(FLAG)

LCS.o:LCS.cpp LCS.h
	g++ -c LCS.cpp $(FLAG)

4 測試結果

動态規劃解最長公共子序列問題1 最長公共子序列問題概述2 動态規劃求解最長公共子序列問題3 實作代碼4 測試結果
算法 c++ 1024程式員節 最長公共子序列 LCS
上一篇: 還要談談Equals和GetHashcode
下一篇: Spring中用@DependsOn注解控制Bean的建立順序

繼續閱讀