计算机算法设计与分析PPT第三章动态规划资料

《计算机算法设计与分析PPT第三章动态规划资料》由会员分享，可在线阅读，更多相关《计算机算法设计与分析PPT第三章动态规划资料（110页珍藏版）》请在金锄头文库上搜索。

1、1 第3章动态规划 2 学习要点 理解动态规划算法概念 掌握动态规划算法基本要素 1 最优子结构性质 2 重叠子问题性质掌握设计动态规划算法的步骤 1 找出最优解的性质 并刻划其结构特征 2 递归地定义最优值 3 以自底向上的方式计算出最优值 4 根据计算最优值时得到的信息 构造最优解 3 通过应用范例学习动态规划算法设计策略 1 矩阵连乘问题 2 最长公共子序列 3 最大子段和 4 凸多边形最优三角剖分 5 多边形游戏 6 图像压缩 7 电路布线 8 流水作业调度 9 背包问题 10 最优二叉搜索树 4 历史及研究问题 动态规划 dynamicprogramming 是运筹学的一个分支 20

2、世纪50年代初美国数学家R E Bellman等人在研究多阶段决策过程 Multistepdecisionprocess 的优化问题时 提出了著名的最优性原理 把多阶段过程转化为一系列单阶段问题 逐个求解 创立了解决这类过程优化问题的新方法 动态规划 多阶段决策问题 求解的问题可以划分为一系列相互联系的阶段 在每个阶段都需要做出决策 且一个阶段决策的选择会影响下一个阶段的决策 从而影响整个过程的活动路线 求解的目标是选择各个阶段的决策使整个过程达到最优 5 动态规划主要用于求解以时间划分阶段的动态过程的优化问题 但是一些与时间无关的静态规划 如线性规划 非线性规划 可以人为地引进时间因素 把它

3、视为多阶段决策过程 也可以用动态规划方法方便地求解 动态规划是考察问题的一种途径 或是求解某类问题的一种方法 动态规划问世以来 在经济管理 生产调度 工程技术和最优控制等方面得到了广泛的应用 例如最短路线 库存管理 资源分配 设备更新 排序 装载等问题 用动态规划方法比其它方法求解更为方便 6 基本概念 状态 表示每个阶段开始时 问题或系统所处的客观状况 状态既是该阶段的某个起点 又是前一个阶段的某个终点 通常一个阶段有若干个状态 状态无后效性 如果某个阶段状态给定后 则该阶段以后过程的发展不受该阶段以前各阶段状态的影响 也就是说状态具有马尔科夫性 适于动态规划法求解的问题具有状态的无后效性

4、策略 各个阶段决策确定后 就组成了一个决策序列 该序列称之为一个策略 由某个阶段开始到终止阶段的过程称为子过程 其对应的某个策略称为子策略 7 最优性原理 Bellman最优性原理求解问题的一个最优策略序列的子策略序列总是最优的 则称该问题满足最优性原理 注 对具有最优性原理性质的问题而言 如果有一决策序列包含有非最优的决策子序列 则该决策序列一定不是最优的 8 动态规划的思想实质是分治思想和解决冗余动态规划算法与分治法类似 其基本思想也是将待求解问题分解成若干个子问题 算法总体思想 9 但是经分解得到的子问题往往不是互相独立的 不同子问题的数目常常只有多项式量级 在用分治法求解时 有些子问题

5、被重复计算了许多次 算法总体思想 10 如果能够保存已解决的子问题的答案 而在需要时再找出已求得的答案 就可以避免大量重复计算 从而得到多项式时间算法 T n 算法总体思想 11 动态规划基本步骤 找出最优解的性质 并刻划其结构特征 递归地划分子问题 递归地定义最优值 给出最优解的递归式 以自底向上的方式计算出最优值 根据计算最优值时得到的信息 构造最优解 注 步骤 是动态规划算法的基本步骤 如果只需要求出最优值的情形 步骤 可以省略 若需要求出问题的一个最优解 则必须执行步骤 步骤 中记录的信息是构造最优解的基础 12 给定n个矩阵 其中与是可乘的 考察这n个矩阵的连乘积由于矩阵乘法满足结合

6、律 所以计算矩阵的连乘可以有许多不同的计算次序 这种计算次序可以用加括号的方式来确定 若一个矩阵连乘积的计算次序完全确定 也就是说该连乘积已完全加括号 则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积 3 2矩阵连乘问题 13 完全加括号的矩阵连乘积 完全加括号的矩阵连乘积的递归定义 1 单个矩阵是完全加括号的 2 矩阵连乘积A是完全加括号的 则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号 即 14 15 矩阵连乘问题 问题描述给定n个矩阵 A1 A2 An 其中Ai与Ai 1是可乘的 矩阵Ai的维数为pi 1 pi i 1 2 n 1 如何确定计算矩阵连乘积的计算次序

7、 使得依此次序计算矩阵连乘积需要的数乘次数最少 注意 设Ap q Aq r两矩阵相乘 普通乘法次数为p q r 加括号对乘法次数的影响 16 17 穷举法列举出所有可能的计算次序 并计算出每一种计算次序相应需要的数乘次数 从中找出一种数乘次数最少的计算次序 算法复杂度分析 对于n个矩阵的连乘积 设其不同的计算次序为P n 由于每种加括号方式都可以分解为两个子矩阵的加括号问题 A1 Ak Ak 1 An 可以得到关于P n 的递推式如下 因此 穷举法不是一个有效算法 呈指数增长 18 计算量小的优先计算n个矩阵的连乘积共有n 1次乘法计算 首先在n 1次乘法计算中选择乘法计算量最小的两个矩阵优先

8、计算 然后再在剩下的n 2次乘法计算中选择计算量最小的两个矩阵进行计算 依此往下 该解决策略在某些情况下可得到最优解 但在很多情况下得不到最优解 如上例的第 5 种完全加括号方式即采用该策略 但得到的显然不是最优解 19 矩阵维数大的优先计算在n个矩阵的n 1个维数序列p0 p1 p2 pn中选择维数的最大值 设为pi 并把相邻两个含有维数pi的矩阵优先进行计算 然后在剩下的n个维数序列中再次选择维数的最大值 进行相应矩阵的乘法运算 依此往下 该策略与上一种策略相似 在某些情况下可得到最优解 但在有些情况下得不到最优解 如上例的第 3 种完全加括号方式就是采用该策略 显然它得到的是最优解 当

9、个矩阵的维数改为50 10 10 40 40 30和30 5时 可验证采用该策略得到的不是最优解 以上两种策略实质都是基于某种贪心选择的贪心算法 这种算法不一定能得到问题的全局最优解 在下一章我们将详细讨论此种策略 20 分治法将矩阵连乘积AiAi 1 Aj简记为A i j 设n个矩阵的连乘积A1A2 An的计算次序在矩阵Ak和Ak 1之间将矩阵链断开 1 k n 则其相应的完全加括号方式为 A1 Ak Ak 1 An 完全加括号是一个递归定义 可递归地计算A 1 k 和A k 1 n 然后将计算结果相乘得到A 1 n 可设计如下递归算法recurmatrixChain 21 22 该递归算法

10、的的计算时间T n 可递归定义如下 当n 1时 该算法的计算时间T n 有指数下界 分治法是该问题的一个可行方法 但不是一个有效算法 23 为何分治法的效率如此低下 recurmatrixChain 1 4 计算A 1 4 的递归树 从图中可看出 许多子问题被重复计算 这是分治法效率低下的根本原因 24 该问题可用分治思想解决 并存在大量冗余 可用动态规划求解 动态规划 25 矩阵连乘问题 将矩阵连乘积简记为A i j i j 考察计算A i j 的最优计算次序 设这个计算次序在矩阵Ak和Ak 1之间将矩阵链断开 i k j 则其相应完全加括号方式为 计算量为A i k 的计算量加上A k 1

11、 j 的计算量 再加上A i k 和A k 1 j 相乘的计算量 26 1 分析最优解的结构 特征计算A i j 的最优次序所包含的计算矩阵子链A i k 和A k 1 j 的次序也是最优的 反证可得 矩阵连乘计算次序问题的最优解包含着其子问题的最优解 这种性质称为最优子结构性质 问题的最优子结构性质是该问题可用动态规划算法求解的显著特征 27 28 假设计算A i j 1 i j n 所需要的最少数乘次数为m i j 则原问题的最优值为m 1 n i j时 A i j Ai m i i 0 i 1 2 ni j时 的维数为 2 建立递归关系 29 递归地定义m i j k的位置只有j i种可

12、能 取得的k为A i j 最优次序中的断开位置 并记录到表s i j 中 即s i j k 注 m i j 实际是子问题最优解的解值 保存下来避免重复计算 30 对于1 i j n不同的有序对 i j 对应于不同的子问题 不同子问题的个数最多只有由此可见 在递归计算时 许多子问题被重复计算多次 这也是该问题可用动态规划算法求解的又一显著特征 3 计算最优值 31 用动态规划算法解此问题 可依据其递归式以自底向上的方式进行计算 在计算过程中 保存已解决的子问题答案 每个子问题只计算一次 而在后面需要时只要简单查一下 从而避免大量的重复计算 最终得到多项式时间的算法 32 s voidMatrix

13、Chain int p intn int m int s n是连乘矩阵数目 A1A2 An p是矩阵维数 Ai的维数为pi 1 pi 1 i n m是n个矩阵连乘的数乘次数最小值 s存储矩阵连乘的最优计算次序 for inti 1 i n i m i i 0 对角线置0 计算Ai Ai的乘法次数 链长为1for intr 2 r n r 分别计算r个矩阵连乘的最小数乘次数for inti 1 i n r 1 i intj i r 1 m i j m i 1 j p i 1 p i p j Ai Aj在矩阵i处断开时的数乘次数s i j i 记录取得Ai Aj当前数乘次数的断开位置for int

14、k i 1 k j k 计算Ai Aj的最小数乘次数intt m i k m k 1 j p i 1 p k p j if t m i j m i j t s i j k 33 34 算法复杂度分析 算法MatrixChain的主要计算量取决于算法中对r i和k的3重循环 循环体内的计算量为O 1 而3重循环的总次数为O n3 因此算法的计算时间上界为O n3 算法所占用的空间显然为O n2 设要计算矩阵连乘积中各矩阵的维数分别为 35 4 用动态规划法求最优解 MatrixChain已记录了构造最优解所需要的全部信息 S i j 表明计算矩阵A i j 的最佳方式应在矩阵Ak和Ak 1之间断

15、开 即最优的加括号方式应为 A i k A k 1 j 从s 1 n 记录的信息可知A 1 n 的最优加括号方式为 A i s 1 n A s 1 n 1 n A i s 1 n 的最优加括号方式为 A i s 1 s 1 n A s 1 s 1 n 1 s 1 s 1 n A s 1 n 1 n 的最优加括号方式在s s 1 n 1 n 处断开 照此递推 最终可确定A 1 n 的最优完全加括号方式 即构造出问题的一个最优解 36 算法traceback 按照MatrixChain计算出的断点s指示加括号方式输出计算A i j 的最优计算次序 Voidtraceback inti intj i

16、nt s 按算法MatrixChain计算出的断点矩阵s指示的加括号方式输出计算A i j 的最优计算次序 if i j return traceback s i s i j traceback s s i j 1 j cout MultiplyA i s i j cout andA s i j 1 j endl 37 一 最优子结构 矩阵连乘计算次序问题的最优解包含着其子问题的最优解 这种性质称为最优子结构性质 在分析问题的最优子结构性质时 所用的方法具有普遍性 首先假设由问题的最优解导出的子问题的解不是最优的 然后再设法说明在这个假设下可构造出比原问题最优解更好的解 从而导致矛盾 利用问题的最优子结构性质 以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解 最优子结构是问题能用动态规划算法求解的前提 同一个问题可以有多种方式刻划它的最优子结构 有些表示方法的求解速度更快 空间占用小 问题的维度低 3 2动态规划算法的基本要素 38 二 重叠子问题 递归算法求解问题时 每次产生的子问题并不总是新问题 有些子问题被反复计算多次 这种性质称为子问题的重叠性质 动态规划算法