当前位置:首页 >> 学科竞赛 >> 动态规划-最长公共子序列

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


动态规划-最长公共子序列
问题描述 一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说,若给定序列 X=<x1, x2,…, xm>,则另一序列 Z=<z1, z2,…, zk>是 X 的子序列是指存在一个严格递增的下标序列 <i1, i2,…, ik>,使 得对于所有 j=1,2,…,k 有 Xij =Zj 例如,序

列 Z=<B,C,D,B>是序列 X=<A,B,C,B,D,A,B>的子序列,相应的递增下标序列为<2,3,5,7>。 给定两个序列 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 的一个公共子序 列,序列<B, C, B, A>也是 X 和 Y 的一个公共子序列。而且,后者是 X 和 Y 的一个最长公共子序列,因为 X 和 Y 没有长度大于 4 的公共子序列。 最长公共子序列(LCS)问题:给定两个序列 X=<x1, x2, …, xm>和 Y=<y1, y2, … , yn>,要求找出 X 和 Y 的一个最长公共子序列。

动态规划算法可有效地解此问题。 下面我们按照动态规划算法设计的各个步骤来设计一个解此问题的有效算法。 1. 最长公共子序列的结构 解最长公共子序列问题时最容易想到的算法是穷举搜索法, 即对 X 的每一个子序列, 检查它是否也是 Y
的子序列,从而确定它是否为 X 和 Y 的公共子序列,并且在检查过程中选出最长的公共子序列。X 的所有子序 列都检查过后即可求出 X 和 Y 的最长公共子序列。 的一个子序列相应于下标序列{1, 2, …, m}的一个子序列, X 因此,X 共有 2 个不同子序列,从而穷举搜索法需要指数时间。 事实上,最长公共子序列问题也有最优子结构性质,因为我们有如下定理:
m

定理: LCS 的最优子结构性质
设序列 X=<x1, x2, …, xm>和 Y=<y1, y2, … , yn>的一个最长公共子序列 Z=<z1, z2,…, zk>,则: 若 xm=yn,则 zk=xm=yn 且 Zk-1 是 Xm-1 和 Yn-1 的最长公共子序列; 若 xm≠yn 且 zk≠xm ,则 Z 是 Xm-1 和 Y 的最长公共子序列; 若 xm≠yn 且 zk≠yn ,则 Z 是 X 和 Yn-1 的最长公共子序列。 其中 Xm-1=<x1, x2, …, xm-1>,Yn-1=<y1, y2, …, yn-1>,Zk-1=<z1, z2, …, zk-1>。

证明
用反证法。若 zk≠xm,则<z1, z2, …, zk ,xm >是 X 和 Y 的长度为 k 十 1 的公共子序列。这与 Z 是 X 和 Y 的一个最长公共子序列矛盾。因此,必有 zk=xm=yn。由此可知 Zk-1 是 Xm-1 和 Yn-1 的一个长度为 k-1 的公共子序列。若 Xm-1 和 Yn-1 有一个长度大于 k-1 的公共子序列 W,则将 xm 加在其尾部将产生 X 和 Y 的一 个长度大于 k 的公共子序列。此为矛盾。故 Zk-1 是 Xm-1 和 Yn-1 的一个最长公共子序列。 由于 zk≠xm,Z 是 Xm-1 和 Y 的一个公共子序列。若 Xm-1 和 Y 有一个长度大于 k 的公共子序列 W,则 W 也是 X 和 Y 的一个长度大于 k 的公共子序列。 这与 Z 是 X 和 Y 的一个最长公共子序列矛盾。 由此即知 Z 是 Xm-1 和 Y 的一个最长公共子序列。 这个定理告诉我们,两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列。因此,最长公 共子序列问题具有最优子结构性质。

2. 子问题的递归结构
由最长公共子序列问题的最优子结构性质可知,要找出 X=<x1, x2, …, xm>和 Y=<y1, y2, … , yn> 的最长公共子序列,可按以下方式递归地进行:当 xm=yn 时,找出 Xm-1 和 Yn-1 的最长公共子序列,然后在 其尾部加上 xm(=yn)即可得 X 和 Y 的一个最长公共子序列。 xm≠yn 时, 当 必须解两个子问题, 即找出 Xm-1 和 Y 的一个最长公共子序列及 X 和 Yn-1 的一个最长公共子序列。这两个公共子序列中较长者即为 X 和 Y 的 一个最长公共子序列。 由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。例如,在计算 X 和 Y 的最长公共子序 列时,可能要计算出 X 和 Yn-1 及 Xm-1 和 Y 的最长公共子序列。而这两个子问题都包含一个公共子问题,即计 算 Xm-1 和 Yn-1 的最长公共子序列。

第 1 页

2012-12-5

动态规划-最长公共子序列
与矩阵连乘积最优计算次序问题类似,我们来建立子问题的最优值的递归关系。用 c[i,j]记录序列 Xi 和 Yj 的最长公共子序列的长度。其中 Xi=<x1, x2, …, xi>,Yj=<y1, y2, …, yj>。当 i=0 或 j=0 时,空序列是 Xi 和 Yj 的最长公共子序列,故 c[i,j]=0。其他情况下,由定理可建立递归关系如下:

?0 当i ? 0或j ? 0时 ? c[i, j] ? ?c[i ? 1, j ? 1] ? 1 当i, j ? 0且x i ? y j时 ?max(c[i, j ? 1], c[i ? 1, j]) 当i, j ? 0且x ?? y 时 i j ?

3. 计算最优值
直接利用上式式容易写出一个计算 c[i,j]的递归算法,但其计算时间是随输入长度指数增长的。由于在所考 虑的子问题空间中,总共只有 O(m*n)个不同的子问题,因此,用动态规划算法自底向上地计算最优值能提高 算法的效率。X 和 Y 的最长公共子序列的长度记录于 c[m,n]中。由于每个数组单元的计算耗费 O(1)时间,算 法 LCS_LENGTH 耗时 O(m*n)。 4.构造(打印)最长公共子序列 5.算法的改进 对于一个具体问题,按照一般的算法设计策略设计出的算法,往往在算法的时间和空间需求上还可以改进。 这种改进,通常是利用具体问题的一些特殊性。 数组元素 c[i,j]的值仅由 c[i-1,j-1]{左斜上},c[i-1,j] {正上}和 c[i,j-1] {左}三个值之一确定。 Program p8_2(Input, Output); const maxlen=200; var i,j:longint; c:array[0..maxlen,0..maxlen] of byte; x,y,z:string; begin assign(input,'lcs.in'); reset(input); assign(output,'lcs.out'); rewrite(output); readln(x); readln(y); fillchar(c,sizeof(c),0); for i:=1 to length(x) do for j:=1 to length(y) do if x[i]=y[j] then c[i,j]:=c[i-1,j-1]+1 else if c[i-1,j]>c[i,j-1] then c[i,j]:=c[i-1,j] else c[i,j]:=c[i,j-1];
{构造(打印)最长公共子序列}

z:=''; i:=length(x); j:=length(y); writeln(c[i,j]); while (i>0) and (j>0) do if x[i]=y[j] then begin z:=x[i]+z;i:=i-1;j:=j-1 end else if c[i-1,j]>c[i,j-1] then i:=i-1 else j:=j-1; if z<>'' then writeln(z); close(input);close(output) end.

第 2 页

2012-12-5

动态规划-最长公共子序列
另外,如果只需要计算最长公共子序列的长度,则算法的空间需求还可大大减少。事实上,在计算 c[i,j]时, 只用到数组 c 的第 i 行和第 i-1 行。因此,只要用 2 行的数组空间就可以计算出最长公共子序列的长度。更进一 步的分析还可将空间需求减至 min(m, n)。

?0 当i ? 0或j ? 0时 ? c[i, j] ? ?c[i ? 1, j ? 1] ? 1 当i, j ? 0且a i ? b j时 ?max(c[i, j ? 1], c[i ? 1, j]) 当i, j ? 0且a ?? b 时 i j ?
我们将 a 的前缀长度 i 设为阶段(1<=i<=n),b 的前缀长度 j 设为状态(1<=j<=n),根据最优子结构的 三个性质决策的 LCS 长度 c[i,j]。 由状态转移方程可以看出, i 阶段的计算仅与第 i-1 阶段的状态发生联系。 第 为了节省内存,设 c[0,i] — a 'n ?1 与 b'j 的 LCS 长度;c[1,j] — a i' 与 b'j 的 LCS 长度。(1<=j<=n) 经过 n 个阶段的计算,得出 c[1,n]即为 a 和 b 的 LCS 长度。 fillchar(c,sizeof(c),0); for i:=1 to n do{枚举阶段} begin c[0]:=c[1]; {数组第 1 行传递给第 0 行,只要长度就不需要保存前面的计算结果,记忆前 i-1 阶段的计算结果} for j:=1 to n do{枚举状态} begin{根据最优子结构的三个性质决策} c[1,j]:=c[1,j-1]; if a[i]=b[j] then c[1,j]:=c[0,j-1]+1{性质 1} else if c[1,j-1]>c[0,j] then c[1,j]:=c[1,j-1] {性质 2,3} else c[1,j]:=c[0,j]; end; end; writeln(n-c[1,n]);

第 3 页

2012-12-5

动态规划-最长公共子序列
var x,y,z:string; c:array[0..255,0..255]of integer; i,j:integer; begin assign(input,'lcs11.in');reset(input); assign(output,'lcs.out');rewrite(output); readln(x); readln(y); fillchar(c,sizeof(c),0); for i:=1 to length(x) do for j:=1 to length(y) do if x[i]=y[j] then begin c[i,j]:=c[i-1,j-1]+1; end else if c[i-1,j]>c[i,j-1] then c[i,j]:=c[i-1,j] else c[i,j]:=c[i,j-1]; i:=length(x); j:=length(y); writeln(c[i,j]); z:=''; while (i>0)and(j>0) do begin if x[i]=y[j] then begin z:=x[i]+z;dec(i);dec(j); end else if c[i-1,j]>c[i,j-1] then dec(i) else dec(j); end; if z<>'' then writeln(z); close(input); close(output); end.

第 4 页

2012-12-5


更多相关文档:

动态规划解最长公共子序列

动态规划最长公共子序列 一、 问题描述与分析 经常遇到一些复杂的问题, 有时我们将待求解问题分解成若干个子问题, 先求解子问题, 然后从这些子问题的解得到原...

动态规划_最长公共子序列

动态规划_最长公共子序列_天文/地理_自然科学_专业资料。动态规划 最长公共子序列 课程设计 课 程 名 称 算法分析 13 计算机 2 班,132511022 计算机科学与技术 ...

用动态规划法解决最长公共子序列问题

动态规划解最长子序列 一、 课程设计目的掌握动态规划法的原理,并能够按其原理编程实现求两个序列数据的最长公共子系 列,以加深对其的理解。 二、 课程设计内容 ...

动态规划最长公共子序列

动态规划最长公共子序列_计算机软件及应用_IT/计算机_专业资料 暂无评价|0人阅读|0次下载|举报文档 动态规划最长公共子序列_计算机软件及应用_IT/计算机_专业资料。...

动态规划 最长公共子序列

动态规划 最长公共子序列_计算机软件及应用_IT/计算机_专业资料。动态规划 最长公共子序列 java动态规划算法的基本思想是: 将待求解的问题分解成若干个相互联系的 子...

动态规划法求解最长公共子序列(含Java代码)

动态规划法求解最长公共子序列(含Java代码)_计算机软件及应用_IT/计算机_专业资料。动态规划法求解最长公共子序列(含Java代码)今日推荐 88...

动态规划解最长公共子序列问题

动态规划法 经常会遇到复杂问题不能简单地分解成几个子问题,而会分解出一 系列...考虑最长公共子序列问题如何分解成子问题,设 A=“a0,a1,?,am-1”,B=“b0...

动态规划解最长公共子序列问题

动态规划最长公共子序列问题 2009-05-30 21:28 36702 人阅读 评论(36) 收藏 举报 c 算法 动态规划法 经常会遇到复杂问题不能简单地分解成几个子问题,而会...

算法设计与分析(动态规划法解最长公共子序列)

{ e.printStackTrace(); } } while (true); } } 输入文本 test2.txt 截图: 结果输出截图: 实验小结: 通过本次实验,对动态规划法求最长公共子序列有更深...

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

动态规划-最长公共子序列_学科竞赛_高中教育_教育专区。动态规划-最长公共子序列问题描述 一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说,若...
更多相关标签:
动态规划 | 最长公共子序列 | lcs | 动态规划 最长子序列 | 最长公共子序列 c | 最长公共上升子序列 | 最长公共子序列算法 | 最长公共子序列问题 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com