动态规划入门讲解.ppt
《动态规划入门讲解.ppt》由会员分享,可在线阅读,更多相关《动态规划入门讲解.ppt(31页珍藏版)》请在三一文库上搜索。
1、动态规划入门讲解,by 张惜今,引入,我们用一个简单的例子来让大家了解什么是动态规划,灵梦的灵符,博丽灵梦是东方幻想乡中博丽神社的巫女,她跟幻想乡中最老资格的妖怪八云紫一起维护着隔绝幻想乡与现实世界的大结界,维护现实世界不被幻想乡中的妖怪侵害,幻想乡中的生物也可以自由自在的维持古老的生活方式。 但不幸的是,每隔六十年,结界会有一次大异变,为了维护结界的完整,博丽灵梦必须将灵力注入灵符,让灵力以最好的方式游走来修复结界。 灵梦的灵符是一个三角形,由一堆数字组成,每个数字表示灵力经过这个位置获得的修复值,三角形共n层,第i层有i个数字,从上方的最尖端注入灵力,灵力只能前往前位置的左下方或者右下方,
2、最终走的下面的边的某个位置释放,问灵梦最多可以获得多少修复值?,灵梦的灵符(USACO 1.5.1),最容易想到的方法:,回溯法,我们可以列举每一条可能的路线,分别累加比较每条路线的修复值进行比较,取得最大的一条作为答案。我们先不引入时间复杂度的计算,来用一个n较小的例子手工计算我们需要做的计算量。,为什么会计算那么多次呢?,因为这个算法有天然呆的属性,多次经过同一个点,太健忘了! 到这个点为止的最大和其实已经算出来了, 而回溯法在每次回溯时会重复计算!,这样要计算多少次?,我们先不引入时间复杂度的计算,来用一个n较小的例子手工计算我们需要做的计算量。 n4,共有2(4-1)8条路线 每条两次
3、加法和一次比较,共24次计算。 但是如果n=100呢?n=1000呢?指数级的运算量将会飞快增长,无法接受,换一种方法,取当前和较大的一种路线记录下来,往下走的时候直接用这个数跟下面点的修复值相加。 每一层都看做一个这样的问题,也就是到当前位置可以获得的最大值,依次类推。 原问题答案:到最下面某个位置(也就是最后一层子问题的当前位置)的最大修复值。 这就是传说中的:,动态规划,这样的计算次数,进行1次比较和1次加法 (1+4)*4/2-1=9个点 共计算18次。 虽然只少了6次,但n增长时与n2成正比的计算量就可以接受了。,动态规划的定义,动态规划是: 运筹学的一个分支 解决策过程最优化的数学
4、方法 把多阶段过程转化为一系列单阶段问题,动态规划 求解可以划分阶段的最优化问题的方法,效率高 局限性 必须可以划分阶段并满足几个条件 指数级-多项式级,动态规划的适用条件,不是一个纯理论的知识 看出来这个题题是考用动态规划求解 感性的认识,1.最优子结构,当前取得了最优值,那么直接用这个值来参与计算后面的状态能使后面的也最优 只要比较取一个值最优的保存,2.无后效性,当前作出决策只会影响后面的状态 前面的决策的影响都在状态中被包含了顺序,3.重叠子问题,也就是有前所述的那种重复计算的减少,动态规划才能减少算法的运行时间,动态规划的要素,阶段 状态 决策,阶段,每个状态属于一个阶段有了前后关系
5、保证最优子结构和无后效性比较明显,是前提也是一种特征 比如:时间的前后,灵梦的灵符那种层次关系,状态,动态规划时操作的对象 表示我们解到了哪一个子问题 1维或者多维 所属的阶段,一些相关信息,决策,是前面阶段的状态向后面的状态转移的操作 是决策把各个阶段的状态依次求出,动态规划的求解模式和程序实现,划分阶段 设计状态 确定决策写出转移 写出方程和边界 递推:看作递推方程,用循环依次递推出每一个状态 记忆化搜索:按搜索的方式写,但是对于已经搜索过的状态直接返回最优值,不再次搜索,按照方程的形态大致分类的几个例题,线性选择 背包问题 区间DP TreeDP,空的裂解原子核(POJ1887),灵乌路
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 动态 规划 入门 讲解
链接地址:https://www.31doc.com/p-2479577.html