《算法设计与分析》第07章1.ppt

《《算法设计与分析》第07章1.ppt》由会员分享，可在线阅读，更多相关《《算法设计与分析》第07章1.ppt（119页珍藏版）》请在金锄头文库上搜索。

1、 7 1一般方法和基本要素7 2每对结点间的最短路径7 3矩阵连乘7 4最长公共子序列7 5最优二叉搜索树7 60 1背包7 7流水作业调度 第7章动态规划法 20世纪50年代初美国数学家R E Bellman 理查德 贝尔曼 等人在研究多阶段决策过程的优化问题时 提出了著名的最优化原理 principleofoptimality 把多阶段过程转化为一系列单阶段问题 创立了解决这类过程优化问题的新方法 动态规划 动态规划 dynamicprogramming 是运筹学的一个分支 是求解决策过程 decisionprocess 最优化的数学方法 应用领域 动态规划问世以来 在经济管理 生产调度

2、工程技术和最优控制等方面得到了广泛的应用 例如最短路线 库存管理 资源分配 设备更新 排序 装载等问题 用动态规划方法比用其它方法求解更为方便 动态规划法的实质也是将较大问题分解为较小的同类子问题 这一点上它与分治法和贪心法类似 但动态规划法有自己的特点 分治法的子问题相互独立 相同的子问题被重复计算 动态规划法解决这种子问题重叠现象 贪心法要求针对问题设计最优量度标准 但这在很多情况下并不容易 动态规划法利用最优子结构 自底向上从子问题的最优解逐步构造出整个问题的最优解 动态规划则可以处理不具备贪心准则的问题 7 1一般方法和基本要素 7 1 1一般方法 最优性原理指出 一个最优策略具有这样

3、的性质 不论过去状态和决策如何 对前面的决策所形成的状态而言 其余决策必定构成最优策略 这便是最优决策序列的最优子结构特性 7 1 2基本要素 一个最优化多步决策问题适合用动态规划法求解有两个要素 最优子结构特性和重叠子问题 7 1 3多段图问题 例7 1多段图G V E 是一个带权有向图 它具有如下特性 图中的结点被划分成k 2个互不相交的子集Vi 1 i k 其中V1和Vk分别只有一个结点 V1包含源点 source s Vk包含汇点 sink t 对所有边 E 多段图要求若u Vi 则v Vi 1 1 i k 每条边的权值为c u v 从s到t的路径长度是这条路径上边的权值之和 多段图问

4、题 multistagegraphproblem 是求从s到t的一条长度最短的路径 结点 结点集V被分成k 2个不相交的集合Vi 1 i k 其中V1和Vk分别只有一个结点 s 源结点 和t 汇点 段 每一集合Vi定义图中的一段 共k段 边 所有的边 u v 均具有如下性质 若 E 则若u Vi 则u Vi 1 即该边将是从某段i指向i 1段 1 i k 1 成本 每条边 u v 均附有成本c u v s到t的路径 是一条从第1段的源点s出发 依次经过第2段的某结点v2i 经第3段的某结点v3j 最后在第k段的汇点t结束的路径 该路径的成本是这条路径上边的成本和 多段图问题 求由s到t的最小成

5、本路径 多段图问题的多阶段决策过程 生成从s到t的最小成本路径是在k 2个阶段 除s和t外 进行某种决策的过程 从s开始 第i次决策决定Vi 1 1 i k 2 中的哪个结点在从s到t的最短路径上 1 最优性原理对多段图问题成立假设s v2 v3 vk 1 t是一条由s到t的最短路径 初始状态 s 初始决策 s v2 v2 V2 初始决策产生的状态 v2则 其余的决策 v3 vk 1相对于v2将构成一个最优决策序列 最优性原理成立 反证 若不然 设v2 q3 qk 1 t是一条由v2到t的更短的路径 则s v2 q3 qk 1 t将是比s v2 v3 vk 1 t更短的从s到t的路径 与假设矛

6、盾 故 最优性原理成立 即 是v2 v3 vk 1 t构成从v2至t的最短路径 2 向前处理 递推 策略求解设P i j 是一条从Vi中的结点j到汇点t的最小成本路径 cost i j 是这条路径的成本 1 向前递推式cost k t 02 递推过程 第k 1段c j t ECOST k 1 j 0 i k 2 l1 l2 lpi 1 t j Vi Vi 1 各递推结果第4段COST 4 9 c 9 12 4COST 4 10 c 10 12 2COST 4 11 c 11 12 5第3段COST 3 6 min 6 COST 4 9 5 COST 4 10 7COST 3 7 min 4 C

7、OST 4 9 3 COST 4 10 5COST 3 8 min 5 COST 4 10 6 COST 4 11 7第2段COST 2 2 min 4 COST 3 6 2 COST 3 7 1 COST 3 8 7COST 2 3 9COST 2 4 18COST 2 5 15第1段COST 1 1 min 9 COST 2 2 7 COST 2 3 3 COST 2 4 2 COST 2 5 16S到t的最小成本路径的成本 16 最小成本路径的求取记d i j 每一cost i j 的决策即 使c j p cost i 1 p 取得最小值的p值 例 d 3 6 10 d 3 7 10 d

8、 3 8 10d 2 2 7 d 2 3 6 d 2 4 8 d 2 5 8d 1 1 2根据d 1 1 的决策值向后递推求取最小成本路径 v2 d 1 1 2 v3 d 2 d 1 1 7 v4 d 3 d 2 d 1 1 d 3 7 10故由s到t的最小成本路径是 1 2 7 10 12 3 算法描述 结点的编号规则源点s编号为0 然后依次对V2 V3 Vk 1中的结点编号 汇点t编号为n 1 目的 使对cost和d的计算仅按n 1 n 2 1的次序计算即可 无需考虑标示结点所在段的第一个下标 算法描述 程序7 1 多段图的向前递推算法templatevoidGraph FMultiGra

9、ph intk int p 采用程序6 8的邻接表存储图G float cost newfloat n intq d newint n cost n 1 0 d n 1 1 for intj n 2 j 0 j floatmin INFTY for ENode r a j r r r nextArc intv r adjVex if r w cost v w cost v q v cost j min d j q p 0 0 p k 1 n 1 for j 1 j k 2 j p j d p j 1 delete cost delete d 算法的时间复杂度若G采用邻接表表示 总计算时间为 3

10、 向后处理 递推 策略求解设BP i j 是一条从源点s到Vi中的结点j的最小成本路径 BCOST i j 是这条路径的成本 1 向后递推式BCOST k t 02 递推过程 第2段c 1 j ECOST 2 j 各递推结果第2段BCOST 2 2 9BCOST 2 3 7BCOST 2 4 3BCOST 2 5 2第3段BCOST 3 6 min BCOST 2 2 4 BCOST 2 3 2 9BCOST 3 7 min BCOST 2 2 2 BCOST 2 3 7 BCOST 2 5 11 11BCOST 3 8 min BCOST 2 4 11 BCOST 2 5 8 10第4段BC

11、OST 4 9 min BCOST 3 6 6 BCOST 3 7 4 15BCOST 4 10 min BCOST 3 6 5 BCOST 3 7 3 BCOST 3 8 5 14BCOST 4 11 min BCOST 3 8 6 16第5段BCOST 5 12 min BCOST 4 9 4 BCOST 4 10 2 BCOST 4 11 5 16S到t的最小成本路径的成本 16 最小成本路径的求取记BD i j 每一COST i j 的决策即 使COST i 1 p c p j 取得最小值的p值 例 BD 3 6 3 BD 3 7 2 BD 3 8 5BD 4 9 6 BD 4 10

12、7 BD 4 11 8BD 5 12 10根据D 5 12 的决策值向前递推求取最小成本路径 v4 BD 5 12 10 v3 BD 4 BD 5 12 7 v2 BD 3 BD 4 BD 5 12 BD 3 7 2故由s到t的最小成本路径是 1 2 7 10 12 7 1 4多段图问题的应用实例 资源分配问题 例7 2 将n个资源分配给r个项目 已知如果把j个资源分配给第i个项目 可以收益N i j 0 j n 1 i r 求总收益最大的资源分配方案 问题 如何将这n个资源分配给r个项目才能使各项目获得的收益之和达到最大 转换成一个多段图问题求解 用r 1段图描述该问题 段 1到r之间的每个

13、段i表示项目i 结点 i 1时 只有一个结点 源点s V 1 0 当2 i r时 每段有n 1个结点 每个结点具有形式V i j 表示到项目i之前为止 共把j个资源分配给了前i 1个项目 j 0 1 n 汇点t V r 1 n 边的一般形式 0 j k n 1 i r成本 当j k且1 i r时 边赋予成本N i k j 表示给项目i分配k j个资源所可能获得的净利 当j n且i r时 此时的边为 该边赋予成本 指向汇点的边 注 并不是分给的资源越多 得到的净利就越大 问题的解 资源的最优分配方案由一条s到t的最大成本路径给出 改变边成本的符号 从而将问题转换成为求取最小成本路径问题 7 1

14、5关键路径问题 1 问题描述求一个带权有向无环图中两结点间的最长路径问题 关键路径问题是一个AOE网问题几个概念 事件活动持续时间源点汇点最短时间最长路径关键路径关键活动 2 最优子结构和重叠子问题 1 事件i的可能最早发生时间earliest i earliest 0 0earliest j max earliest i w i j a代表的活动是关键活动 3 关键路径算法 基本步骤 1 对有向图G进行拓扑排序 确认其是否为有向无环图 2 按拓扑次序计算earliest i 0 i 计算latest j earliest i 并检查latest j earliest i 是否等于w i j

15、从而确定关键活动 例7 3是AOE网络的一个例子 它代表一个包括11项活动和9个事件的工程 其中 源点0表示整个工程已经开始 汇点8表示整个工程结束 关键路径问题是一个带权有向无环图中源点0到汇点8的最长路径问题 即工程所需的最短时间 关键路径为 0 1 4 7 8长度为 19 例求AOE网的关键路径 关键路径上的活动都是关键活动 缩短非关键活动都不能缩短整个工期如a6缩短为1 则整个工期仍为8 又如a6推迟3天开始 或拖延3天完成 a6 6 均不影响整个工期 分析关键路径的目的是找出影响整个工期的关键活动 缩短关键活动的持续时间 常可以缩短整个工期 如a7缩短为1 则整个工期为7 此时 再缩

16、短任一关键活动均不能缩短整个工期 即在有多条关键路径时 缩短那些在所有关键路径上的关键活动 才能缩短整个工期 7 2 1问题描述 设G V E 是一个有n个结点的带权有向图 w i j 是权函数 每对结点间的最短路径问题是指求图中任意一对结点i和j之间的最短路径 7 2每对结点间的最短路径 分析 利用单源最短路径算法求解 计算n个结点的单源最短路径 时间复杂度 n3 利用动态规划策略求解将求解G中每对结点之间的最短路径问题转化成一个多阶段决策过程 决策什么 最优性原理对于该问题是否成立 7 2 2动态规划法求解 最优子结构设图G V E 是带权有向图 i j 是从结点i到结点j的最短路径长度 k是这条路径上的一个结点 i k 和 k j 分别是从i到k和从k到j的最短路径长度 则必有 i j i k k j 因为若不然 则 i j 代表的路径就不是最短路径 这表明每对结点之间的最短路径问题的最优解具有最优子结构特性 最优解的递推关系 重叠子问题 为了计算dk i j 时 必须先计算dk 1 i j dk 1 i k 和dk 1 i k dk 1的元素被多个dk的元素的计算共享 7 2