学习面对实际问题如何设计算法与分析算法。
042最长公共子序列
Loading...
来自 Peking University 的课程
算法设计与分析 Design and Analysis of Algorithms
39 个评分
从本节课中
动态规划算法
动态规划是另一种常用的算法设计技术。首先通过矩阵相乘的例子介绍动态规划算法的设计思想、主要步骤、分析方法、迭代实现与存储表示等。然后通过投资、背包、最长公共子序列等典型问题展现不同的动态规划算法在子问题划分与迭代计算时的特点和提高算法效率的技巧。
与讲师见面
Wanling QuProfessor
School of EECS, Peking University
这次介绍一个最长公共子序列问题，我们先看看这个问题的描述。
有两个序列，一个是X一个是Z，X有
m项，就是x1到xm，Z呢有k个项，从z1
到zk。如果存在着X的元素构成的一个
严格递增的序列，就是说我们从这里边
选出若干个元素出来，它构成一个递增的序列，原来的顺序不变。
当然选的时候可以挑着选，不一定连续的 可以间隔的，这样选了以后呢使得
这里边的z1等于xi1 选的z2，这个z2等于这里边选的xi2。
一直到最后一个zk等于这里边选的第k个元素xik。
这样，满足这个等式的话我们就叫做Z是X的一个
子序列。所以Z呢它里边的k个元素，是从X中选出的。
选的这些个项的前后次序不能变，选的时候可以间隔着选。
这个就是子序列，那么有两个序列X和Y。
它的公共子序列Z是什么含义呢，就是Z既是X的子序列，也是Y的
子序列，就叫做它们的公共子序列，子序列的长度呢就是子序列含有的元素个数。
下边是这样一个问题，给定了两个序列。
X是m个元素，Y是n个元素，求X和Y的
最长的公共子序列。这里是一个实例。
X一共七个元素，Y呢是六个元素。
它的一个最长的公共子序列就是这些红颜色字符构成的元素。
我们看到它是B C B A，这个顺序两个序列
都是一样的，但是选的时候是可以间隔的，这个最长的长度是四。
对于给定的实例呢，它的解不一定是唯一的。
就是有的时候最长的子序列长度也是四。
当然它的选出来的子序列可能是不一样的。那我们这个 问题只要给出一个最长的公共子序列就可以了。
下面看一下蛮力的算法，蛮力的算法不妨
设m小于等于n，就是X的序列长度比Y的长度
要不超过Y的长度，可能会小一点，算法是依次
把X每个子序列来检查它在Y中是否出现。
那么X有多少种可能的子序列呢？X一共原来是m个字符，那每次
第一个字符到底选不选到这个子序列呢？有两种可能性，那么这m个字符呢
总共应该有2的m次方种可能性，所以它有2的m次方个不同的子序列。
对每个子序列要检查它在Y出现不出现，我们
可以从前到后扫描，那么这个扫描的时间 应该是O n的时间，因为Y的长度是O n。
那么把这所有的2的m次方个子序列每个都要 花O
n的时间来检查子序列它是不是Y的子序列。
这个情况下，总的时间就是n乘以2的m次方。
这是一个输入规模的指数量级的算法。
好，这是蛮力算法。下面我们看一下动态规划的算法，动态规划的算法先要来
界定子问题，这是原始的输入，x1到xm。
这样的一个序列，Y的序列在这里，y1到yn。
这样一个序列。这，我们用这块面积
来表示原始问题的它的一个规模，是由这样两个
维度的参数m和n来界定了它的大小。
下边我们要取子问题，子问题呢可能是X是取了
x1到xi，就是取这个长度一段子序列。
那么Y呢，取了y1到yj这个长度的一段子序列。
由这两个子序列来界定一个子问题它应该是在这个范围里的面积。
由这块来表达它的子问题，这就是说，看到子问题的界定它也是由两个参数
但这两个参数一个代表x的长度的最后的位置，一个是代表y的长度的最后的位置。
它是两个不同序列的参数，下边我们看一下
子问题知道后，它到底存在着什么的依赖关系，就是比较大的子问题
跟较小的子问题怎样的依赖，这是X序列它有m个元素，Y的序列有n个元素。
Z假定有k个元素，它是X和Y的
最长的公共子序列，那么我们来看一下 这个面积，假定这个代表m个
元素的长度，这个代表n个元素的长度，那就是这是X和Y这两个问题的原始
问题的它的这个规模可以用这样一个图来表示，下边我们分几种情况来讨论一下。
第一种情况就是x的最后一个元素和y的最后一个元素是相同的元素。
那就是说x的这边最后一个元素和y的这个地方的最后元素是同一个元素。
那我们怎么办呢？我们就把这个元素选到这个公共子序列里去，剩下的问题就是
X前m减1个元素和Y的前n减1个元素，它的最长的公共子序列是什么？
那这是一个子问题，如果这个最长的公共子序列知道了，我们把这个共同的
就是X和Y的最后那个相同的元素放到这个子问题的最长子序列的
后面就可以得到原问题的最长的公共子序列，所以
这个子问题可以归结到这样的一个子问题，就是X也减少一个元素，Y也减少一个元素。
它的子问题就是这个红颜色的区域代表的这个子问题，这是第一种情况。
下边看第二种情况，如果X的最后一个元素和
Y的最后一个元素不相等，它不可能被取到这个公共子序列中去。
那我们有两种选择，一种选择是我们取的这个公共子序列考虑的X最后
一个元素，不考虑它，不考虑它进公共子序列，那这个就是说X前m减1个元素
和Y的公共子序列就是原始问题X和Y的公共子序列。
那么X减少一个元素，它的界定的子问题就是这样的，X减少一个元素。
那就是X短了一个，但是Y还是原来的长度，所以就是这个子问题的
它的解，也就是在最后一个元素不等的时候，它有可能
作为原始问题的一种考虑，最长公共子序列的考虑，下边第三种情况
就是说你可以不考虑X的最后一个元素，类似的我也可以不考虑Y的最后一个元素。
我X选择原始的长度，而Y减少一个元素，那么这个子问题呢就是这样的
一个子问题，Y减少了一个长度，这是另外一种选择。这是规约成 X和Y
n减1这样的一个子问题。
所以我们看到这是几种不同的规约的办法。
那么这样的规约的办法都可以看到它满足优化原则
和子问题的重叠性，下面我们就依据这样的分析来给出它的递推
方程。X和Y的子序列，X是从
x1到xi，我们记作xi，这样的一个子问题，Y是从
y1到yj，也就是大Yj，这样 一个子问题，那么对于这个子问题来讲
它的最长的公共子序列的长度呢 记作C
ij，因为这是子问题的后边界，i j两个参数
我们用C ij来记它的长度，根据刚才讲的有几种可能的
规约的方法，一种方法就是如果X的最后一个元素xi和Y里边
的最后的一个元素yj是同一个元素，那么可以归结到X减少1那就是i减1了。
Y也减少1是j减1了，那就是说归结到 XY各少一个元素的前边这个子问题的长度
加上1，因为最后这个元素是同一个元素。
它可以加到子问题的最长公共子序列的后面就可以了，所以加上一个长度1。这是
刚才的第一种情况。后面两种情况呢，就是说如果最后这两元素不一样，
我也可能x去掉，也可能y去掉，有两种可能，都写在这个式子里头。这一项
是y减少1，归约成y-1的子问题，这一项是归约成x-1的子问题，
而子问题的长度就是我们这个原问题的长度。这是
这样三，三种的归约的办法。如果其中有一个序列的长度是0了，
这个时候最长公共子序列长度当然是0了。这是初值，这是递推方程的表示。
下边看一下标记函数，标记函数呢，实际上讲的是当你得到这个
长度的时候，到底你是按照刚才那几种归约的方法，是怎么样得到的，就是哪个
归约的方式。这个标记函数B[i, j]就是对子问题，i,j界定的子问题它的标记函数。
这个标记函数的值呢我们用这三个箭头来表示，一个是斜向的，
一个是横向的，一个是向上的，纵向的。假定这个是x的界定范围是到
i，y的界定的范围是到j，这样的一个子问题，也就是说是由这个面积来表达的子问题。
那么我们看到根据递推方程，如果你是选择了这样的递推，
就是说x的最后元素和y的最后元素是同一个元素，
它可以归约到前边红颜色这个区域的子问题，然后把这个子问题的解加上这个最后这个
共同元素就可以得到原问题的最长公共子序列。那就是由原始问题这个黑框的
这个矩形可以归结到这个红颜色的矩形，它是一个 斜方向向上的归结，由这个位置的元素归结到这个位置的
元素。所以我们就把它标记成这个斜的箭头，这是第一种情况。
如果你采用的是这个归结办法，就是y去掉一个元素，因为它
x跟y序列的最后元素不等，我不考虑y最后的元素，
那这个情况下呢，相当于把这个元素去掉，去掉对应的是这个 蓝颜色的子问题，那原始的项最大的项是在这里，
那归约到这个子问题后，最大项在这里，它是一个横向的一个移动，我们就用一个横箭头来- 表示它。
最后一种归约的办法呢，就是x的最后的元素不考虑。
这个归结办法呢那正好对应的是这个黄色的子问题，它正好位置是向上的这样一个归结，
所以我们用一个向上的箭头来表示它。这是它的归结的方法。
那么通过这样的归结的方法呢，我们就可以来追踪问题的解。
下边我们看一下算法的伪码。这个是算法的伪码。
前面这个地方是赋初值，我们可以看到
它对所有的子序列，如果有一个子序列是0，这是y的长度是0，
下边是x长度是0，它的初值都赋成0。然后下边就开始
界定子问题i是x的后边界，j是y的后边界，
当把i，j界定以后，这个子问题就选择好了。然后当选择好了以后就按照
刚才讲的三种归约的方法进行计算。如果它最后一项相等，我们归约到这个情况，
这是它的优化函数值的计算选择，这个是它标记函数的
选择。否则如果它最后一项不相等，会有下面的归结
办法，或者选x减少一个的，或者选y减少一个的，两种归结办法呢
都要把函数值也替换出来，然后把它的标记函数也计上。
啊，这个就是这个算法的伪码。
那么有了这个 标记函数和这个优化函数值以后，怎么样得到它的解呢？
这个解我们可以按照这个伪码来进行追踪，
我们看到这个伪码呢，这是原始的是(B,i,j)
它是追踪，由(B,i,j)这个位置 开始向前追踪。那么当一个
子问题的长度是0的时候，这个序列是空，这个时候就可以输出了，追踪结束了。
那么我们看看追踪的做法是怎么做呢？如果这个标记是一个斜向上的标记，表示
它的最后一项被选到这个公共子序列中去了。而这项呢就是x的第 i
个项，我们就直接把这个项输出。所以输出这个子序列的时候是从后向前输出，
先输出它后一个字符。输出完了以后，这个时候我们根据归约的办法
x的长度也减1，y的长度也减1，就来追踪下边这个子问题它的
后面的字符是什么，大家看到的是一个递归调用同样的算法来做。
如果不是这种情况，它遇到的符号是个向上的符号，
这个时候是x减少1，因此我们把x的长度减1，来追踪x
长度减1的这个子问题，否则的话，那意味着这个符号是个横向的符号，
这个时候y减少1，就追踪y减少1的这个子问题。通过这样的办法从后向前
就把这个序列给生成出来了。下边我们看一个具体的实例，
这个是刚才一开始给的那个例子。如果我们按照它的计算过程，
它的标记函数就是最后形成这样一个表。形成这个表以后，我们就可以看到
我们的做法应该从最后这个项 向前进行追踪，那么这个项大家看到是向上，
向上我们就向上走，走到这个位置，就是从这个斜箭头的位置才要记录
这个字符。那么到这个位置以后，我们发现它是6，x的
这个标号是6，所以x的第6个字符就被取到序列的最后一项。
那么也就是取到了这个A，把这个A取进来了。然后下边就开始按照这个标号来移动了。
那这个标号是斜向上的，所以它就移动到这个位置。到这个位置以后，标号向上的，什么- 都不做，
只要移动就可以，我们并不需要取字符。到这个位置又是
一个斜向的，这个又开始取字符了，就是取到第二个字符，这是x的
第四个位置的字符，也就是这个B，把它取出来了。取出来以后，还按照斜的方向再移动，
移动追踪到这个位置，这个位置呢是横的方向，什么也不做，所以向左移动，
又到了这个斜的方向，那么把这个还要记下来，这是x的第三个字符，也就是这个C把它
记下来，记下来以后再按照这个箭头方向来追踪，追踪到这个位置，这个也不做，
接着追踪到左边这个位置，这是最后一个追踪到的字符，
x的第二位置的字符。那么按照这样的追踪办法，也就是说
在这些个位置的对应的x的字符
被选到这个最长的公共子序列中去，因此问题的解就是
后面的这个解，x的第2、第3、第4、第6这四个字符选出来，
就是B，C，B，A，这时问题的解就找到了。算法的
时空复杂度我们来估计一下。作为这个算法，
计算优化函数和标记函数，赋初值是O(m)+O(n)，
因为两个序列的长度，一个是m，一个是n。那么优化函数跟标记函数
它需要有mn个不同的值， 因为x的序列长度和y的序列长度确定了在这个表中有mn个项，
而每个项的计算呢，它是三种可能的选择，每个选择都是常数时间，
所以它总共花的时间呢是mn这个量级的工作量，
这是它的计算这个算法的这个时间。
下面我们看一下追踪解。追踪解呢，
每次它的长度呢是要缩小的，或者你缩小了X，或者缩小了Y，
也可能两个都同时缩小。所以你至多追踪
m+n步，因为这是X的长度和Y的长度之和，每次至少缩小1嘛，
所以至多这么多步就可以缩小到初值的情况。这是它的追踪的工作量。那么这两个函数
相比呢，这个函数的值更大一点，所以总的工作量呢是mn的
时间，空间呢因为它的备忘录是mn个项，也是mn的 空间，这个是算法的复杂度估计。
把这个最长公共子序列问题小结一下。
这个问题首先要把它建模，建模呢，建模成一个组合优化问题，包括
目标函数和它的约束条件，可以这样建模。然后我们看一下它的边界的界定，
边界的界定呢，实际上它是由两个参数来界定的，i和j，i代表X的后边界，
j代表Y的后边界，这是两个不同序列的边界，都是 后边界。根据边界界定呢，给出它的递推
方程和初值，然后判定优化原则是不是成立，如果成立的话，就可以
使用动态规划的方法。这里边介绍了这个算法的伪码，
包括计算它的优化函数和标记函数的伪码，
还有追踪解的伪码。所以这个解的追踪呢，和标记函数的设定，
在这个问题中也是一个重要的因素。最后是它的复杂度，复杂度呢，
这里边包括可以是时间复杂度，也可以估计它的空间复杂度，这主要是备忘录的大小。
这是关于这个最长公共子序列问题的算法的小结。
