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

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

摘 要：算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。其中动态规划是一种有效的解决问题的算法。此论文将围绕如何利用动态规划算法解决最长公共子序列问题展开。

关键词：算法，动态规划，最长公共子序列。

Abstract: Algorithm can be understood as a basic computing and the provisions of the order of operations that form a complete solving steps. Or as according to the request and design of the exact calculation of good limited sequence, and the steps and can solve problem of sequence. Among them the dynamic planning is a kind of effective problem solving algorithm. This paper will focus on how to use dynamic programming algorithm is presented to solve the longest public son on sequence. Keywords: algorithm, the dynamic programming, the longest public son sequence. 1 引言

动态规划算法是一种有效的解决问题的算法。通常将待求解问题分解成若干个子问题，利用这一特性，可以解决很多能够以大化小的问题，如：矩阵连成问题、求最长公共子序列、求凸多边形最优三角剖分、图像压缩、电路布线、流水作业调度等。此论文将联系如何求解最长公共子序列来描述动态规划算法。 2 动态规划的思想 2、1 动态规划的概念

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。

2、2 动态规划的基本步骤

(1)找出最优解的性质，并刻划其结构特征。 (2)递归地定义最优值。

(3)以自底向上的方式计算出最优值。

(4)根据计算最优值时得到的信息，构造最优解。 2、3 动态规划算法的基本要素 1）最优子结构

(1)矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。

(2)在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。

(3)利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。 2）重叠子问题

(1)递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。

(2)动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。

(3)通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。 3）备忘录方法

备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。 3、利用动态规划算法解决求最长公共子序列问题

3、1 问题描述

? 若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存

在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。例如，序列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的公共子序列。 3、2 最长公共子序列的结构

设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk} ，则

(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的最长公共子序列。

由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。 3、3 子问题的递归结构

由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序列和的最长公共子序列的长度。其中， Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时C[i][j]=0。其他情况下，由最优子结构性质可建立递归关系如下：

?0?c[i][j]??c[i?1][j?1]?1

?max{c[i][j?1],c[i?1][j]}?

3、4 计算最优值

i?0,j?0i,j?0;xi?yji,j?0;xi?yj由于在所考虑的子问题空间中，总共有θ(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。 3、5 算法的改进

? 在算法lcsLength和lcs中，可进一步将数组b省去。事实上，数组元素c[i][j]

的值仅由c[i-1][j-1]，c[i-1][j]和c[i][j-1]这3个数组元素的值所确定。对于给定的数组元素c[i][j]，可以不借助于数组b而仅借助于c本身在时间内确定c[i][j]的值是由c[i-1][j-1]，c[i-1][j]和c[i][j-1]中哪一个值所确定的。 ? 如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。事实上，

在计算c[i][j]时，只用到数组c的第i行和第i-1行。因此，用2行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至O(min(m,n))。

4、 结束语

通过对动态规划算法的学习，使我明白了利用动态规划算法解决问题的关键步骤以后算法的深刻内涵，明白了动态规划算法适合求解哪些问题，并联系实际问题明确解决问题的思路，在此基础上，也可以帮助我了解学习其他算法。 5、 参考文献

张德富，算法设计与分析 ，国防工业出版社，2009-8-1。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库利用动态规划算法解决最长公共子序列问题在线全文阅读。