资讯专栏INFORMATION COLUMN

动态规划法(十)最长公共子序列(LCS)问题

Ashin / 1731人阅读

摘要:最长公共子序列问题指的是求解两个序列和的长度最长的公共子序列。当然,可以看出,问题容易出现重叠子问题,这时候,就需要用动态规划法来解决。

问题介绍

  给定一个序列$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的伪代码如下:

</>复制代码

  1. LCS-LENGTH(X, Y):
  2. m = X.length
  3. n = Y.length
  4. let b[1...m, 1...n] and c[0...m, 0...n] be new table
  5. for i = 1 to m
  6. c[i, 0] = 0
  7. for j = 1 to n
  8. c[0, j] = 0
  9. for i = 1 to m
  10. for j = 1 to n
  11. if x[i] == y[j]
  12. c[i,j] = c[i-1, j-1]+1
  13. b[i,j] = "diag"
  14. elseif c[i-1, j] >= c[i, j-1]
  15. c[i,j] = c[i-1, j]
  16. b[i,j] = "up"
  17. else
  18. c[i,j] = c[i, j-1]
  19. b[i,j] = "left"
  20. 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如下:

</>复制代码

  1. PRINT-LCS(b, X, i, j):
  2. if i == 0 or j == 0
  3. return
  4. if b[i,j] == "diag"
  5. PRINT-LCS(b, X, i-1, j-1)
  6. print x[i]
  7. elseif b[i,j] == "up":
  8. PRINT-LCS(b, X, i-1, j)
  9. else
  10. PRINT-LCS(b, X, i, j-1)
程序实现

  有了以上对LCS问题的算法分析,我们不难写出具体的程序来实现它。下面将会给出Python代码和Java代码,供读者参考。
  完整的Python代码如下:

</>复制代码

  1. import numpy as np
  2. # using dynamic programming to solve LCS problem
  3. # parameters: X,Y -> list
  4. def LCS_LENGTH(X, Y):
  5. m = len(X) # length of X
  6. n = len(Y) # length of Y
  7. # create two tables, b for directions, c for solution of sub-problem
  8. b = np.array([[None]*(n+1)]*(m+1))
  9. c = np.array([[0]*(n+1)]*(m+1))
  10. # use DP to sole LCS problem
  11. for i in range(1, m+1):
  12. for j in range(1, n+1):
  13. if X[i-1] == Y[j-1]:
  14. c[i,j] = c[i-1,j-1]+1
  15. b[i,j] = "diag"
  16. elif c[i-1,j] >= c[i, j-1]:
  17. c[i,j] = c[i-1,j]
  18. b[i,j] = "up"
  19. else:
  20. c[i,j] = c[i,j-1]
  21. b[i,j] = "left"
  22. #print(b)
  23. #print(c)
  24. return b,c
  25. # print longest common subsequence of X and Y
  26. def print_LCS(b, X, i, j):
  27. if i == 0 or j == 0:
  28. return None
  29. if b[i,j] == "diag":
  30. print_LCS(b, X, i-1, j-1)
  31. print(X[i-1], end=" ")
  32. elif b[i,j] == "up":
  33. print_LCS(b, X, i-1, j)
  34. else:
  35. print_LCS(b, X, i, j-1)
  36. X = "conservatives"
  37. Y = "breather"
  38. b,c = LCS_LENGTH(X,Y)
  39. print_LCS(b, X, len(X), len(Y))

输出结果如下:

</>复制代码

  1. e a t e

  完整的Java代码如下:

</>复制代码

  1. package DP_example;
  2. import java.util.Arrays;
  3. import java.util.List;
  4. public class LCS {
  5. // 主函数
  6. public static void main(String[] args) {
  7. // 两个序列X和Y
  8. List X = Arrays.asList("A","B","C","B","D","A","B");
  9. List Y = Arrays.asList("B","D","C","A","B","A");
  10. int m = X.size(); //X的长度
  11. int n = Y.size(); // Y的长度
  12. String[][] b = LCS_length(X, Y); //获取维护表b的值
  13. print_LCS(b, X, m, n); // 输出LCS
  14. }
  15. /*
  16. 函数LCS_length:获取维护表b的值
  17. 传入参数: 两个序列X和Y
  18. 返回值: 维护表b
  19. */
  20. public static String[][] LCS_length(List X, List Y){
  21. int m = X.size(); //X的长度
  22. int n = Y.size(); // Y的长度
  23. int[][] c = new int[m+1][n+1];
  24. String[][] b = new String[m+1][n+1];
  25. // 对表b和表c进行初始化
  26. for(int i=1; i= c[i][j-1]){
  27. c[i][j] = c[i-1][j];
  28. b[i][j] = "up";
  29. }
  30. else{
  31. c[i][j] = c[i][j-1];
  32. b[i][j] = "left";
  33. }
  34. }
  35. }
  36. return b;
  37. }
  38. // 输出最长公共子序列
  39. public static int print_LCS(String[][] b, List X, int i, int j){
  40. if(i == 0 || j == 0)
  41. return 0;
  42. if(b[i][j].equals("diag")){
  43. print_LCS(b, X, i-1, j-1);
  44. System.out.print(X.get(i-1)+" ");
  45. }
  46. else if(b[i][j].equals("up"))
  47. print_LCS(b, X, i-1, j);
  48. else
  49. print_LCS(b, X, i, j-1);
  50. return 1;
  51. }
  52. }

输出结果如下:

</>复制代码

  1. B C B A
参考文献

算法导论(第三版) 机械工业出版社

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

注意:本人现已开通两个微信公众号: 因为Python(微信号为:python_math)以及轻松学会Python爬虫(微信号为:easy_web_scrape), 欢迎大家关注哦~~

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/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元查看
<