动态规划.ppt
《动态规划.ppt》由会员分享,可在线阅读,更多相关《动态规划.ppt(9页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、动态规划(四),求最长不下降序列,问题描述: 设有一个正整数的序列:b1, b2, bn, 对于下标i1i2ih, 若有bi1bi2bih,则称存在一个长度为h的不下降序列。例如,下列数13 7 9 16 38 24 27 38 44 49 21 52 63 15对于下标 i1=1,i2=4,i3=5,i4=9,i5=13, 且满足13 16 38 44 63则存在长度为5的不下降序列。但是,我们看到还存在其它的不下降序列。如7 9 16 18 19 21 22 63则存在长度为8的不下降序列。问题:当给定b1, b2, bn后,求出最长的不下降序列h及这个序列中的各个数。,最长不下降序列-分
2、析,动态规划的难点之一:怎样定义问题?你首先要能定义出问题是什么,才能进一步定义出子问题是什么,然后才能证明或者直观地感觉问题与子问题之间是否存在最优子结构性质。从前往后分析。从序列长度为1开始,逐步放大序列长度,2,3,4看看要求的结果的变化规律。我们可能会很直接地想到,把问题定义成当前最长不下降序列。序列长度序列 当前最长不下降序列长度1131213 71313 7 92413 7 9 163513 7 9 16 384613 7 9 16 38 244 (2438, 长度不增加)713 7 9 16 38 24 27? (凭什么计算出当前值?) 由于当前记录的最长不下降序列是 7 9 1
3、6 38 ,而实际上应该有了更长的子序列 7 9 16 24 27。,13 7 9 16 38 24 27 38 44 49 21 52 63 15,最长不下降序列-分析,我们定义F(i) 为原始序列长度为I 的最长不下降序列,则F(I)只有一个子问题F(I-1),即原始序列长度为I-1的最长不下降序列。而且我们无法得出问题与子问题之间的“最优子结构”性质。重新思考关于问题的定义。我们定义问题F(i)为以bi结束的最长不下降序列。则得到如下的分析结果:下标I序列F(I)前趋结点下标131113 7 1213 7 92213 7 9 163313 7 9 16 384413 7 9 16 38
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 动态 规划 计划
限制150内