最长公共子序列
1. 若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列； 2. 若xm≠yn且zk≠xm ，则Z是Xm-1和Y的最长公共子序列； 3. 若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>。 证明 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的一个最长公共子序列。 2.由于zk≠xm，Z是Xm-1和Y的一个公共子序列。若Xm-1和Y有一个长度大于k的公共子序列W，则W也是X和Y的一个长度大于k的公共子序列。这与Z是X和Y的一个最长公共子序列矛盾。由此即知Z是Xm-1和Y的一个最长公共子序列。 3. 与 2.类似。 这个定理告诉我们，两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。 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的最长公共子序列。 与矩阵连乘积最优计算次序问题类似，我们来建立子问题的最优值的递归关系。用c[i,j]记录序列Xi和Yj的最长公共子序列的长度。其中Xi=<x1,x2, …, xi>，Yj=<y1, y2, …,yj>。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列，故c[i,j]=0。其他情况下，由定理可建立递归关系如下： 3.计算最优值 直接利用(2.2)式容易写出一个计算c[i,j]的递归算法，但其计算时间是随输入长度指数增长的。由于在所考虑的子问题空间中，总共只有θ(m*n)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。 计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=<x1, x2, …,xm>和Y=<y1, y2, …,yn>作为输入。输出两个数组c[0..m ,0..n]和b[1..m,1..n]。其中c[i,j]存储Xi与Yj的最长公共子序列的长度，b[i,j]记录指示c[i,j]的值是由哪一个子问题的解达到的，这在构造最长公共子序列时要用到。最后，X和Y的最长公共子序列的长度记录于c[m,n]中。 Procedure LCS_LENGTH(X,Y); begin m:=length[X]; n:=length[Y]; for i:=1 to m do c[i,j]:=0; for j:=1 to n do c[0,j]:=0; for i:=1 to m do for j:=1 ton do if x[i]=y[j] then begin c[i,j]:=c[i-1,j-1]+1; b[i,j]:="↖"; end else if c[i-1,j]≥c[i,j-1] then begin c[i,j]:=c[i-1,j]; b[i,j]:="↑"; end else begin c[i,j]:=c[i,j-1]; b[i,j]:="←" end; return(c,b); end; 由于每个数组单元的计算耗费Ο(1)时间，算法LCS_LENGTH耗时Ο(mn)。 4.构造最长公共子序列 由算法LCS_LENGTH计算得到的数组b可用于快速构造序列X=<x1, x2, …,xm>和Y=<y1, y2, …,yn>的最长公共子序列。首先从b[m,n]开始，沿着其中的箭头所指的方向在数组b中搜索。当b[i,j]中遇到"↖"时，表示Xi与Yj的最长公共子序列是由Xi-1与Yj-1的最长公共子序列在尾部加上xi得到的子序列；当b[i,j]中遇到"↑"时，表示Xi与Yj的最长公共子序列和Xi-1与Yj的最长公共子序列相同；当b[i,j]中遇到"←"时，表示Xi与Yj的最长公共子序列和Xi与Yj-1的最长公共子序列相同。 下面的算法LCS(b,X,i,j)实现根据b的内容打印出Xi与Yj的最长公共子序列。通过算法的调用LCS(b,X,length[X],length[Y])，便可打印出序列X和Y的最长公共子序列。 Procedure LCS(b,X,i,j); begin if i=0 or j=0 then return; if b[i,j]="↖" then begin LCS(b,X,i-1,j-1); print(x[i]); {打印x[i]} end else if b[i,j]="↑" then LCS(b,X,i-1,j) else LCS(b,X,i,j-1); end; 在算法LCS中，每一次的递归调用使i或j减1，因此算法的计算时间为O(m+n)。 例如，设所给的两个序列为X=<A，B，C，B，D，A，B>和Y=<B，D，C，A，B，A>。由算法LCS_LENGTH和LCS计算出的结果如图2所示。 j 0 1 2 3 4 5 6 i yj B
发布日期：2022-02-02 02:58:12
浏览次数：13
分类：技术文章
本文共 5030 字，大约阅读时间需要 16 分钟。
最长公共子序列问题LCS 问题描述 参考解答 动态规划算法可有效地解此问题。下面我们按照动态规划算法设计的各个步骤来设计一个解此问题的有效算法。 1.最长公共子序列的结构 解最长公共子序列问题时最容易想到的算法是穷举搜索法，即对X的每一个子序列，检查它是否也是Y的子序列，从而确定它是否为X和Y的公共子序列，并且在检查过程中选出最长的公共子序列。X的所有子序列都检查过后即可求出X和Y的最长公共子序列。X的一个子序列相应于下标序列{1,2, …, m}的一个子序列，因此，X共有2m个不同子序列，从而穷举搜索法需要指数时间。 事实上，最长公共子序列问题也有最优子结构性质，因为我们有如下定理： 定理: LCS的最优子结构性质 设序列X=<x1, x2, …,xm>和Y=<y1, y2, …,yn>的一个最长公共子序列Z=<z1, z2, …,zk>，则：