最长公共子序列问题

  • 动态规划-最长公共子序列

  • 资料来源:

    算法导论

  • 更新

    1
    2021.03.23 初始

导语

这是重启算法的第一篇,希望能缓慢但是长久的完成.

这次重启的几个规划

  • 希望能够尽量简洁的描述证明过程.
  • 都是以问题为中心,描述算法的实现,而不是反过来.

问题定义

子序列:

给定一个序列 X[1..m]X[1..m],另一个序列 z 满足两个条件时称 Z 为 X 的子序列.

  • zjZ\forall z_j \in Z,有 xi=zjx_i = z_j.所有 Z 的元素都属于 X
  • zj1=xi1,zj2=xi2z_{j1} = x_{i1},z_{j2} = x_{i2} , i1<i2i1 < i2 时,j1<j2j1 < j2.Z 的所有元素在 X 的位置的前后顺序依旧保持不变.

给定两个序列 X Y,如果 Z 是 X 和 Y 共同的子序列,称 Z 是 XY 的公共子序列.

最长公共子序列: 给定两个序列 X[1..m]X[1..m]Y[1..n]Y[1..n] , 求 XY 最长的公共子序列.

最长公共子序列简称 LCS.

ps:

  • 求公共子序列并非连续公共子序列,两者区别很大.
  • 最长公共子序列的结果可能不唯一,但是其长度是相同的.

暴力搜索

暴力搜索的思路是将属于 X 的所有子序列都到 Y 中搜索一遍,最后确认 LCS.

子序列数量: 对于 X[1..m]X[1..m] 中的每一个元素,都有两个选择,出现或者不出现在子序列中,因此最后子序列的数量是 2m2^m 个,当然可能有重复的子序列.

每次到 Y[1..n]Y[1..n] 中搜索的成本是 O(n)O(n)

所以最后总的时间复杂度是 O(n2m)O(n*2^m),指数级别直接 boom.

动态规划

定义

先规定一些定义.

  • Z\mid Z \mid: 代表序列 Z 的长度.
  • LCS(X[1..m],Y[1..n])LCS(X[1..m],Y[1..n]): 代表 X Y 的公共子序列.
  • X+YX + Y: 代表将两个序列或元素合并为新的序列.

则可以得出以下定义

  • C[i,j]=LCS(X[1..i],Y[1..j])C[i,j] = | LCS(X[1..i],Y[1..j]) |: 代表了 XY 最长公共子序列的长度.
  • Z[1..k]=LCS(X[1..m],Y[1..n])Z[1..k] = LCS(X[1..m],Y[1..n]): Z 是 XY 的最长公共子序列之一.

最长公共子序列的特征

直观上想,所有非暴力的解法都是寻得了问题的某些特征,利用这些特征省去了大量计算过程.

动态规划与分治法相同,都是不断将问题分解,最后串起子问题得到原问题的解.

对于 C[i,j]C[i,j] 我们可以得出以下结论 ^9bfe6c

C[i,j]={C[i1,j1]X[i]=Y[j](1)Max{C[i1,j],C[i,j1]}X[i]Y[j](2)C[i,j] = \begin{cases} C[i-1,j-1] & X[i] = Y[j] & (1)\\ Max\{C[i-1,j],C[i,j-1]\} & X[i] \neq Y[j] & (2) \end{cases}

证明

  1. X[i]=Y[j]X[i] = Y[j] 时.
    1. 假设 W=LCS(X[1..i1],Y[1..j1])\exists W = LCS(X[1..i-1],Y[1..j-1]),且 W>k1|W| > k-1.
    2. W+X[i]W + X[i] (or Y[j]Y[j]),将会是 XY 的公共子序列,且 W+X[i]>k|W + X[i]| > k.
    3. 与 Z 是最长公共子序列,长度为 k 矛盾.因此原命题成立.
    4. 这实际上是剪贴法,反例证明.
  2. X[i]Y[j]X[i] \neq Y[j]
    1. 这里只说明 Z[k]X[i]Z[k] \neq X[i] 情况,另一种情况类型相似.
    2. 如果 Z[k]X[i]Z[k] \neq X[i] 则 Z 一定是 X[1..i1]X[1..i-1] 和 Y 的最长公共子序列.
    3. 假设存在 W 是 X[1..i1]X[1..i-1] 和 Y 的 LCS 且 W>Z|W| > |Z|,则 W 也将是 X Y 的 LCS
    4. 这与前提条件不符,假设不成立.

这里证明了递推公式,现在如果直接进行递归计算呢?

递归

直接递归

我们假设 m=7 n=6,查看直接递归的递归树(部分).

graph TD;
1((76)) --> 2((66))
1((76)) --> 3((75))
2((66)) --> 4((56))
2((66)) --> 5((65))
3((75)) --> 6((65))
3((75)) --> 7((74))
4((56)) --> 8((46))
4((56)) --> 9((55))
7((74)) --> 14((64))
7((75)) --> 15((73))
subgraph 重复1
5((65)) --> 10((55))
5((65)) --> 11((64))
end
subgraph 重复2
6((65)) --> 12((55))
6((65)) --> 13((64))
end

递归树特点

  • 二叉树,非满.
  • 树的高度是 h = m + n
  • 有许多子问题被重复计算了.

m n 很大时,直接递归的时间复杂度是 O(2m+n)O(2^{m+n}) --> BOOM !

记录子问题结果递归

大量子问题被重复计算了,可以维持一个空间记录已求解子问题答案,直接直接查询.

对于 LCS 而言,子问题的解空间是 mnm*n.

因此记录+递归的复杂度

  • 时间复杂度 O(mn)O(mn)
  • 空间复杂度 O(mn)O(mn)

自底向上

与递归不同,还有一种自底向上的真动态规划.

LCS 子问题的解空间是 Θ(mn)\Theta(m*n).因此参考递归的逆过程,直接自底向上,从计算最小的子问题开始,直到最终计算出原问题.

下图展示了这一过程

  • 一行一行的计算子问题,直到完成求解

![[Pasted image 20210328202613.png]]

时间复杂度

  • 每个表项的计算是 Θ(1)\Theta (1)
  • 最终整个计算过程是有 mnm*n
  • 最终的时间复杂度是 Θmn\Theta m*n
  • 空间复杂度是 Θ(mn)\Theta (m*n)

构建 LCS

上面计算的问题结果是 LCS 的长度,而不是 LCS 本身.因此求解原问题还差一步.

其实构建 LCS 的步骤并不复杂

  • 记录-递归,需要记录每次有效选择.
  • 自底向上,需要记录每次有效选择.上图展示的就是自底向上构建 LCS 的过程.
  • LCS 不唯一…

算法改进

主要是空间上的改进

回到自底向上计算过程,实际参与计算是只是 mnm*n 表的两行,因此只需要保存这两行即可.

当然这样要构建 LCS,就不能事后构建了,只能运行算法同时,记录选择的结果.

看 m or n 那个小,作为行运算.