Pascal动态规划.ppt
《Pascal动态规划.ppt》由会员分享,可在线阅读,更多相关《Pascal动态规划.ppt(22页珍藏版)》请在三一文库上搜索。
1、动态规划-入门篇,Dynamic programming,EZOI,多阶段决策过程,多阶段决策过程( multistep decision process )是指这样一类特殊的活动过程,过程可以按时间顺序分解成若干个相互联系的阶段,在每一个阶段都需要做出决策,全部过程的决策是一个决策序列。 动态规划(dynamic programming )算法是解决多阶段决策过程最优化问题的一种常用方法,难度比较大,技巧性也很强。利用动态规划算法,可以优雅而高效地解决很多贪婪算法或分治算法不能解决的问题。,求解问题的两个重要性质,最优子结构性质:如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具
2、有最优子结构性质( 即满足最优化原理 )。最优子结构性质为动态规划算法解决问题提供了重要线索。 子问题重叠性质:在用递归算法自顶向下对问题进行求解时,每次产生的子问题并不总是新问题,有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只计算一次,然后将其计算结果保存在一个表格中,当再次需要计算已经计算过的子问题时,只是在表格中简单地查看一下结果,从而获得较高的解题效率。,动态规划与分治、递归、贪心的区别,递归算法在程序实现上直观容易,但因为子问题被重复计算,且程序背后存在对栈的操作,速度(计算复杂度一般是指数级的)上劣于动态规划。在递归的过程中,通过保存子问题
3、的结果,可以减少计算量,同样是空间换时间的思想,称作memoization算法。 分治法要求各个子问题是独立的(即不包含公共的子问题),因此一旦递归地求出各个子问题的解后,便可自下而上地将子问题的解合并成原问题的解。动态规划与分治法的不同之处在于动态规划允许这些子问题不独立(即各子问题可包含公共的子问题),它对每个子问题只解一次,并将结果保存起来,避免每次碰到时都要重复计算。这就是动态规划高效的一个原因。 在贪婪算法中,每采用一次贪婪准则,便做出一个不可撤回的决策;而在动态规划算法中,还要考察每个最优决策序列中是否包含一个最优决策子序列,即问题是否具有最优子结构性质。,最短路径问题,图中给出了
4、一个地图,地图中每个顶点代表一个城市,两个城市间的连线代表道路,连线上的数值代表道路的长度。现在,想从城市A到达城市E,怎样走路程最短,最短路程的长度是多少?,题1 最长不下降子序列,【问题描述】 设有整数序列b1,b2,b3,bm,若存在i1i2i3in,且bi1bi2bi3bin,则称 b1,b2,b3,bm中有长度为n的不下降序列bi1,bi2,bi3,bin。求序列b1,b2,b3,bm中所有长度(n)最大不下降子序列 输入:整数序列 输出:最大长度n,题1 最长不下降子序列,【分析】 设F(i)为前I个数中的最大不下降序列长度。由题意不难得知,要求F(i),需要求得F(1)F(i-1
5、),然后选择一个最大的F(j) ( jbj ),那么前I个数中最大不下降序列便是前j个数中最大不下降序列后添加bi而得。可见此任务满足最优子结构,可以用动态规划解决。 通过上面的分析可得状态转移方程如下: F(i)=maxF(j)+1 (jbj)and(filen then len:=fi 记录最大值,题2 数塔,如下图所示的数塔,从顶部出发,在每一结点可以选择向左下走或是向右下走,一直走到底层,要求找出一条路径,使路径上的数的和最大。数塔层数用n表示,1=n=100。,题2 数塔,贪心法。时间上有保证,但得不到最优解。主要原因是贪心法只顾眼前利益,不考虑长远利益。 在规定时间内得到正确结果,
6、唯一的方法就是“动态规划”。 下面以示意图表示动态规划的过程:所选路径为:9-12-10-18-10 注意分析时,有以下几个特点: (1)将问题划分成了4个阶段; (2)每个阶段均得到了“部分”的最优解,得到最优解时,需要进行条件判断; (3)从最下面一层往顶层推导。,题3 棋盘路径问题,【题目简介】 有一个n*m的棋盘,左下角为(1,1),右上角为(n,m),如下图: 有一颗棋子,初始位置在(1,1),该棋子只能向右走或者向上走,问该棋子从(1,1)到(n,m)一共有几条路径? 输入:两个整数n和m 输出:一个数,路径总数,题3 棋盘路径问题,【题目简介】 如果使用枚举的方法,必定有很多路径
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Pascal 动态 规划
链接地址:https://www.31doc.com/p-2977140.html