函数及其图像纯手工打,用表格及其公式编辑器写作。动态规划解最长公共子序列,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。在其他情况下,由最优子结构性质可建立递归关
动态规划解最长公共子序列 一、 问题描述与分析 经常遇到一些复杂的问题, 有时我们将待求解问题分解成若干个子问题, 先求解子问题, 然后从这些子问题的解得到原...
动态规划法 经常会遇到复杂问题不能简单地分解成几个子问题,而会分解出一 系列...考虑最长公共子序列问题如何分解成子问题,设 A=“a0,a1,?,am-1”,B=“...
动态规划解最长子序列 一、 课程设计目的掌握动态规划法的原理,并能够按其原理编程实现求两个序列数据的最长公共子系 列,以加深对其的理解。 二、 课程设计内容 ...
算法设计与分析 实验名称:动态规划法解最长公共子序列 张锦雄 专业: 计算机科学与技术 2007 级 1 班学号: 蓝冠恒 完成日期: 2011 年 1 月 12 日 二、主要...
利用动态规划算法解决最长公共子序列问题_物理_自然科学_专业资料 暂无评价0人阅读0次下载举报文档 利用动态规划算法解决最长公共子序列问题_物理_自然科学_专业...
实验二 动态规划法解最长公共子序列 一、实验内容及要求 1.要求按动态规划法原理求解问题; 2.要求交互输入两个序列数据; 3.要求显示结果。 二、实验仪器和软件...
学院:计算机科学与技术 专业:计科 092 姓名:毕业毅 学号:0907300425 广西大学实验项目卡(实验二)课程名称 算法设计与分析 项目名称 动态规划法解最长公共子序列 ...
2, … xm} 和 Y={y1,y2, …yn} ,找出 X 和 Y 的最长公共子序列。...动态规划算法可有效的解此问题。下面按照鼎泰规划算法设 计步骤来设计界此问题...
动态规划解最长公共子序列问题 2009-05-30 21:28 36702 人阅读 评论(36) 收藏 举报 c 算法 动态规划法 经常会遇到复杂问题不能简单地分解成几个子问题,而...
动态规划法求解最长公共子序列(含Java代码)_计算机软件及应用_IT/计算机_专业资料。动态规划法求解最长公共子序列(含Java代码)今日推荐 ...
热门文档