4.7 关键路径算法 源点 起始点 v1 v4 v3 v2 v5 v6 v7 v8 v9 a1=6 a6=2 a3=5 a2=4 a5=1

Presentation on theme: "4.7 关键路径算法 源点 起始点 v1 v4 v3 v2 v5 v6 v7 v8 v9 a1=6 a6=2 a3=5 a2=4 a5=1"— Presentation transcript:

1 4.7 关键路径算法 源点 起始点 v1 v4 v3 v2 v5 v6 v7 v8 v9 a1=6 a6=2 a3=5 a2=4 a5=1
AOE网（Activity On Edge Network） 在带权的有向图中，用顶点表示事件，用边表示活动，边上权表示活动的开销（如持续时间），则称此有向图为边表示活动的网络，简称AOE网。 下图是有11项 活动，9个事件的AOE网，每个事件表示在它之前的活动已经完成, 在它之后的活动可以开始。 源点 起始点 v1 v4 v3 v2 v5 v6 v7 v8 v9 a1=6 a6=2 a3=5 a2=4 a5=1 a4=1 a7=9 a8=7 a9=4 a11=4 a10=2 汇点 结束点 2019/6/12

2 4.7 关键路径算法(cont.) 源点 起始点 v1 v4 v3 v2 v5 v6 v7 v8 v9 a1=6 a6=2 a3=5
AOE网的性质 只有在某个顶点所代表的事件发生后，从该顶点出发的各有向边代表的活动才能开始; 只有在进入某一顶点的各有向边代表的活动已经结束，该顶点所代表的事件才能发生； 表示实际工程计划的AOE网应该是无环的，并且存在唯一的入度为0的开始顶点（源点）和唯一的出度为0的结束点（汇点）。 源点 起始点 v1 v4 v3 v2 v5 v6 v7 v8 v9 a1=6 a6=2 a3=5 a2=4 a5=1 a4=1 a7=9 a8=7 a9=4 a11=4 a10=2 汇点 结束点 2019/6/12

3 4.7 关键路径算法(cont.) 源点 起始点 v1 v4 v3 v2 v5 v6 v7 v8 v9 a1=6 a6=2 a3=5
AOE网研究的主要问题： 如果用AOE 网表示一项工程，那么仅仅考虑各个子工程之间的优先关系还不够，更多地是关心整个工程完成的最短时间是多少，哪些活动的延迟将影响整个工程进度，而加速这些活动能否提高整个工程的效率，因此AOE网有待研究的问题是: (1)完成整个工程至少需要多少时间？ (2)哪些活动是影响工程进度的关键活动？ 源点 起始点 v1 v4 v3 v2 v5 v6 v7 v8 v9 a1=6 a6=2 a3=5 a2=4 a5=1 a4=1 a7=9 a8=7 a9=4 a11=4 a10=2 汇点 结束点 2019/6/12

4 4.7 关键路径算法(cont.) 源点 起始点 v1 v4 v3 v2 v5 v6 v7 v8 v9 a1=6 a6=2 a3=5
路径长度、关键路径、关键活动： 路径长度：是指从源点到汇点路径上所有活动的持续时间之和。 关键路径：在AOE网中，由于有些活动可以并行，所以完成工程的最短时间是从源点到汇点的最大路径长度。因此，把从源点到汇点具有最大长度的路径称为关键路径。 一个AOE中，关键路径可能不只一条。 关键活动：关键路径上的活动称为关键活动。 源点 起始点 v1 v4 v3 v2 v5 v6 v7 v8 v9 a1=6 a6=2 a3=5 a2=4 a5=1 a4=1 a7=9 a8=7 a9=4 a11=4 a10=2 汇点 结束点 2019/6/12

5 4.7 关键路径算法(cont.) Vj Vk ai 源点 起始点 v1 v4 v3 v2 v5 v6 v7 v8 v9 a1=6 a6=2
关键路径和关键活动性质分析-----与计算关键活动有关的量 ①事件Vj 的最早可能发生时间VE(j) 是从源点V1 到顶点Vj 的最长路径长度。 ②活动ai 的最早可能开始时间 E(i) 设活动ai 在边< Vj , Vk>上, 则E(i)也是从源点V1到顶点Vj 的最长路径长度。这是因为事件Vj发生表明以Vj为起点的所有活动ai可以立即开始。因此, E(i) = VE(j) …………..(1) Vj Vk ai 事件V5的最早发生时间 a1+a4=6+1=7 活动a7,a8的最早发生时间 E(7)=E(8)=6+1=7 源点 起始点 v1 v4 v3 v2 v5 v6 v7 v8 v9 a1=6 a6=2 a3=5 a2=4 a5=1 a4=1 a7=9 a8=7 a9=4 a11=4 a10=2 汇点 结束点 2019/6/12

6 4.7 关键路径算法(cont.) ai Vj Vk 关键路径和关键活动性质分析-----与计算关键活动有关的量
③事件Vk的最迟发生时间VL(k) 是在保证汇点Vn在VE(n)时刻完成的前提下，事件Vk的允许的最迟开始时间。 在不推迟工期的情况下，一个事件最迟发生时间VL(k)应该等于汇点的最早发生时间VE(n )减去从Vk到Vn的最大路径长度。 ④ 活动ai 的最迟允许开始时间 L(i) 是指在不会引起工期延误的前提下，活动ai允许的最迟开始时间。 因为事件Vk发生表明以Vk为终点的入边所表示的所有活动均已完成，所以事件Vk的最迟发生时间VL(k)也是所有以Vk为终点的入边< Vj , Vk>所表示的活动ai可以最迟完成时间。 显然，为不推迟工期，活动ai的最迟开始时间L(i)应该是Vk的最迟完成时间VL(k)减去ai的持续时间，即 L(i) = VL(k) - ACT[j][k] …………..( 2 ) 其中, ACT[j][k]是活动ai的持续时间（ < Vj , Vk>上的权）。 Vj Vk ai 2019/6/12

7 4.7 关键路径算法(cont.) 关键路径和关键活动性质分析-----与计算关键活动有关的量 ⑤时间余量 L(i) - E(i)
L(i) - E(i)表示活动 ai 的最早可能开始时间和最迟允许开始时间的时间余量。 关键路径上的活动都满足：L(i) = E(i) …………..( 3 ) L(i) = E(i)表示活动是没有时间余量的关键活动。 由上述分析知，为找出关键活动，需要求各个活动的E(i)与 L(i)，以判别一个活动ai是否满足L(i) = E(i)。 E(i)和L(i)可有公式 (1)和(2)计算得到。而VE(j) 和VL(j)可由拓扑排序算法得到。 AOE网可以用邻接矩阵或邻接表表示；矩阵中行下标i表示起点，列下标j表示终点，ACT[i][j]>0表示时间，ACT[i][j]=-1表示无边。 2019/6/12

8 4.7 关键路径算法(cont.) 关键路径和关键活动分析计算示例： a b c e g h k 6 4 5 2 1 8 7 d f 6 4 5 5 7 7 15 11 14 18 18 6 18 6 18 8 18 7 8 18 10 18 16 18 14 18

9 4.7 关键路径算法(cont.) a b c e g h k 6 4 5 2 1 8 7 d f 6 4 5 7 15 14 18 16
6 4 5 7 15 14 18 16 10 8 2 3

10 VE(j) = max{ VE(i)+ACT[i][j] }
4.7 关键路径算法(cont.) 利用拓扑排序算法求关键路径和关键活动 （1）前进阶段：计算VE[j]。从源点V1出发，令VE(1) = 0，按拓扑序列次序求出其余各顶点事件的最早发生时间: 其中T是以顶点Vj为尾的所有边的头顶点的集合(2≤j≤n) 如果网中有回路，不能求出关键路径则算法中止；否则转（2） j∈T VE(j) = max{ VE(i)+ACT[i][j] } VE=6 VE=12 VE=9 2 已知 VE=11? 14? 13? 求解 5 4 4 5 2019/6/12

11 VL(j) = min{ VL(i)-ACT[j][i] }
4.7 关键路径算法(cont.) 利用拓扑排序算法求关键路径和关键活动 （２）回退阶段：计算VL[j]从汇点Vn出发，令VL(n) = VE(n)，按逆拓扑有序求其余各顶点的最晚发生时间(用逆邻接矩阵ACT转置即可）： 其中S是以顶点Vj为头的所有边的尾顶点的集合(2≤j≤n-1) k∈S VL(j) = min{ VL(i)-ACT[j][i] } 7 6 5 VL=19 VL=24 VL=11 已知 VL=13? 17? 6? 求解 2019/6/12

12 L( i ) = VL( k ) - ACT[j][k] （４）若某条边满足E( i ) = L( i )，则它是关键活动。
求每一项活动ai的最早开始时间: 　　　　　　E( i ) = VE( j ) 求每一项活动ai的最晚开始时间: 　　　　　　L( i ) = VL( k ) - ACT[j][k] （４）若某条边满足E( i ) = L( i )，则它是关键活动。 为了简化算法, 可以在求关键路径之前已经对各顶点实现拓扑排序, 并按拓扑有序的顺序对各顶点重新进行了编号。 不是任意一个关键活动的加速一定能使整个工程提前。 想使整个工程提前，要考虑各个关键路径上所有关键活动。 2019/6/12

13 //运用拓扑有序计算出各事件最早发生时间 for(v=1;v<=n;v++) if(indegree[v]==0)
Enquque(v,Q);//入度为0的结点进队 while(!Empty(Q))//表明排队非空 {v=Q.vertex[Q.front]; Q.front++; for(i=1;i<=n;i++) if((ACT[i][v]>0)&&(VE[v]<ACT[i][v]+VE[i])) VE[v]=ACT[i][v] + VE[i]; for(j=1;j<=n;j++) if(ACT[v][j]>0) { w=j;//对于每一个邻接于v的结点 indegree[w]--;//删除由v出发的所有边 if(indegree[w]==0) Enqueue(w,Q);//入度为0的结点进队 } 2019/6/12

14 //运用逆拓扑有序计算出各个事件的最迟发生时间 //把每个事件的最迟发生时间都置为VE[n]，以作为它们的初值
for(i=0;i<=;i++) VL[i]=VE[9]; RQ.front=0; RQ.rear=-1;//将排队重新置为空 for(v=n;v>=1;v--) if(rindegree[v]==0) EnQueue(v,RQ);//入度为0的结点入队 while(!Empty(RQ))//表明排队非空 { v=RQ.vertex[RQ.front]; RQ.front++; for(i=n;i>=1;i--) if((RACT[i][v]>0)&&(VL[v]>VL[i]-RACT[i][v])) VL[v]=VL[i]-RACT[i][v]; 2019/6/12

15 for(j=n;j>=1;j--) if(RACT[v][j]>0) { w=j;//对于邻接于v的每一个结点 rindegree[w]--;//删除v发出的所有边 if(rindegree[w]==0) EnQueue(w,RQ);//入度为0的结点进队 } 2019/6/12

16 //求得并且输出各个活动的最早开始时间和最晚开始时间并且求出所求关键路径 int account=0;//记录活动的次数
for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(ACT[i][j]>0) { account++;//活动次数加1 cout<<"a"<<account<<" "; E[account]=VE[i]; L[account]=VL[j]-ACT[i][j]; if(L[account]-E[account]==0) cout<<" "<<i<<"--"<<j<<"critical activity"; cout<<endl; } 2019/6/12

17 本章小结 图 逻辑结构 存储结构 应用 深度优先搜索 广度优先搜索 图的遍历 比较 图的定义 基本术语 基本操作 邻接矩阵表示法
邻接表表示法 拓扑排序 最短路径 最小生成树 关键路径 图的遍历 2019/6/12