10.2.3 算法应用案例
在问题提出之前,本节先介绍几个基本概念:
(1)子序列的定义: 子序列就是在给定序列中去掉零个或者多个元素的序列。
例如:给定一个序列 X={x
1
,x
2
,……,x
m
},另外一个序列 Z={z
1
、z
2
、……,z
k
},如
果存在 X 的一个严格递增小标序列<i
1
,i
2
……,i
k
>,使得对所有 j=1,2,……k,有 x
ij
= z
j
,
则 Z 是 X 的子序列。
假定:Z={B,C,D,B}是 X={A,B,C,B,D,A,B}的一个子序列,相应的小标为<2,3,5,7>从定
义可以看出子序列直接的元素不一定是相邻的。
(2)公共子序列:给定两个序列 X 和 Y,如果 Z 既是 X 的一个子序列又是 Y 的一个
子序列,则称序列 Z 是 X 和 Y 的公共子序列。
例如:X={A,B,C,B,D,A,B},Y={B,D,C,A,B,A},则序列{B,C,A}是 X 和 Y 的一个公共子
序列,但不是最长公共子序列。因为它的长度等于 3,而子序列{B,C,A,B}其长度等 4,序列
{B,C,B,A}也是是 X 和 Y 的公共子序列。
案例:最长公共子序列 LCS(Longest Common Subsequence),问题描述:给定两个
序列 X={x
1
,x
2
,……,x
m
}和 Y={y
1
,y
2
,……y
n
},求出 X 和 Y 的最大长度公共子序列。
案例分析:
如何找出一个最长公共子序列?如果序列比较短,可以采用蛮力法枚举出 X 的所有子
序列(假定它的长度为 M,则有 2
M
个子序列),然后检查是否是 Y 的子序列(假定其长度为
N,则有 2
N
个子序列),并记录所发现的最长子序列。如果序列比较长,这种方法需要指数级
0(2
(M+N)
)的时间,是难以满足需求的。
能否采用动态规划算法求解问题,需要知道求解问题是否具有最优子结构解,对于该
案例,看看下面的分析:
X
i
=﹤x
1
,,x
i
﹥即 X 序列的前 i 个字符 (1≤i≤m)(前缀)
Y
j
=﹤y
1
,,y
j
﹥即 Y 序列的前 j 个字符 (1≤j≤n)(前缀)
假定 Z=﹤z
1
,…,z
k
﹥∈LCS(X , Y)。
(1)若
(最后一个字符相同),则可用反证法证明:该字符必是 X 与 Y 的任
一最长公共子序列 Z(设长度为 k)的最后一个字符,即有
且有 Z
k-1
∈LCS(X
m-
1
, Y
n-1
),即 Z 的前缀 Z
k-1
是 X
m-1
与 Y
n-1
的最长公共子序列。此时,问题转换成求解 X
m-1
与 Y
n-
1
的 LCS(X
m-1
, Y
n-1
); 而 LCS(X , Y)的长度,它等于 LCS(X
m-1
, Y
n-1
)的长度加 1;
(2)若
,则亦不难用反证法证明:要么 Z∈LCS(X
m-1
, Y),要么 Z∈LCS(X ,
Y
n-1
)。由于
与
其中至少有一个必成立,若
则有 Z∈LCS(X
m-1
,
Y),类似的,若
则有 Z∈LCS(X , Y
n-1
)。此时,问题就转换成求 X
m-1
与 Y 的 LCS 及
X 与 Y
n-1
的 LCS。LCS(X , Y)的长度为:max{ LCS(X
m-1
, Y)的长度, LCS(X , Y
n-1
)的长度}。
由于上述当
的情况中,求 LCS(X
m-1
, Y)的长度与 LCS(X , Y
n-1
)的长度,这
两个问题是不相互独立的,两者都需要求 LCS(X
m-1
,Y
n-1
)的长度。另外两个序列的 LCS 中包
含了两个序列的前缀的 LCS,故此问题具有最优子结构性质,可以考虑用动态规划法。
下面从三个步骤进行求解:
(1)LCS 的最优子结构定义:设 X={x
1
,x
2
,……,x
m
}和 Y={y
1
,y
2
,……,y
n
}为两
个序列,并设 Z={z
1
、z
2
、……,z
k
}为 X 和 Y 的任意一个 LCS,则必须满足如下条件: