第5章-6-动态规划-算法设计基本方法.ppt

2020 4 20 南京信息工程大学计算机与软件学院 1 第5 6动态规划法 闫雷鸣 南京信息工程大学计算机与软件学院 2 2020 4 20 5 6动态规划 学习要点 理解动态规划算法的概念 理解动态规划算法的基本要素 1 最优子结构性质 2 重叠子问题性质了解设计动态规划算法的步骤 1 找出最优解的性质 并刻划其结构特征 2 递归地定义最优值 3 以自底向上的方式计算出最优值 4 根据计算最优值时得到的信息 构造最优解 南京信息工程大学计算机与软件学院 3 2020 4 20 分治法基本思想 简言之 将一个难以直接解决的大问题 分割成一些规模较小的相同问题 以便各个击破 分而治之 对这k个子问题分别求解 如果子问题的规模仍然不够小 则再划分为k个子问题 如此递归的进行下去 直到问题规模足够小 很容易求出其解为止 将求出的小规模的问题的解合并为一个更大规模的问题的解 自底向上逐步求出原来问题的解 南京信息工程大学计算机与软件学院 4 2020 4 20 动态规划算法与分治法类似 其基本思想也是将待求解问题分解成若干个子问题 动态规划算法总体思想 南京信息工程大学计算机与软件学院 5 2020 4 20 但是经分解得到的子问题往往不是互相独立的 不同子问题的数目常常只有多项式量级 在用分治法求解时 有些子问题被重复计算了许多次 算法总体思想 南京信息工程大学计算机与软件学院 6 2020 4 20 如果能够保存已解决的子问题的答案 而在需要时再找出已求得的答案 就可以避免大量重复计算 从而得到多项式时间算法 算法总体思想 T n 南京信息工程大学计算机与软件学院 7 2020 4 20 动态规划基本步骤 找出最优解的性质 并刻划其结构特征 递归地定义最优值 以自底向上的方式计算出最优值 根据计算最优值时得到的信息 构造最优解 南京信息工程大学计算机与软件学院 8 2020 4 20 例矩阵连乘积 给定n个矩阵 A1 A2 An 其中Ai与Ai 1是可乘的 i 1 2 n 1 如何确定计算矩阵连乘积的计算次序 使得依此次序计算矩阵连乘积需要的数乘次数最少 南京信息工程大学计算机与软件学院 9 2020 4 20 例矩阵连乘积 假定A为100 1矩阵 B为1 100矩阵 C为100 1矩阵 A B C需乘法数为100 1 100 100 100 1 20000而A B C 所需乘法数为1 100 1 100 1 1 200长度q的矩阵乘法链有指数量级 2n 的可能的相乘方式 有q个叶节点的二叉数的数目 要找一种相乘方式 使得元素乘法数最少 南京信息工程大学计算机与软件学院 10 2020 4 20 16000 10500 36000 87500 34500 完全加括号的矩阵连乘积可递归地定义为 1 单个矩阵是完全加括号的 2 矩阵连乘积A是完全加括号的 则A可表示为2个完全加括号的矩阵连乘积A和B的乘积并加括号 即A BC 设有四个矩阵A B C D 它们的维数分别是 矩阵连乘积 总共有五种完全加括号的方式 南京信息工程大学计算机与软件学院 11 2020 4 20 给定n个矩阵 其中与是可乘的 考察这n个矩阵的连乘积由于矩阵乘法满足结合律 所以计算矩阵的连乘可以有许多不同的计算次序 这种计算次序可以用加括号的方式来确定 若一个矩阵连乘积的计算次序完全确定 也就是说该连乘积已完全加括号 则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积 南京信息工程大学计算机与软件学院 12 2020 4 20 给定n个矩阵 A1 A2 An 其中Ai与Ai 1是可乘的 i 1 2 n 1 如何确定计算矩阵连乘积的计算次序 使得依此次序计算矩阵连乘积需要的数乘次数最少 穷举法 列举出所有可能的计算次序 并计算出每一种计算次序相应需要的数乘次数 从中找出一种数乘次数最少的计算次序 算法复杂度分析 对于n个矩阵的连乘积 设其不同的计算次序为P n 由于每种加括号方式都可以分解为两个子矩阵的加括号问题 A1 Ak Ak 1 An 可以得到关于P n 的递推式如下 南京信息工程大学计算机与软件学院 13 2020 4 20 动态规划 将矩阵连乘积AiAi 1 Aj 简记为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 相乘的计算量 南京信息工程大学计算机与软件学院 14 2020 4 20 特征 计算A i j 的最优次序所包含的计算矩阵子链A i k 和A k 1 j 的次序也是最优的 矩阵连乘计算次序问题的最优解包含着其子问题的最优解 这种性质称为最优子结构性质 问题的最优子结构性质是该问题可用动态规划算法求解的显著特征 分析最优解的结构 南京信息工程大学计算机与软件学院 15 2020 4 20 建立递归关系 设计算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 n当i j时 这里的维数为 的位置只有种可能 可以递归地定义m i j 为 南京信息工程大学计算机与软件学院 16 2020 4 20 计算最优值 对于1 i j n不同的有序对 i j 对应于不同的子问题 因此 不同子问题的个数最多只有 由此可见 在递归计算时 许多子问题被重复计算多次 这也是该问题可用动态规划算法求解的又一显著特征 用动态规划算法解此问题 可依据其递归式以自底向上的方式进行计算 在计算过程中 保存已解决的子问题答案 每个子问题只计算一次 而在后面需要时只要简单查一下 从而避免大量的重复计算 最终得到多项式时间的算法 南京信息工程大学计算机与软件学院 17 2020 4 20 用动态规划法求最优解 voidMatrixChain int p intn int m int s for inti 1 i n i m i i 0 for intr 2 r n 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 s i j i for intk i 1 k j k 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 南京信息工程大学计算机与软件学院 18 2020 4 20 南京信息工程大学计算机与软件学院 19 2020 4 20 算法复杂度分析 算法matrixChain的主要计算量取决于算法中对r i和k的3重循环 循环体内的计算量为O 1 而3重循环的总次数为O n3 因此算法的计算时间上界为O n3 算法所占用的空间显然为O n2 南京信息工程大学计算机与软件学院 20 2020 4 20 动态规划算法的基本要素 一 最优子结构 矩阵连乘计算次序问题的最优解包含着其子问题的最优解 这种性质称为最优子结构性质 在分析问题的最优子结构性质时 所用的方法具有普遍性 首先假设由问题的最优解导出的子问题的解不是最优的 然后再设法说明在这个假设下可构造出比原问题最优解更好的解 从而导致矛盾 利用问题的最优子结构性质 以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解 最优子结构是问题能用动态规划算法求解的前提 同一个问题可以有多种方式刻划它的最优子结构 有些表示方法的求解速度更快 空间占用小 问题的维度低 南京信息工程大学计算机与软件学院 21 2020 4 20 动态规划算法的基本要素 二 重叠子问题 递归算法求解问题时 每次产生的子问题并不总是新问题 有些子问题被反复计算多次 这种性质称为子问题的重叠性质 动态规划算法 对每一个子问题只解一次 而后将其解保存在一个表格中 当再次需要解此子问题时 只是简单地用常数时间查看一下结果 通常不同的子问题个数随问题的大小呈多项式增长 因此用动态规划算法只需要多项式时间 从而获得较高的解题效率 南京信息工程大学计算机与软件学院 22 2020 4 20 动态规划算法的基本要素 三 备忘录方法 动态规划的一种变形 备忘录方法的控制结构与直接递归方法的控制结构相同 区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看 避免了相同子问题的重复求解 intLookupChain inti intj if m i j 0 returnm i j if i j return0 intu LookupChain i i LookupChain i 1 j p i 1 p i p j s i j i for intk i 1 k j k intt LookupChain i k LookupChain k 1 j p i 1 p k p j if t u u t s i j k m i j u returnu 南京信息工程大学计算机与软件学院 23 2020 4 20 0 1背包问题 给定n种物品和一背包 物品i的重量是wi 其价值为vi 背包的容量为C 问应如何选择装入背包的物品 使得装入背包中物品的总价值最大 0 1背包问题是一个特殊的整数规划问题 南京信息工程大学计算机与软件学院 24 2020 4 20 在0 1背包问题中 需对容量为c的背包进行装载 从n个物品中选取装入背包的物品 每件物品i的重量为wi 价值为pi 对于可行的背包装载 背包中物品的总重量不能超过背包的容量 最佳装载是指所装入的物品价值最高 即p1 x1 p2 x1 pi xi 其1 i n x取0或1 南京信息工程大学计算机与软件学院 25 2020 4 20 设所给0 1背包问题的子问题 的最优值为m i j 即m i j 是背包容量为j 可选择物品为i i 1 n时0 1背包问题的最优值 由0 1背包问题的最优子结构性质 可以建立计算m i j 的递归式如下 南京信息工程大学计算机与软件学院 26 2020 4 20 intknapSack intn intc intw intv intm 6 N intx intjmax min w n 1 c for intj 0 i1 i jmax min w i 1 c for j 0 j w 1 m 1 c max m 1 c m 2 c w 1 v 1 南京信息工程大学计算机与软件学院 27 2020 4 20 traceback返回最优值 for inti 1 i n i if m i c m i 1 c x i 0 else x i 1 c c w i x n m n c 1 0 M 1 c 为最优解 eg n 5 c 10 W 2 2 6 5 4 V 6 3 5 4 6 南京信息工程大学计算机与软件学院 28 2020 4 20 算法复杂度分析 从m i j 的递归式容易看出 算法需要O nc 计算时间 当背包容量c很大时 算法需要的计算时间较多 例如 当c 2n时 算法需要 n2n 计算时间 南京信息工程大学计算机与软件学院 29 2020 4 20 小结动态规划法的定义 在求解问题中 对于每一步决策 列出各种可能的局部解 再依据某种判定条件 舍弃那些肯定不能得到最优解的局部解 在每一步都经过筛选 以每一步都是最优解来保证全局是最优解 这种求解方法称为动态规划法 南京信息工程大学计算机与软件学院 30 2020 4 20 适合于用动态规划法求解的问题具有以下特点 1 可以划分成若干个阶段 问题的求解过程就是对若干个阶段的一系列决策过程 2 每个阶段有若干个可能状态3 一个决策将你从一个阶段的一种状态带到下一个阶段的某种状态 4 在任一个阶段 最佳的决策序列和该阶段以前的决策无关 5 各阶段状态之间的转换有明确定义的费用 而且在选择最佳决策时有递推关系 即动态转移方程 南京信息工程大学计算机与软件学院 31 2020 4 20 动态规划设计都有着一定的模式 一般要经历以下几个步骤 1 划分阶段 按照问题的时间或空间特征 把问题分为若干个阶段 2 确定状态 将问题发展到各个阶段时所处的各种客观情况用不同的状态表示出来 3 确定决策并写出状态转移方程 因为决策和状态转移有着天然的联系 状态转移就是根据上一阶段的状态和决策来导出本阶段的状态 所以如果确定了决策 状态转移方程也就可以写出 南京信息工程大学计算机与软件学院 32 2020 4 20 4 寻找边界条件 给出的状态转移方程是一个递推式 需要一个递推的终止条件或边界条件 5 程序设计实现 动态规划的主要难点在于理论上的设计 一旦设计完成 实现部分就会非常简单 南京信息工程大学计算机与软件学院 33 2020 4 20 例题 数字三角形问题 738810277455265一个数字三角形宝塔 数字三角形中的数字为不超过100的正整数 现规定从最顶层走到最底层 每一步可沿左斜线向下或右斜线向下走 假设三角形行数 100 编程求解从最顶层走到最底层的一条路径 使得沿着该路径所经过的数字的总和最大 输出最大值 输人数据 由文件输入数据 文件第一行是三角形的行数N 以后的N行分别是从最顶层到最底层的每一层中的数字 南京信息工程大学计算机与软件学院 34 2020 4 20 如输入 5738 810 2774 45265 输出 30 南京信息工程大学计算机与软件学院 35 2020 4 20 分析 对于这一问题 很容易想到用枚举的方法 深度搜索法 去解决 即列举出所有路径并记录每一条路径所经过的数字总和 然后寻找最大的数字总和 这一想法很直观 很容易编程实现其程序如下 inta maxn maxn max n i j voidtry x y dep integer sum longint if dep n then ifsum maxthenmax sum exit try x 1 y dep 1 sum a x 1 y try x 1 y 1 dep 1 sum a x 1 y 1 main fori 1tondoforj 1toido从文件中读数据到a i j max 0 try 1 1 1 a 1 1 printf max 但是当行数很大时 当三角形的行数等于100时 其枚举量之大是可想而知的 用枚举法肯定超时 甚至根本不能得到计算结果 必须用动态规划法来解 南京信息工程大学计算机与软件学院 36 2020 4 20 用动态规划法解题 逆推法按三角形的行划分阶段 若行数为n 则可把问题看做一个n 1个阶段的决策问题 先求出第n 1阶段 第n 1行上各点 到第n行的最大和 再依次求出第n 2阶段 第n 3阶段 第1阶段 起始点 各决策点至第n行的最佳路径 设 f i j 为从第i阶段中的点j至第n行的最大的数字和 则 f n j a n j 1 j nf i j max a i j f i 1 j a i j f i 1 j 1 1 j i f 1 1 即为所求 南京信息工程大学计算机与软件学院 37 2020 4 20 definemaxn 100 char fname fileinputf intn i j inta maxn 1 maxn 1 f maxn 1 maxn 1 for i 1 i 1 i for j 1 jf i 1 j 1 f i j a i j f i 1 j elsef i j a i j f i 1 j 1 输出f 1 1 南京信息工程大学计算机与软件学院 38 2020 4 20 顺推法按三角形的行划分阶段 若行数为n 则可把问题看做一个n 1个阶段的决策问题 先求第2行各元素到起点的最大和 再依次求出第3 4 5 n 1 n到起点的最大和 最后找第n行的最大值设f i j 为第i行第j列上点到起点的最大和则f 1 1 a 1 1 f i 1 a i 1 f i 1 1 f i j max a i j f i 1 j 1 a i j f i 1 j 2 j imax f n 1 f n 2 f n n 即为所求 南京信息工程大学计算机与软件学院 39 2020 4 20 intn i j a maxn maxn f maxn maxn maxsum main f 1 1 a 1 1 for i 2 if i 1 j f i j a i j f i 1 j 1 elsef i j a i j f i 1 j maxsum 0 for i 2 imaxsumthenmaxsum f n i 输出 南京信息工程大学计算机与软件学院 40 2020 4 20 挖地雷 问题描述在一条公路上埋有若干堆地雷 每堆地雷有一定的数量 地雷堆的编号为1 2 N 例如 埋有地雷数量如下 81421733261517196此时 地雷的数量可用一维数组A N 表示 同时 给出地雷堆之间的联系 从第1堆开始 它指出挖了此堆之后 还可以选择继续往下挖 若存在多种方案 只能选择其中的一种 若没有任何后继的方案 则挖地雷结束 例如 可给出下面的关系 南京信息工程大学计算机与软件学院 41 2020 4 20 81421733261517196若从第1堆开始挖 首先得到8枚地雷 然后 下面有2种选择3 4 若选择3 则可挖到2枚 下面还可以继续挖 或选择4此时可挖到17枚 到此结束 总共可挖到8 17 25枚 或选择1 3 6 7 8 10此时可挖到74枚 但也可以从2开始挖 后选择2 3 6 7 8 10 则共可挖到14 26 15 17 6 80枚 但还不是最多的 最多的为5 6 7 8 10 此时共可挖到33 26 15 17 6 97枚 南京信息工程大学计算机与软件学院 42 2020 4 20 地雷堆之间的联系可用以下的数组表示 二维整数型数组R i j 表示 当R i j 1表示从i到j有通路 当R i j 0表示无通路 南京信息工程大学计算机与软件学院 43 2020 4 20 算法分析用动态规划求解 1由后往前查找 若从第n堆地雷开始挖 此时可能得到a n 枚地雷 若从第n 1堆地雷开始挖 此时有2种可能 n 1堆到n堆无联系 可由R n 1 n 判断 此时可挖a n 1 枚 n 1堆到n堆有联系 则可挖a n 1 a n 枚 一般情况 若从第i堆开始挖 根据关系R 找出i后面的所有联系 从中找出一个可挖最多地雷的作为联系 这样可得到最多的挖地雷数 2上面计算出从每个堆开始能挖到最多的地雷数 此时找出一个最大值即可 南京信息工程大学计算机与软件学院 44 2020 4 20 3算法流程 定义数据结构 整数型二维数组B N 2 B i 1 表示最多可挖地雷数 B i 2 向后连接 求从第i堆地雷开始挖的数量的算法 for i N i 1 i CMAX 0 H 0 for j i 1 jCMAX H j CMAX B j 1 B i 1 A i CMAXB i 2 H 南京信息工程大学计算机与软件学院 45 2020 4 20 找出最大值并找出挖的路径 CMAX 0 H 0 for i 1 iCMAX THEN H i CMAX B i 1 printf 最大可挖数量 d CMAX printf H while H0 H B H 2 printf h 南京信息工程大学计算机与软件学院 46 2020 4 20 动态规划 石子归并 题目描述在一个圆形操场的四周摆放着N堆石子 N 100 现要将石子有次序地合并成一堆 规定每次只能选取相邻的两堆合并成新的一堆 并将新的一堆的石子数 记为该次合并的得分 堆数N及每堆的石子数 20 1 选择一种合并石子的方案 做N 1次合并 得分的总和最小 2 选择一种合并石子的方案 做N 1次合并 得分的总和最大 南京信息工程大学计算机与软件学院 47 2020 4 20 输入数据 第一行为石子堆数N 第二行为每堆的石子数 每两个数之间用一个空格分隔 输出数据 从第一至第N行为得分最小的合并方案 第N 1行是空行 从第N 2行到第2N 1行是得分最大合并方案 每种合并方案用N行表示 其中第i行 1 i N 表示第i次合并前各堆的石子数 依顺时针次序输出 哪一堆先输出均可 要求将待合并的两堆石子数以相应的负数表示 南京信息工程大学计算机与软件学院 48 2020 4 20 输入输出范例 输入 44594 输出 459 4 8 59 13 9224 5 944 14 4 4 1822 石子堆数N每堆的石子数 输出数据 从第一至第N行为得分最小的合并方案 第N 1行是空行 从第N 2行到第2N 1行是得分最大合并方案 每种合并方案用N行表示 其中第i行 1 i N 表示第i次合并前各堆的石子数 依顺时针次序输出 哪一堆先输出均可 要求将待合并的两堆石子数以相应的负数表示 南京信息工程大学计算机与软件学院 49 2020 4 20 本题初看以为可以使用贪心法解决问题 但是事实上因为有必须相邻两堆才能合并这个条件在 用贪心法就无法保证每次都能取到所有堆中石子数最多的两堆 例如下面这个例子 6346542 南京信息工程大学计算机与软件学院 50 2020 4 20 例如下面这个例子 6346542如果使用贪心法求最小得分 应该是如下的合并步骤 第一次合并3465422 3合并得分是 第二次合并546545 4合并得分是9第三次合并96545 4合并得分是9第四次合并9699 6合并得分是15第五次合并15915 9合并得分是24总得分 5 9 9 15 24 62 南京信息工程大学计算机与软件学院 51 2020 4 20 但是如果采用如下合并方法 却可以得到比上面得分更少的方法 第一次合并3465423 4合并得分是7第二次合并765427 6合并得分是13第三次合并135424 2合并得分是6第四次合并13565 6合并得分是11第五次合并131113 11合并得分是24总得分 7 13 6 11 24 61 南京信息工程大学计算机与软件学院 52 2020 4 20 动态规划思路 阶段i 石子的每一次合并过程 先两两合并 再三三合并 最后N堆合并状态s 每一阶段中各个不同合并方法的石子合并总得分 决策 把当前阶段的合并方法细分成前一阶段已计算出的方法 选择其中的最优方案具体来说我们应该定义一个数组s i j 用来表示合并方法 i表示从编号为i的石头开始合并 j表示从i开始数j堆进行合并 s i j 为合并的最优得分 南京信息工程大学计算机与软件学院 53 2020 4 20 对于上面的例子来说 初始阶段就是s 1 1 s 2 1 s 3 1 s 4 1 s 5 1 s 6 1 因为一开始还没有合并 所以这些值应该全部为0 第二阶段 两两合并过程如下 其中sum i j 表示从i开始数j个数的和s 1 2 s 1 1 s 2 1 sum 1 2 s 2 2 s 2 1 s 3 1 sum 2 2 s 3 2 s 3 1 s 4 1 sum 3 2 s 4 2 s 4 1 s 5 1 sum 4 2 s 5 2 s 5 1 s 6 1 sum 5 2 s 6 2 s 6 1 s 1 1 sum 6 2 南京信息工程大学计算机与软件学院 54 2020 4 20 第三阶段 三三合并可以拆成两两合并 拆分方法有两种 前两个为一组或后两个为一组s 1 3 s 1 2 s 3 1 sum 1 3 或s 1 3 s 1 1 s 2 2 sum 1 3 取其最优s 2 3 s 2 2 s 4 1 sum 2 3 或s 1 3 s 2 1 s 3 2 sum 2 3 取其最优第四阶段 四四合并的拆分方法用三种 同理求出三种分法的得分 取其最优即可 以后第五阶段 第六阶段依次类推 最后在第六阶段中找出最优答案即可 南京信息工程大学计算机与软件学院 55 2020 4 20 由此得到算法框架如下 Forj 2tondo 枚举阶段 从两两合并开始计算 Fori 1tondo 计算当前阶段的n种不同状态的值 Fork 1toj 1do 枚举不同的分段方法 beginIfi k nthent i k modnelset i k 最后一个连第一个的情况处理 s i j 最优 s i k s t j k sum 1 3 sum i j 表示从i开始数j个数的和 end 南京信息工程大学计算机与软件学院 56 2020 4 20 小结 一 动态规划的实质是分治思想和解决冗余 因此它与分治法和贪心法类似 它们都是将问题的实例分解为更小的 相似的子问题 但是动态规划又有自己的特点 贪心法的当前选择可能要依赖于已经作出的选择 但不依赖于还未做出的选择和子问题 因此它的特征是由顶向下 一步一步地做出贪心选择 但不足的是 如果当前选择可能要依赖子问题的解时 则难以通过局部的贪心策略达到全局最优解 南京信息工程大学计算机与软件学院 57 2020 4 20 相比而言 动态规划则可以处理不具有贪心实质的问题 在用分治法解决问题时 由于子问题的数目往往是问题规模的指数函数 因此对时间的消耗太大 动态规划的思想在于 如果各个子问题不是独立的 不同的子问题的个数只是多项式量级 如果我们能够保存已经解决的子问题的答案 而在需要的时候再找出已求得的答案 这样就可以避免大量的重复计算 南京信息工程大学计算机与软件学院 58 2020 4 20 由此而来的基本思路是 用一个表记录所有已解决的子问题的答案 不管该问题以后是否被用到 只要它被计算过 就将其结果填入表中 比较感性的说 动态规划的思想是对贪心算法和分治法的一种折衷 它所解决的问题往往不具有贪心实质 但是各个子问题又不是完全零散的 这时候我们用一定的空间来换取时间 就可以提高解题的效率 南京信息工程大学计算机与软件学院 59 2020 4 20 二 动态规划的基本步骤动态规划算法通常用于求解具有某种最优性质的问题 在这类问题中 可能会有许多可行解 每一个解都对应于一个值 我们希望找到具有最优值 最大值或最小值 的那个解 设计一个动态规划算法 通常可以按以下几个步骤进行 1 找出最优解的性质 并刻画其结构特征 2 递归地定义最优值 3 以自底向上的方式计算出最优值 4 根据计算最优值时得到的信息 构造一个最优解 其中 1 3 步是动态规划算法的基本步骤 在只需要求出最优值的情形 步骤 4 可以省去 若需要求出问题的一个最优解 则必须执行步骤 4 此时 在步骤 3