当前位置:首页 >> 高中教育 >>

第二十一讲 图与动态规划算法


图 —— 关键路径

2008/05/27

Hu Junfeng

主要内容
? Floyd算法 ? AOV网与拓扑排序概念 ? AOE网与关键路径

Hu Junfeng

2

Floyd算法 Floyd算法 基本思想:
? 图采用邻接矩阵作为存储结构。把关系矩阵看成是没 有经过任何中间结点,直接可以到达的每一对顶点间 的最短路径的完整表示, ? 然后经过多次迭代,每次增加一个新的结点,在允许 这个结点作为中间结点的条件下,计算每一对顶点间 的最短路径的缩短变化, ? 直到把所有结点都考虑进去为止,结果得到每一对顶 点间的最短路径。

Hu Junfeng

3

数据结构
typedef struct{ AdjType *a[]; int *nextvex[]; 标值 */ }ShortPath; *a[]: 存放每对顶点间的距离(或最短路径长度) , 以关系矩阵作为其初始状态。 *nextvex[]:存放vi到vj最短路径上vi的后继顶点的下标值。以 保存全部最短路径的轨迹,
Hu Junfeng

/*存放每对顶点间最短路径长度 */ /*存放vi到vj最短路径上vi的后继顶点的下

4

例题
? 用Floyd方法求图G10各顶点间的最短路径长度。

Hu Junfeng

5

初始状态
? 0 50 10 ∞ 45 ∞? ? ∞ 0 15 ∞ 5 ∞? ? ? ?20 ∞ 0 15 ∞ ∞? A0 = ? ? ∞ 20 ∞ 0 35 ∞? ? ? ∞ ∞ ∞ 30 0 ∞? ? ? ? ∞ ∞ ∞ 3 ∞ 0? ? ?

? 0 1 2 ?1 4 ??1 1 2 ?1 4 ? ? 0 ?1 2 3 ?1 nex tvex 0 = ? ??1 1 ?1 3 4 ??1 ?1 ?1 3 4 ? ? ??1 ?1 ?1 3 ?1

?1? ?1? ? ?1? ? ?1? ?1? ? 5? ?
6

Hu Junfeng

Hu Junfeng

7

Hu Junfeng

8

代价分析
算法中初始化部分由一个循环组成,其中外循环运行n次, 内循环也运行n次,初始化部分的时间复杂度为O(n2)。 迭代生成最短路径长度矩阵A和路径矩阵nextvex的部分为 三重循环的嵌套,其时间复杂度为O(n3)。因此,Floyd算法 的时间复杂度为O(n3)。 空间代价是O(n2)。

Hu Junfeng

9

AOV网 网
? 顶点活动网络。每一个顶点代表一个活动。顶点 之间的有向弧代表活动之间的序关系。

Hu Junfeng

10

AOV网与拓扑排序概念 网与拓扑排序概念
? 对一个有向无环图G进行拓扑排序,是指将G中所有顶点 排成一个线性序列,使得图中任意一对顶点u和v,若<u, v> ∈E(G),则u在线性序列中出现在v之前。
C

? ABE CFGE ? ACFGBE ? CAFBGE

F G A

E B
Hu Junfeng

11

拓扑排序思想
(1)从AOV网中选择一个入度为0的顶点将其输出。 (2)在AOV网中删除此顶点及其所有的出边。 反复执行以上两步,直到所有顶点都已经输出为止, 此时整个拓扑排序完成;或者直到剩下的顶点的入度 都不为0为止,此时说明AOV网中存在回路,拓扑排序 无法再进行。

Hu Junfeng

12

拓扑排序算法
? 拓扑排序前,先调用findInDegree得到所有结点的入 度,然后将所有入度为0的顶点压栈 顶点压栈。 顶点压栈 ? 从栈顶取出一个顶点将其输出,由它的出边表可以得 到以该顶点为起点的出边,将这些边终点的入度减1 ,即删除这些边。 ? 如果某条边终点的入度为0,则将该顶点入栈。 ? 反复进行上述操作,直到栈为空。 ? 如果这时输出的顶点个数小于n,则说明该AOV网中 存在回路,否则,拓扑排序正常结束。
Hu Junfeng

13

采用邻接出边表表示: 采用邻接出边表表示: 增加一个indegree维度,存放各顶点的入度。

Hu Junfeng

14

AOE网 AOE网
? 如果在带权的有向图中,用顶点表示事件,用有 向边表示活动,边上的权值表示活动的开销,则 此带权的有向图称为边活动网 (Activity on edge 边活动网 network) ,简称AOE网。 网 ? 顶点表示一个事件。 ? 顶点的入边所表示该事件发生所需的的活动 ? 顶点的出边所表示当该事件发生后,后续的活动 都可以开展了。

Hu Junfeng

15

AOE网 AOE网
修围墙 16天 进材料 3天 盖房子 120天

开工

动工
拆迁 2年 打地基 40天

Hu Junfeng

16

关键路径
? AOE网中有些活动可以并行进行,所以完成整个工程的最短时 间是从开始顶点到完成顶点的最长路径长度 最长路径长度,路径长度为路径 最长路径长度 上各边的权值之和。把开始顶点到完成顶点的最长路径称为关 键路径。

关键路径是:1 -> 4 -> 3 -> 2, 关键路径长度为:2+7+6 = 15,

Hu Junfeng

17

几个相关的概念
? ee(j):事件 可能发生的最早时刻,它是从 到 的最长带权 路径长度。也代表了从vj出发的所有活动的最早开始时间 。 ? le(i):在保证不延误整个工期的前提下,事件vi 所允许发 生的最晚时刻。 ? 活动ak = < vi ,vj>的最早开始时间e(k) ? 活动ak = < vi ,vj>的最晚开始时间l(k) ? 源点:入度为0的顶点。 ? 汇点:出度为零的顶点。
Hu Junfeng

18

关键活动
关键活动就是e(k) = l(k)的活动。 l(k)-e(k)表示完成活动ak的时间余量,是在不延误工期的前 提下,活动ak可以延迟的时间。

关键活动是:a2,a4,a5。

Hu Junfeng

19

关键路径算法
(1) 输入e条弧<j,k>,建立AOE网的存储结构。 (2) 从源点v0出发,令ee(0)=0,求 ee(j) (3) 从汇点n-1出发,令le(n-1) = ee(n-1), 求 le(i) 0<=i<=n-2。 (4) 根据各顶点的ee和le值,求每条弧ak<vi,vj>的 最早开始时间e(k) = ee(i) 和 最晚开始时间l(k) = le(j) – weight (<vi,vj>), 其中e(k)=l(k)的为关键活动。 求关键路径是在拓扑排序的前提下进行的,不能进行拓扑排序 ,自然也不能求关键路径。
Hu Junfeng

1<=j<=n-1。

20

例子: 例子:

Hu Junfeng

21

算法分析: 算法分析:
设AOE网有n个顶点,e条边,在求事件可能的最早发 生时间及允许的最迟发生时间,以及活动的最早开始 时间和最晚开始时间时,都要对图中所有顶点及每个 顶点边表中所有的边结点进行检查,时间花费为 O(n+e),因此,求关键路径算法的时间复杂度为 O(n+e)。

Hu Junfeng

22

AOE网研究的问题 网研究的问题
? 完成整个工程至少需要多少时间 ? 哪些活动是影响工程的关键
1956年,美国杜邦公司提出关键路径法,并于1957年首先用 于1000万美圆化工厂建设,工期比原计划缩短了4个月。杜邦 公司在采用关键路径法的一年中,节省了100万美圆。

Hu Junfeng

23

作业: 作业:
? 考试复习。

Hu Junfeng

24


相关文章:
动态规划算法详解_图文
动态规划算法详解_理学_高等教育_教育专区。孙啸老师...值的三种选择决定了各矩阵元素之间的关系,如下图...1,1; (2)从(0,1)出发, 即从第 0 行...
动态规划算法入门、原理、应用_图文
因此动态规划算法中最重要的两个概念为状态状态转移 方程。 2.1 状态给定一...而对于 Fk 来讲, F1...FN 都是 Fk 的子问题:因为以第 k 项结尾的最长...
实验三动态规划求多段图问题
实验三动态规划求多段图问题_计算机软件及应用_IT/计算机_专业资料。算法设计与分析 实验项目 算法实验动态规划实验 一、实验目的 1. 掌握动态规划算法的基本思想 ...
动态规划算法举例分析
新闻网页贴吧知道音乐图片视频地图百科文库 ...(1)最优子结构 设计动态规划算法第一步骤通常是...也就是说, 对于每对顶点(i, j), 需要寻找从 i...
动态规划算法原理与应用
几个实例的分析, 研究了利用动态规划设计算法的具体...篇研究论文, 并出版了他的第一部著作《动态规划》...2.动态规划的基本思想一般来, 只要问题可以划分成...
算法设计与分析答案参考
2 c f 2 h 解: 4、用动态规划策略求解最长公共...下图所示的连通网络 G,用克鲁斯卡尔(Kruskal)算法求...A=(65,70,75,80,85,55,50,2) 解:第一个...
算法设计与分析考试题及答案
新闻 网页 贴吧 知道 音乐 图片 视频 地图 百科...二、综合题(50 分) 1.写出设计动态规划算法的主要...也就是贪心算 法并不从整体最优考虑,它所做出...
实验二 动态规划算法
网页 新闻 贴吧 知道 音乐 图片 视频 地图 文库 |...实验二 动态规划算法_计算机软件及应用_IT/计算机_...{ //x 数组用来存放是否第 i 个元素被装栽进来 ...
实验三动态规划算法实验
3.学会利用动态规划算 实验三一、实验目的 动态规划算法的应用 1.掌握动态规划算法的基本思想,包括最优子结构性质基于表格的最优 值计算方法。 2.熟练掌握分...
动态规划算法实现多段图的最短路径问题算法设计与分析...
j ? Us 初始值,uj第j段的最优值。 3.一般方法 1) 找出最优解的性质,并...二.实验内容 1.编程实现多段图的最短路径问题的动态规划算法2.图的数据...
更多相关标签: