當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

动态规划之最长公共子序列(LCS)

發布時間：2023/12/20 编程问答 39 豆豆

生活随笔收集整理的這篇文章主要介紹了动态规划之最长公共子序列(LCS) 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

最長公共子序列(LCS,Longest Common Subsequence)。其定義是，一個序列 S ，如果分別是兩個或多個已知序列的子序列，且是所有符合此條件序列中最長的，則 S 稱為已知序列的最長公共子序列。而最長公共子串(要求連續)和最長公共子序列是不同的。

設X(m)={x(1), x(2), x(3),....,x(m)} 和 Y(n)={y(1), y(2), y(3),....,y(n)}的最長公共子序列Z(k)={z(1), z(2),z(3),....,z(k)}

首先，將原問題分解為子問題，得出一個已知的結論：當m或n等于0時，k等于0，即公共子序列長度為0

當m和n都不等于0時，此時分為三種情況：

(1) x(m) == y(n) ，此時z(k) =?x(m) = y(n)，該元素屬于當前最長公共子序列的最后一個元素。此時Z(k-1)={ X(m-1)與Y(n-1)的最長公共子序列 }?

(2) x(m) ！= y(n) ，且z(k) ！=?x(m)，此時Z={ X(m-1)與Y(n)的最長公共子序列 }

(3) x(m) ！= y(n) ，且z(k) ！=?y(n)，此時Z={ X(m)與Y(n-1)的最長公共子序列 }?

其中X(m-1)={x(1), x(2), x(3),....,x(m-1)} ， Y(n-1)={y(1), y(2), y(3),....,y(n-1)}，Z(k-1)={z(1), z(2),z(3),....,z(k-1)}

上面三個步驟，每個步驟都是根據當前序列的狀態，將問題轉化為已知解的子問題(最初的已知解的子問題是當m==0或n==0時)，從而求出當前問題的解。

由此便得出了該問題的狀態轉移方程，數學描述如下：

現有兩個序列X={x₁,x₂,x_3，...x_i}，Y={y₁,y₂,y_3，....，y_i}，

設一個C[i,j]: 保存X_i與Y_j的LCS的長度

最后，該算法的python實現：

1 # 最長公共子序列問題 2 __author__ = 'ice' 3 4 5 # arr_x,arr_y [0 ~ length-1] 6 # subarr_len [0,1~x_length][0,1~y_length] 7 # flag [0 ~ x_length-1][0 ~ y_length] 8 9 10 def lcs_length(arr_x, arr_y): 11 x_length = len(arr_x) 12 y_length = len(arr_y) 13 subarr_len = [[0 for j in range(y_length + 1)] for i in range(x_length + 1)] 14 flag = [[0 for j in range(y_length)] for i in range(x_length)] 15 for i in range(1, x_length + 1): 16 for j in range(1, y_length + 1): 17 if arr_x[i - 1] == arr_y[j - 1]: 18 subarr_len[i][j] = subarr_len[i - 1][j - 1] + 1 19 flag[i - 1][j - 1] = 1 20 elif subarr_len[i - 1][j] >= subarr_len[i][j - 1]: 21 subarr_len[i][j] = subarr_len[i - 1][j] 22 flag[i - 1][j - 1] = 2 23 else: 24 subarr_len[i][j] = subarr_len[i][j - 1] 25 flag[i - 1][j - 1] = 3 26 return {'subarr_length': subarr_len[x_length][y_length], 'flag': flag} 27 28 29 def lcs(arr_x, x_i, y_j, flag, result): 30 if x_i < 0 or y_j < 0: 31 return 32 if flag[x_i][y_j] == 1: 33 lcs(arr_x, x_i - 1, y_j - 1, flag, result) 34 result.append(arr_x[x_i]) 35 elif flag[x_i][y_j] == 2: 36 lcs(arr_x, x_i - 1, y_j, flag, result) 37 elif flag[x_i][y_j] == 3: 38 lcs(arr_x, x_i, y_j - 1, flag, result) 39 40 41 array_x = ['a', 'b', 'c', 'b', 'd', 'a', 'b'] 42 array_y = ['b', 'd', 'c', 'a', 'b', 'a'] 43 longest_common_subsequence = [] 44 lcs_info = lcs_length(array_x, array_y) 45 lcs(array_x, len(array_x) - 1, len(array_y) - 1, lcs_info['flag'], longest_common_subsequence) 46 print(longest_common_subsequence)

轉載于:https://www.cnblogs.com/z941030/p/4910035.html

總結

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

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