一、實驗目的

了解最長公共子序列問題求解的基本思想

掌握實現最長公共子序列的實驗算法

二、實驗原理

最長公共子序列（LCS）是一個在一個序列集合中（通常為兩個序列）用來查找所有序列中最長子序列的問題。一個數列?，如果分別是兩個或多個已知數列的子序列，且是所有符合此條件序列中最長的，則稱為已知序列的最長公共子序列。

比如序列 X 為 ABCBDAB ，序列 Y 為 BDCABA，則其公共最長子序列之一為 BCBA（可能不唯一）。

2-1實驗原理圖

三、設計思路

若設A= (a0, a1, . am-1)，B= (b0， b1， … bn-1) ，設Z= (z0, z1, .，zk-1) 為它們的最長公共子序列。不難證明有以下性質:

3-1性質圖

用更簡單的方法來理解，假設有兩個字符串A、B，分別有兩個指針指向這兩個字符串，設這兩個指針分別為i和j，如今我們設定一個狀態方程f(i,j)，表示i指向字符串A的某個字符，而j指向字符串B的某個字符的情況。那么此時就會有兩種情況：

①兩個指針所指向的字符相同：那么兩個指針繼續向右移動，此時的狀態為f(i+1,j+1)+1;

②兩個指針所指向的字符不相同：那么此時的狀態又分為兩種分別為f(i+1,j)和f(i,j+1)

?

因此我們定義一個二維動態規劃數組dp，其中dp[i][j]為子序列A和B的最長公共子序列的長度。

那么狀態轉移方程如下：

dp[i][j]=0 (當i=0或者j=0即邊界條件的情況下）

dp[i][j]=dp[i-1][j-1]+1 (當a[i-1]=b[i-1])

dp[i][j]=max(dp[i][j-1],dp[i-1][j]) （當a[i-1]!=b[j-1])

那么dp[m][n]就是我們要求的最終結果

?

?

四、代碼實現

#include <iostream>

#include <string.h>

#include <vector>

#include <string>

using namespace std;

#define max(x,y) ((x)>(y)?(x):(y))

#define MAX 51????????????????????

?

int m,n;

string a,b;

int dp[MAX][MAX];?????????????????

vector<char> subs;???????????????????

void LCSlength()??????????????

{

?? int i,j;

?? for (i=0;i<=m;i++)????????????????

?????? dp[i][0]=0;

?? for (j=0;j<=n;j++)?????????????

?????? dp[0][j]=0;

?? for (i=1;i<=m;i++)

?????? for (j=1;j<=n;j++)?????????????

?????? {?? if (a[i-1]==b[j-1])?????

????????????? dp[i][j]=dp[i-1][j-1]+1;

????????? else????????????????????

????????????? dp[i][j]=max(dp[i][j-1],dp[i-1][j]);

?

?????? }

}

void Buildsubs()??????????????

{

?? int k=dp[m][n];????????????

?? int i=m;

?? int j=n;

?? while (k>0)????????????????????

?????? if (dp[i][j]==dp[i-1][j])

????????? i--;

?????? else if (dp[i][j]==dp[i][j-1])

????????? j--;

?????? else

?????? {

????????? subs.push_back(a[i-1]);?

????????? i--; j--; k--;

?????? }

}

int main()

{

?? a="abcbdb";

?? b="acbbabdbb";

?? m=a.length();???????

?? n=b.length();????

?? LCSlength();?????

?? Buildsubs();????????

?? cout << "求解結果" << endl;

?? cout << "??? a: " << a << endl;

?? cout << "??? b: " << b << endl;

?? cout << "??? 最長公共子序列: ";

?? vector<char>::reverse_iterator rit;

?? for (rit=subs.rbegin();rit!=subs.rend();++rit)

?????? cout << *rit;

?? cout << endl;

?? cout << "??? 長度: " << dp[m][n] << endl;

?? return 0;

}

?

?

?

五、運行結果和實驗小結

1.運行結果

5-1運行結果

2.實驗小結

用vector字符向量subs存放一個LCS，k=dp[m][n](LCS的字符個數），從k到1循環求出subs中的k個字符：

①如果dp[i][j]=dp[i-1][j]（上方），說明a[i-1]或者b[j-1]不是LCS中的字符。→→ i-1；

②如果dp[i][j]=dp[i][j-1]（左方），說明a[i-1]或者b[j-1]不是LCS中的字符。→→j-1

③其他情況，說明a[i-1]或者b[j-1]是LCS中的字符。

→→i-1,j-1,k-1表示求的字符減少一個

六、結論

本次實驗讓我們小組操作的是求最長公共子序列。這個實驗是一個十分實用的實驗。它可以描述成兩段文字之間的“相似度”，即它們雷同程度，從而辨別抄襲。此次實驗從側面看也是考察我們對動態規劃的應用。動態規劃通過拆分問題，將問題拆分成許多的子問題，定義問題狀態和狀態之間的關系（即狀態轉移方程或遞推公式），使得問題能夠以遞推（或者說分治）的方式去解決。實驗之前，對動態規劃法還是有些疑惑，結合了課本上利用動態規劃法求解最長公共子序列的基本步驟和例子之后，基本掌握了動態規劃法的原理。

總結

以上是生活随笔為你收集整理的最长公共子序列的求解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。