一、问题定义
1.1 子序列
子序列是给定序列中在任意位置去掉任意多个字符后得到的结果。例如:
给定序列 X X X:
X : A B C B D A B X:ABCBDAB X:ABCBDAB
X X X的子序列:
X 1 : A B C B D A B X_1:ABCBDAB X1:ABCBDAB
X 2 : A B C B X_2:ABCB X2:ABCB
X 3 : A C B B X_3:ACBB X3:ACBB
1.2 公共子序列
给定两个序列 X X X和 Y Y Y:
X : A B C B D A B X:ABCBDAB X:ABCBDAB
Y : B D C A B A Y:BDCABA Y:BDCABA
公共子序列示例:
X 1 = Y 1 = C A X_1=Y_1=CA X1=Y1=CA
X 2 = Y 2 = A B A X_2=Y_2=ABA X2=Y2=ABA
X 3 = Y 3 = B C A B X_3=Y_3=BCAB X3=Y3=BCAB
1.3 问题形式化定义
最长公共子序列问题:
输入:
\quad 序列 X = < x 1 , x 2 , . . . , x n > X=<x_1,x_2,...,x_n> X=<x1,x2,...,xn>和序列 Y = < y 1 , y 2 , . . . , y m > Y=<y_1,y_2,...,y_m> Y=<y1,y2,...,ym>
输出:
\quad 求解一个公共子序列 Z = < z 1 , z 2 , . . . , z l > Z=<z_1,z_2,...,z_l> Z=<z1,z2,...,zl>
\quad \quad \quad 优化目标: m a x ∣ Z ∣ max|Z| max∣Z∣
\quad \quad \quad 约束条件: < z 1 , z 2 , . . . , z l > = < x i 1 , x i 2 , . . . , x l 1 > = < y j 1 , y j 2 , . . . , y j l > <z_1,z_2,...,z_l>=<x_{i_1},x_{i_2},...,x_{l_1}>=<y_{j_1},y_{j_2},...,y _{j_l}> <z1,z2,...,zl>=<xi1,xi2,...,xl1>=<yj1,yj2,...,yjl>,其中 1 ≤ i 1 < i 2 < . . . < i l ≤ n ; 1 ≤ j 1 < j 2 < . . . < j l ≤ m 1\leq i_1< i_2<...<i_l\leq n;1\leq j_1<j_2<...<j_l\leq m 1≤i1<i2<...<il≤n;1≤j1<j2<...<jl≤m
二、求解策略
给定两个序列 X X X和 Y Y Y:
X : A B C B D A B X:ABCBDAB X:ABCBDAB
Y : B D C A B A Y:BDCABA Y:BDCABA
其最长公共子序列 Z = B D A B Z=BDAB Z=BDAB,观察可以发现,其后3位为长度为3的最长公共子序列,其后2位为长度为2的最长公共子序列,最后一位为长度为一的最长公共子序列。这便启示我们可能存在最优子结构和重叠子问题,可以采用动态规划进行求解。
2.1 分析问题结构
形式化给出问题表示:
- C [ i , j ] C[i,j] C[i,j]: X [ 1.. i ] X[1..i] X[1..i]和 Y [ 1.. j ] Y[1..j] Y[1..j]的最长公共子序列长度
明确原始问题:
- C [ n , m ] C[n,m] C[n,m]: X [ 1.. n ] X[1..n] X[1..n]和 Y [ 1.. m ] Y[1..m] Y[1..m]的最长公共子序列长度
2.2 建立递推关系
对于给定序列:
对于末尾来说,有两种情况:
① x i = y j x_i=y_j xi=yj
此时,
C
[
i
,
j
]
=
m
a
x
{
C
[
i
−
1
,
j
−
1
]
+
1
①
C
[
i
−
1
,
j
]
②
C
[
i
,
j
−
1
]
③
C[i,j]=max\left\{\begin{matrix} C[i-1,j-1]+1 & ①\\ C[i-1,j] & ②\\ C[i,j-1] &③ \end{matrix}\right.
C[i,j]=max⎩
⎨
⎧C[i−1,j−1]+1C[i−1,j]C[i,j−1]①②③
但是,
①
≥
m
a
x
{
②,③
}
{①\ge max\left \{ ②,③ \right \} }
①≥max{②,③},因此,
C
[
i
,
j
]
=
C
[
i
−
1
,
j
−
1
]
+
1
C[i,j]=C[i-1,j-1]+1
C[i,j]=C[i−1,j−1]+1
② x i ≠ y j x_i \ne y_j xi=yj
此时,
C
[
i
,
j
]
=
m
a
x
{
C
[
i
−
1
,
j
]
①
C
[
i
,
j
−
1
]
②
C[i,j]=max\left\{\begin{matrix} C[i-1,j] & ①\\ C[i,j-1] & ② \end{matrix}\right.
C[i,j]=max{C[i−1,j]C[i,j−1]①②
综上所述,得到递推关系式:
C
[
i
,
j
]
=
{
C
[
i
−
1
,
j
−
1
]
+
1
x
i
=
y
j
m
a
x
{
C
[
i
−
1
,
j
]
,
C
[
i
,
j
−
1
]
}
x
i
≠
y
j
C[i,j]=\left\{\begin{matrix} C[i-1,j-1]+1 & x_i=y_j\\ max\left\{ C[i-1,j],\\ C[i,j-1] \right\} & x_i\ne y_j\\ \end{matrix}\right.
C[i,j]={C[i−1,j−1]+1max{C[i−1,j],C[i,j−1]}xi=yjxi=yj
2.3 自底向上计算
(1)初始化
当其中一段序列长度为0时,最长公共子序列长度为0,即: C [ i , 0 ] = C [ 0 , j ] = 0 C[i,0]=C[0,j]=0 C[i,0]=C[0,j]=0
(2)依照递推公式计算
2.4 追踪最优方案
构造追踪数组
r
e
c
[
1..
n
]
rec[1..n]
rec[1..n],用来记录子问题的来源:
r
e
c
[
i
,
j
]
=
{
L
U
i
f
C
[
i
,
j
]
=
C
[
i
−
1
,
j
−
1
]
+
1
U
i
f
C
[
i
,
j
]
=
C
[
i
−
1
,
j
]
L
i
f
C
[
i
,
j
]
=
C
[
i
,
j
−
1
]
rec[i,j]=\left\{\begin{matrix} LU & if\quad C[i,j]=C[i-1,j-1]+1\\ U & if\quad C[i,j]=C[i-1,j]\\ L & if\quad C[i,j]=C[i,j-1] \end{matrix}\right.
rec[i,j]=⎩
⎨
⎧LUULifC[i,j]=C[i−1,j−1]+1ifC[i,j]=C[i−1,j]ifC[i,j]=C[i,j−1]
(使用
U
U
U代表来自上方,
L
L
L代表来自左方,
L
U
LU
LU代表来自左上角)
当左值和上值相等时,任取其一即可。
从右下角开始追踪,如果其值为 L L L,则向左移动1格, U U U则向上移动一格, L U LU LU向左上角移动一格。当且仅当 r e c [ i , j ] = L U rec[i,j]=LU rec[i,j]=LU时, X [ i ] = Y [ j ] X[i]=Y[j] X[i]=Y[j]为最长公共子序列中的一个字符,记录下来。如此寻找,直至抵达 r e c rec rec数组的边界。
2.5 算法实例
给定序列 X X X和 Y Y Y:
初始化辅助数组:
计算完毕:
追踪最优方案:
得到最长公共子序列 B C B A BCBA BCBA
三、算法分析
3.1 伪代码
文章来源:https://www.toymoban.com/news/detail-743439.html
3.2 时间复杂度
时间复杂度 O ( n m ) O(nm) O(nm)文章来源地址https://www.toymoban.com/news/detail-743439.html
到了这里,关于【动态规划】最长公共子序列——算法设计与分析的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!