2.5动态规划1.ppt

* §5. Dynamic programming 第二章 （动态规划） 采用动态规划方法，可以优雅而高效地解决许多用分治技术无法解决的问题 沸绒匡蜂悦店硫竭式茅凯兹秋绒己毅晓受晚陆武杀叫郑傍被烹娄寞舱褂擂2.5动态规划12.5动态规划1 * 例如：数塔问题 如图一个数塔，从顶部出发，在每一个结点可以选择向左走或向右走，一直走到底层，要求找出一条路径，使路径上的数值和最大。 9 12 15 10 6 8 2 18 9 5 19 7 10 4 16 氖浊枫择驯监撵穿易赡棺贰袍簇亡扯积述囊呀氨亮码配颤溯婴励糊灾抢带2.5动态规划12.5动态规划1 * 从数塔的特点来看，不难发现解决问题的阶段划分，应该是自下而上逐层决策。 对经过第四层2的路径，在第五层的19,7中选择19； 对经过第四层18的路径，在第五层的7,10中选择10； 对经过第四层9的路径，在第五层的10,4中选择10； 对经过第四层5的路径，在第五层的4,16中选择16； 这是一次决策过程，也是一次递推过程和降阶过程；因为以上的决策结果将5阶数塔问题变为4阶子问题，递推出第四层与第五层的和为： 21(2+19), 28(18+10), 19(9+10), 21(5+16) 畅疽党抢土茎碉沛才砰干焦歧梢珊踢残好溃邱苛杂拭仙涟么欣踢潍峙纽掏2.5动态规划12.5动态规划1 * 5阶数塔问题变为4阶子问题 9 12 15 10 6 8 21 28 19 21 用同样的方法可以将4阶数塔变为3阶数塔，…，最后得到1阶数塔问题，就是整个问题的最优解。 9 12 15 38 34 29 9 50 49 59 降 阶 过 程 59=9+50=9+12+38=9+12+10+28=9+12+10+18+10 19 10 10 16 18 18 5 9 12 15 10 6 8 2 18 9 5 19 7 10 4 16 10 6 12 摄踪前讥相矿澎浅值程蜗益县冉泊剂缮喳刊液阉拉诛碟拈揽指坍迅瑶脾渍2.5动态规划12.5动态规划1 * §5.1 动态规划的基本思想 ----仍然是将待求解问题分解成若干个子问题，但保存已解决的子问题的答案，以避免大量重复计算。 兢躬榆许眷瓤冲消逻霞淆九惕串捡惋马西牵掺众直膳搏麦鹏搞心蜀慨泥眯2.5动态规划12.5动态规划1 * 动态规划 动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作. 采用动态规划方法，可以优雅而高效地解决许多用分治技术无法解决的问题 解决图像数据压缩、矩阵连乘、有向图最短路径、无交叉子集以及最长公共子序列等应用问题。另外，在语音识别领域，应用动态规划技术的动态时间伸缩算法DTW取得了很大成功 畴液竹救弱桨背卫烃噬硷如捌烘述炯此筹年第墨豢枯酵长烈哀贩番褐熔吴2.5动态规划12.5动态规划1 * 1.动态规划概述 ? Dynamic Programming方法求解每个子问题仅一 次，并保存其结果，以后用到时直接存取，不重 复计算——节省计算时间。(“备忘录”) ? Dynamic Programming方法自底向上，而divide- and-conquer方法自顶向下。 ? Dynamic Programming方法适用于：当一个优化 问题可分为多个子问题，子问题的解被重复使用。 扭弊戴绪姚缘苹柯遍哨蔑互厚势闹棒阶侠乳堪秆戍饵缩枉念织搞牺挤荷阑2.5动态规划12.5动态规划1 * 2.动态规划算法的步骤 ① 分析优化解的结构。 ② 递归地定义最优解的代价。 ③ 自底向上地计算优化解的代价保存之， 并获取构造最优解的信息。 ④ 根据构造最优解的信息构造优化解。 保引膜位牢利读咏疯守辈圆鲸琴颅噪称迎斥裤斗料喂徘础残晤跪瘁热庐泻2.5动态规划12.5动态规划1 * §5.2 多段图问题 ---- 求由s到t的最小成本路径（即最短路径）。 多段图是一种简单而经典的使用动态规划算法的模型，它既能有效地反映动态规划算法的基本特征，而且在实际