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

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


图 —— 关键路径

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


相关文章:
动态规划讲解大全(含例题及答案)
(看词条图) 这种把一个问题看作是一个前后关联...动态规划算法解决这个问题,我们根据状态转移方程状态...在前面的例子中,第个阶段就是点 A,而第二个...
动态规划算法详解
动态规划算法详解_理学_高等教育_教育专区。孙啸老师...值的三种选择决定了各矩阵元素之间的关系,如下图...中的第个字符 A 已经与 t 中的 第二个字符 ...
动态规划的很经典的教程
这样对图求最优路径就是动态规划问题 的求解。 二...一个求最长非升子序列问题,显然标准算法动态规划...( 2 )为了方便操作可以将 a[n+1] 赋值为 -max...
算法分析与设计动态规划
规划方法解决问题的基本思想,学会如何问题化为多阶段图的方 法,并能对具体...实验单元动态规划 一实验题目实验二背包问题 二实验目的掌握动态规划算法求解...
动态规划算法示意图
第六章 动态规划 第六章 动态规划 Chapter 6 Dynamic Programming §6.1 引例例 6.1 最短路径问题 图 6.1 表示从起点 A 到终点 E 之间各点的距离。求 ...
动态规划实验_算法分析与设计
动态规划实验_算法分析与设计_计算机软件及应用_IT/计算机_专业资料。动态规划实验 实验二:在Σ ={a,b,c}上定义乘法: a a b c 若 b c a b b b c c...
动态规划算法
一、 实验题目 动态规划算法 二、 实验目的 1.掌握动态规划算法的基本方法 《...要求用导线(i,π(i)) 上端接线柱 i 与下端接线柱 π(i)相连, 如下图...
实验2动态规划算法
{ //从 i 的第二个数开始算起 //从第一个数开始算起 《 算法分析与设计...最后动态规划算法上课的时候老师讲过也进行分 析过所以比较容易理解也能运行...
动态规划算法入门、原理、应用
被打击了,问我动态规划算法了解吗,我一下就蒙了。...每件物品都有自己的价值 v 重量 w,物品 放入...设图 G 中 n 个顶 点的编号为 1 到 n 。令...
详细解释动态规划算法
动态规划避免了重复,对每一个子问题只解一次,而后其解 保存 在一个表格中,...第二句: 已经知道 Z 是 X 与 Y 的最长公共子序列, 倘若此时 X 与 Y 的...
更多相关标签:
动态规划算法视频讲解 | 动态规划算法讲解 | 动态规划算法 | 动态规划算法例题 | 01背包动态规划算法 | java动态规划算法 | 贪心算法 动态规划 | 动态规划算法基本步骤 |