【新编】动态规划策略教材

《【新编】动态规划策略教材》由会员分享，可在线阅读，更多相关《【新编】动态规划策略教材（42页珍藏版）》请在金锄头文库上搜索。

1、动 态 规 划 河海大学计算机信息学院 丁海军 dinghaijun 例例1 1 求出从 求出从顶点顶点1 1点到点到顶点顶点7 7点的最短路径点的最短路径 方法 方法 一 导言一 导言 u最优性原理 根据穷举法 1 3 5 7 为优化解 优化原理指 相对于初始决策1 3造成的问题状态 3 5 7 必须是3到7的最短路 否则 1 3 5 7 也不可能是优化的 无论第一步决策取 2 3 4 中那一节点 其后的决策序列 必须是该节点到目的节点的最短路 节点1到目的节点的最短路长度可从2 3 4到目的节点的 最短路长度 节点1到这些节点的边成本经枚举得到 u应用优化原理设计算法的过程如下 选择子问题

2、的表示 设f i 为i到目的节点的最短路长度 建立f i 的递归方程 设A i 为与i相邻的结点集合 则有 初始f 7 0 依次计算f 6 f 1 f 6 1 f 5 2 f 4 8 f 6 f 3 min 1 f 5 5 f 6 f 2 min 7 f 5 6 f 6 f 1 min 1 f 2 4 f 3 6 f 4 递归还可从前向后 f i 节点1到节点i的最短 路的长度 递归从f 1 0开始 u例1 数字三角问题 如图所示的数字三角形 从顶部出发 在每一个节点可以选择向左 走或者向右走 一直走到底部 要求找到一 条路径 使路径上的数字和最大 贪心法 贪心法 穷举法 穷举法 F1 F3

3、F4 F5 F2 用函数fi x 表示第i层节点到底部 假设是第N层 的路 径上数字和的最大值 显而易见 f1 9 9 max f2 12 f2 15 问题变成 f1 9 f2 12 12 max f3 10 f3 6 f2 15 15 max f3 6 f3 8 fi x x max fi 1 x1 fi 1 x2 递归公式的终止条件 fN 19 19 fN 7 7 思考 请同学们手工计算一下结果 如何编程 如何编程与数据结构有关 将原始数塔写成下面 的形式 用data i j data i j 表示这个矩阵 用矩阵d i j d i j 表示上面的f f i i x x 用矩阵表示的递归公

4、式是什么样子 用矩阵表示的递归公式是什么样子 D i j data i j max d i 1 j d i 1 j 1 D i j data i j max d i 1 j d i 1 j 1 D n j data i j D n j data i j i n 1 n 2 i n 1 n 2 2 1 2 1 最终的最终的结果结果d d 1 1 1 1 下一个问题 求的下一个问题 求的d i j d i j 后如何让具体最大值路径 后如何让具体最大值路径 b d i j data i j b d i j data i j if b d i 1 j then i j if b d i 1 j th

5、en i j i 1 j i 1 j if b d i 1 j 1 then i j if b d i 1 j 1 then i j i 1 j 1 i 1 j 1 u总结 动态规划问题的设计要素 划分子问题 用参数表达子问题的边界 将问题求解转化为多步判 断问题 确定优化目标函数 根据问题性质 以函数的极大或者极小为依据 确定 是否满足最优原理 列出关于优化函数的递推方程和边界 约束条件 注意 递推方程中总会存在极大或极小运算 求解递推方程 两种求解递推方程的方法 自顶向下 递归方法 自底向上 迭代方法 例例2 2 资源分配问题资源分配问题 设有设有n n个单位的资源个单位的资源 比如比如n

6、 n万元万元 的资金的资金 分配给分配给mm个项目 个项目 g g i i x x 为第为第i i个项目的到个项目的到x x单单 位的资源所产生的利润 求利润总和为最大的资源分位的资源所产生的利润 求利润总和为最大的资源分 配方案 配方案 下表是下表是n 7n 7万元资金分配给三个项目万元资金分配给三个项目A A B B C C的利润的利润 表表 分析 根据题意 本质上是求下面的优化问题分析 根据题意 本质上是求下面的优化问题 J xJ x 1 1 x x 2 2 x xm m max g max g 1 1 x x 1 1 g g 2 2 x x 2 2 g gm m x xm m x x

7、1 1 x x 2 2 x xm m n n 0 x 0 x i i n n 要求要求x x i i 是整数是整数 这是一个整数规划问题 这是一个整数规划问题 解法解法1 1 最笨的求解方法 穷举发 最笨的求解方法 穷举发 解法解法2 2 动态规划方法 动态规划方法 关键 找到一个递归公式关键 找到一个递归公式 假设 将数量为假设 将数量为x x单位的资源分配前单位的资源分配前i i个项目的最大个项目的最大 利润为利润为f f i i x x 可以写出下面的递归公式可以写出下面的递归公式 最终所需要的最大值是 最终所需要的最大值是 f fm m n n 如何编程 需要解决数据结构问题如何编程

8、需要解决数据结构问题 将函数用数组表示 将函数用数组表示 x x用用j j表示 表示 y y用用k k表示 可写出表示 可写出 下面的递归公式下面的递归公式 f m n f m n 就是所需要的最大利润 就是所需要的最大利润 实际编程时 还缺少一个东西 每个项目到底分配到多少资源量实际编程时 还缺少一个东西 每个项目到底分配到多少资源量 定义数组定义数组a i j a i j a i j kmax a i j kmax 表示前表示前i i个项目分配资源量为个项目分配资源量为j j 的情况下 使得前的情况下 使得前i i个项目利润最时 第个项目利润最时 第i i个项目分个项目分 配的资源量为配的

9、资源量为kmaxkmax 求的求的a i j a i j 之后 就可以求的每个项目分的资源量 之后 就可以求的每个项目分的资源量 j n j n for i m i 1 i for i m i 1 i x i a i j x i a i j j j x i j j x i 二 动态规划问题的设计方法 u1 动态规划的特点 最优值 递归 递推 公式 重复子问题 u自顶向下递归实现 存在问题 大量重复计算 解决办法 备忘录 u自底向上递推实现 根据问题递推公式性质 循环递推即可 三 进一步的例子 u例3 矩阵链乘 给定n个矩阵 A1 A2 An 其 中Ai与Ai 1是可乘的 i 1 2 3 n 1

10、 考察这n个 矩阵的连乘积 A1A2A3 An u由于矩阵乘法满足结合律 所以计算矩阵的连乘可 以有许多不同的计算次序 这种计算次序可以用加 括号的方式来确定 u若一个矩阵连乘积的计算次序完全确定 也就是说 该连乘积已完全加括号 则可以依此次序反复调用 2个矩阵相乘的标准算法计算出矩阵连乘积 u给定n个矩阵 A1 A2 An 其中Ai与 Ai 1是可乘的 i 1 2 n 1 如何确定计 算矩阵连乘积的计算次序 使得依此次序计 算矩阵连乘积需要的数乘次数最少 为了表示方便 以矩阵加括号表示矩阵 相乘的顺序 输入 向量 P n个矩阵的行数 列数 实例 P A1 10 100 A2 100 5 A3

11、 5 50 u完全加括号的矩阵连乘积可递归地定义为 1 单个矩阵是完全加括号的 2 矩阵连乘积A是完全加括号的 则A可 表示为2个完全加括号的矩阵连乘积B和C 的乘积并加括号 即 A B C uu设有四个矩阵设有四个矩阵A A B B C C D D 它们的维数分别是它们的维数分别是 16000 10500 36000 87500 34500 四种加括号方式 u穷举法 列举出所有可能的计算次序 并计算出每一种计算次序相 应需要的数乘次数 从中找出一种数乘次数最少的计算次 序 u算法复杂度分析 对于n个矩阵的连乘积 设其不同的计算次序为P n 由于每种加括号方式都可以分解为两个子矩阵的加括号 问

12、题 A1 Ak Ak 1 An 可以得到关于P n 的递推 式如下 将矩阵连乘积 A1A2A3 An简记为A i j 这里i j 考察计算A i j 的最优计算次序 设这个计算次序 在矩阵Ak和Ak 1之间将矩阵链断开 i k j 则其 相应完全加括号方式为 计算量 A i k 的计算量加上A k 1 j 的计算量 再加上A i k 和A k 1 j 相乘的计算量 u动态规划 划分子问题 确定子问题的边界 有i和j确定 子问题的边界 uu设计算设计算A i j A i j 1 i j n1 i j n 所需要的最少数乘次数 所需要的最少数乘次数 m i j m i j 则原问题的最优值为 则原

13、问题的最优值为m 1 n m 1 n uu当当i ji j时 时 A i j AiA i j Ai 因此 因此 m i im i i 0 0 uu当当i ji j时时 这里 的维数为 的位置只有 种可能 uu可以递归地定义可以递归地定义m i j m i j 为 为 确定优化函数和递推方程 设立标记函数 决策函数 为了确定加括号的次序 定义 s i j 记录m i j 最优时 k的位置 s i j k 问题 如何编程实现 自顶向下递归实现 自底向上迭代 递推 实现 int RecurMatrixChain P i j m i j s i j i for k i to j 1 q RecurMa

14、trixChain P i k RecurMatrixChain P k 1 j pi 1 pk pj If q m i j m i j q s i j k end if end for return m i j 这里没有写出算法的全部描述 进入递归调 用的初值等 uu方法方法1 1 直接递归方法实现 直接递归方法实现 26 复杂性满足递推关系 数学归纳法证明 T n 2n 1 n 2 显然为真 假设对于任何小于n 的 k 命题为真 则 递归实现的复杂性 27 n 5 计算子问题 81个 不同的子问题 15个 子 问 题 1 12 23 34 45 51 22 33 44 51 32 43 5

15、1 42 51 5 数812141284554222111 2 复杂性高的原因 子问题重复计算 uu方法方法2 2 直接递推方法 直接递推方法 MatrixChain P n 令所有的 m i j 初值为0 1 i j n for r 2 to n r为计算的矩阵链长度 for i 1 to n r 1 n r 1为最后r链的始位置 j i r 1 计算链i j m i j m i 1 j pi 1 pi pj Ai Ai 1 Aj s i j i 记录分割位置 for k i 1 to j 1 t m i k m k 1 j pi 1 pk pj Ai Ak Ak 1 Aj if t m i

16、 j m i j t s i j k end if end for k end for i A1A1A2A2A3A3A4A4A5A5A6A6 3030 35353535 15151515 5 55 5 10101010 20202020 2525 算法复杂度分析 算法matrixChain的主要计算量取决于算法中对r i和k的3重循环 循环体内的计算量为O 1 而3 重循环的总次数为O n3 因此算法的计算时间上 界为O n3 算法所占用的空间显然为O n2 例例4 4 最长公共子序列最长公共子序列 概念 概念 n n 若若给定序列给定序列X xX x 1 1 x x 2 2 x xm m 另 另一一序列序列Z Z z z 1 1 z z 2 2 z z k k 如果如果 存在存在一个严格递增下标序列一个严格递增下标序列 i i 1 1 i i2 2 i i k k 使得对于所有使得对于所有 j 1 2 kj 1 2 k有 有 z z j j x x i ij j 则称则称Z Z是是X X的子的子序列序列 例 例 序列序列Z BZ B C C D D B B 是序列是序列X AX A