文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 计算机软件及应用 > 动态规划解最长公共子序列
侵权投诉

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

函数及其图像纯手工打,用表格及其公式编辑器写作。动态规划解最长公共子序列,C语言实现,算法核心在,

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

一、 问题描述与分析

经常遇到一些复杂的问题,有时我们将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。由于分解到的子问题往往不是独立的,用一个表来记录所有已解决的子问题的答案,这样就得到了原问题的解,这就是动态规划法的基本思想。 一个给定序列的子序列是在该序列中删去若干元素后得到的序列。给定两个序列X 和Y,当另一序列Z即是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列。在公共子序列中长度最长的则是最长公共子序列。

穷举搜索法是最容易想到的解题算法。对X的所有子序列,检查它是否也是Y的子序列,从而确定它是否是X和Y的公共子序列。并且在检查过程中记录最长的公共子序列。X的所有子序列都检查过后即可求出X和Y的最长公共子序列。事实上,最长公共子序列问题具有最优子结构的结构性质。

二、 算法设计

1. 最长公共子序列的结构

设序列X= 1, 2,…, 和Y= 1, 2,…, 的最长公共子序列为Z= 1, 2,…, ,则

1) 若 = ,则 = = ,且 1是 1和 1的最长公共子序列;

2) 若 ≠ 且 ≠ ,则Z是 1和Y的最长公共子序列;

3) 若 ≠ 且 ≠ ,则Z是X和 1的最长公共子序列。

其中,X 1= 1, 2,…, 1 ; Y 1= 1, 2,…, 1 ; Z 1= 1, 2,…, 1 。 证明:

1) 用反证法。若 ≠ ,则 1, 2,…, , 是X和Y的长度为k+1的公共子序列。这与Z是X和Y的最长公共子序列矛盾。因此,必有 = = 。由此可知 1是 1和 1的长度为k-1的公共子序列。若 1和 1有长度大于k-1的公共子序列W,,则将 加在其尾部产生X和Y的长度大于k的公共子序列。此为矛盾。故 1是 1和 1的最长公共子序列。

2) 由于 ≠ ,Z是 1和Y的公共子序列。若 1和Y有长度大于k的公共子序列W,则W也是X和Y的长度大于k的公共子序列。这与Z是X和Y的最长公共子序列矛盾。由此即知,Z是 1和Y的公共子序列。

3) 证明与(2)类似。

2. 子问题的递归结构

由最长公共子序列的问题的最优子结构可知,当 = 时,找出是 1和 1的最长公共子序列,然后在其尾部加上 (= )即可得X和Y的最长公共子序列。当 ≠ 时,必须解两个子问题,即找出 1和Y的一个最长公共子序列及X和 1的一个最长公共子序列。这两个公共子序列中较长者即为X和Y的最长公共子序列。

由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。首先建立子问题最优值的递归关系。用C 记录序列X 和Y 的最长公共子序列的长度。其中X = 1, 2,…, ;Y = 1, 2,…, 。当i=0或j=0时,空序列是X 和Y 的最长公共子序列,故此时C =0。在其他情况下,由最优子结构性质可建立递归关

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email