第3章_动态规划_1.ppt

第三章动态规划dynamicprogramming 1 2019年12月20日星期五 第3章动态规划 掌握设计动态规划算法的步骤 掌握动态规划算法的基本要素 通过应用范例学习动态规划算法设计策略 20世纪50年代 美国数学家r e bellman等人 最优化原理 动态规划 2 2019年12月20日星期五 第3章动态规划 3 2019年12月20日星期五 第3章动态规划 动态规划 dynamicprogramming 属运筹学中的规划论分支 是求解决策过程最优化的数学方法 20世纪50年代初美国数学家r e bellman等人在研究多阶段决策过程的优化问题时 提出了著名的最优化原理 principleofoptimality 把多阶段过程转化为一系列单阶段问题 逐个求解 创立了解决这类过程优化问题的新方法 动态规划 多阶段决策问题 指这样的一类特殊的活动过程 问题可以按时间顺序分解成若干相互联系的阶段 在每一个阶段都要做出决策 全部过程的决策是一个决策序列 要使整个活动的总体效果达到最优的问题 称为多阶段决策问题 4 2019年12月20日星期五 第3章动态规划 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题 但是一些与时间无关的静态规划 如线性规划 非线性规划 只要人为地引进时间因素 把它视为多阶段决策过程 也可以用动态规划方法方便地求解 应用广泛 经济管理 生产调度 工程技术和最优控制 例如最短路线 库存管理 资源分配 设备更新 排序 装载等问题 用动态规划方法比用其它方法求解更为方便 动态规划的基本要素 1 最优子结构性质 最优化原理 一个最优化策略的子策略总是最优的 一个问题满足最优化原理又称其具有最优子结构性质 2 子问题重叠性质 5 2019年12月20日星期五 第3章动态规划 a b c i j 如图 若路线i和j是a到c的最优路径 则根据最优化原理 路线j必是从b到c的最优路线 最优化原理是动态规划的基础 2019年12月20日星期五 6 第3章动态规划 一般来说 只要该问题可以划分成规模更小的子问题 并且原问题的最优解中包含了子问题的最优解 即满足最优化原理 则可以考虑用动态规划解决 7 2019年12月20日星期五 第3章动态规划 动态规划的基本思想 与分治法类似 其基本思想也是将待求解问题分解成若干个子问题 先求解子问题 然后从这些子问题的解得到原问题的解 与分治法不同的是 适合用动态规划求解的问题 经分解得到的子问题往往不是相互独立的 8 2019年12月20日星期五 第3章动态规划 t n 避免大重复计算 9 2019年12月20日星期五 第3章动态规划 动态规划的实质 动态规划的实质是分治思想和解决冗余 1 一种将问题实例分解为更小的 相似的子问题 2 存储子问题的解而避免计算重复的子问题 10 2019年12月20日星期五 第3章动态规划 主要特点 问题分解 采用表格技术 用多项式算法代替指数算法 空间换取时间 动态规划的特点 动态规划法用于最优化问题 这类问题会有多种可能的解 而动态规划找出其中最优值的解 若存在若干个取最优值的解的话 它只取其中的一个 对于重复出现的子问题 只在第一次遇到时加以求解 并把答案保存起来 以后再遇到时不必重新求解 11 2019年12月20日星期五 第3章动态规划 动态规划算法设计步骤 分析最优解的性质 并刻划其结构特征 递归地定义最优值 以自底向上的方式计算出最优值 根据计算最优值时得到的信息 构造最优解 12 2019年12月20日星期五 第3章动态规划 步骤 1 3 是基本步骤 在只需要求出最优值的情形 步骤 4 可以省略 若需要求出问题的一个最优解 则必须执行步骤 4 此时 需要利用在步骤 3 中计算最优值时记录的相关信息 两个矩阵相乘 计算c需要多少次数乘 3 1矩阵连乘问题 13 2019年12月20日星期五 第3章动态规划 三个矩阵连乘 7500 2019年12月20日星期五 14 第3章动态规划 矩阵连乘问题 2019年12月20日星期五 15 第3章动态规划 例如 矩阵连乘积a1a2a3a4可以有以下5种不同的完全加括号方式 a1 a2 a3a4 a1 a2a3 a4 a1a2 a3a4 a1 a2a3 a4 a1a2 a3 a4 每一种完全加括号方式对应于一种矩阵连乘积的计算次序 而这种计算次序与计算矩阵连乘积的计算量有着密切的关系 2019年12月20日星期五 16 第3章动态规划 为方便起见 定义下列的符号 矩阵连乘积 最少数乘次数 2019年12月20日星期五 17 第3章动态规划 1 分析最优解的结构 最优子结构 设 为最优计算次序 反证法 若存在一个计算次序 其需要的计算量更少 令 矛盾 矩阵连乘积计算次序问题具有最优子结构性质 即最优解包含着子问题的最优解 18 2019年12月20日星期五 第3章动态规划 2 建立递归关系 1 单一矩阵 2 19 2019年12月20日星期五 第3章动态规划 2 建立递归关系 单一矩阵 20 2019年12月20日星期五 第3章动态规划 3 计算最优值 用动态规划算法解问题 可依据其递归式以自底向上的方式进行计算 在计算过程中 保存已解决的子问题答案 2019年12月20日星期五 21 第3章动态规划 例1 计算矩阵连乘积a 1 6 其中各矩阵的维数分别为 2019年12月20日星期五 22 第3章动态规划 1 2 3 4 5 6 0 0 0 0 0 0 5000 1000 1 2 3 4 5 6 0 0 0 0 0 0 5 3500 4 5 15750 7875 9375 11875 15125 2625 4375 7125 10500 750 2500 5375 1 1 3 3 3 3 3 3 2 3 3 3 s i j 23 2019年12月2