算法设计与分析课件 29 最长公共子序列

算法设计与分析本节要点CONTENTS最长公共子序列最长公共子序列假设爸爸对应的基因序列为X={x1，x2，x3，…，xm}，孩子对应的基因序列Y={y1，y2，y3，…，yn}，那么怎么找到他们有多少相似的基因呢？如果按照严格递增的顺序，从爸爸的基因序列X中取出一些值，组成序列Z={xi1，xi2，xi3，…，xik}，其中下标{i1，i2，i3，…，ik

}是一个严格递增的序列。那么就说Z是X的子序列，Z中元素的个数就是该子序列的长度。X和Y的公共子序列是指该序列既是X的子序列，也是Y的子序列。最长公共子序列最长公共子序列问题是指：给定两个序列X={x1，x2，x3，…，xm}和Y={y1，y2，y3，…，yn}，找出X和Y的一个最长的公共子序列。例如：X=（A，B，C，B，A，D，B），Y=（B，C，B，A，A，C），那么最长公共子序列是B，C，B，A。如何找到最长公共子序列呢？最长公共子序列如果使用暴力搜索方法，需要穷举X的所有子序列，检查每个子序列是否也是Y的子序列，记录找到的最长公共子序列。X的子序列有2m个，因此暴力求解的方法时间复杂度为指数阶，这是我们避之不及的爆炸性时间复杂度。那么能不能用动态规划算法呢？下面分析该问题是否具有最优子结构性质。最长公共子序列（1）分析最优解的结构特征假设已经知道Zk={z1，z2，z3，…，zk}是X={x1，x2，x3，…，xm}和Y={y1，y2，y3，…，yn}的最长公共子序列。这个假设很重要，我们都是这样假设已经知道了最优解。那么可以分3种情况讨论。最长公共子序列最长公共子序列（2）建立最优值的递归式设c[i][j]表示Xi和Yj的最长公共子序列长度。• xm=yn=zk：那么c[i][j]=c[i−1][j−1]+1；• xm≠yn：那么只需要求解Xi和Yj−1的最长公共子序列和Xi−1和Yj的最长公共子序列，取最大值：c[i][j]=max{c[i][j−1],c[i−1][j]}。最长公共子序列（3）自底向上计算最优值，并记录最优值和最优策略i=1时：{x1}和{y1，y2，y3，…，yn}中的字符一一比较，按递归式求解并记录最长公共子序列长度。i=2时：{x2}和{y1，y2，y3，…，yn}中的字符一一比较，按递归式求解并记录最长公共子序列长度。……最长公共子序列（4）构造最优解上面的求解过程只是得到了最长公共子序列长度，并不知道最长公共子序列是什么，那怎么办呢？例如，现在已经求出c[m][n]=5，表示Xm和Yn的最长公共子序列长度是5，那么这个5是怎么得到的呢？可以反向追踪5是从哪里来的。最长公共子序列c[i][j]的来源一共有3个：c[i][j]=c[i−1][j−1]+1，c[i][j]=c[i][j−1]，c[i][j]=c[i−1][j]。计算最优值时，用辅助数组b[i][j]记录来源：c[i][j]=c[i−1][j−1]+1，b[i][j]=1；c[i][j]=c[i][j−1]，b[i][j]=2；c[i][j]=c[i−1][j]，b[i][j]=3。这样就可以根据b[m][n]反向追踪最长公共子序列，当b[i][j]=1时，输出xi；当b[i][j]=2时，追踪c[i][j−1]；当b[i][j]=3时，追踪c[i−1][j]，直到i=0或j=0停止。最长公共子序列以字符串s1=“ABCADAB”，s2=“BACDBA”为例。最长公共子序列以字符串s1=“ABCADAB”，s