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

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


图 —— 关键路径

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


相关文章:
算法设计与分析-动态规划法
算法设计与分析 实验报告书实验名称: 算法实验-动态规划法 学 号: 2013210773 姓 名: 汪涛 实验时间: 2015 年 6 月 7 日 《算法分析与设计》实验报告 -1-...
动态规划算法举例分析
新闻网页贴吧知道音乐图片视频地图百科文库 ...(1)最优子结构 设计动态规划算法第一步骤通常是...也就是说, 对于每对顶点(i, j), 需要寻找从 i...
动态规划的很经典的教程
这样对图求最优路径就是动态规划问题 的求解。 二...也就是当前状态是前面状态的完美总结,现在与过去...就要用下面介绍的方法解决问题了: (1)模型匹配法:...
实验二 动态规划算法
实验二 动态规划算法_计算机软件及应用_IT/计算机_专业资料。计算机算法分析实验报告实验二 动态规划算法基本题一:最长公共子序列问题一、实验目的与要求 1、熟悉最长...
动态规划实验_算法分析与设计
动态规划实验_算法分析与设计_计算机软件及应用_IT/计算机_专业资料。动态规划实验 实验二:在Σ ={a,b,c}上定义乘法: a a b c 若 b c a b b b c c...
动态规划算法原理及应用
动态规划算法刘兴田(浙江工业大学 计算机学院 软件工程...篇研究论文, 并出版了他的第一部著作《动态规划》...2.动态规划的基本思想一般来说, 只要问题可以划分成...
动态规划算法入门
网页 新闻 贴吧 知道 音乐 图片 视频 地图 文库 |...动态规划算法入门 [例 1] 有一个 m*n 的棋盘,...第二章 旅游规划与开发... 62页 2下载券 大型...
动态规划算法示意图
B1 2 A 1 5 10 12 14 6 C1 9 3 D1 6 5 E 5 8 D2 10 2 B2 10 4 13 12 B3 11 C2 C3 图 6.1 1 第六章 动态规划 20 12 14 10 14 6 ...
动态规划算法
新闻网页贴吧知道音乐图片视频地图百科文库 ...动态规划算法_计算机软件及应用_IT/计算机_专业资料。...若一个矩阵连乘积的计算次序完全确定,也就是 该...
算法分析与设计实验二动态规划
2、实现矩阵连乘的动态规划算法 3、实现最长公共子序列的动态规划算法 4、实现电路布线的动态规划算法 5、实现 m=2 的流水线作业调度动态规划算法。 (任选一个...
更多相关标签: