本文主要是介绍AOE-网 关键路径,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
关键路径:在AOE-网中,从始点到终点具有最大路径长度(该路径上的各个活动所持续的时间之和)的路径称为关键路径。
关键活动:关键路径上的活动称为关键活动。
关键路径可能不只一条,重要的是找到关键活动
事件Vi 的最早可能开始时间Ve(i)
是从源点V0 到顶点Vi 的最长路径长度。
Ve(i) =Max{Ve(k)+wk,i}(k是i的前驱事件)
wk,i是弧<Vk,Vi>的权值,即活动持续时间
事件Vi 的最迟允许开始时间Vl(i)
Vl(i)不得迟于其后继事件Vj的最迟发生时间减去活动 <Vi,Vj>
Vl(i) = Min{Vl(j) - wi,j}
活动ak 的最早可能开始时间 e(k)
设活动ak 在边< Vi , Vj >上,
e(k) = Ve(i)。
活动ak 的最迟允许开始时间 l(k)
l(k)需要保证不会引起后继事件Vj的Vl(j)延误
l(k) =Vl(j) - wi,j
l(k) == e(k)表示活动ak 是没有时间余量的关键活动。
步骤:
(1)对AOE-网中的顶点进行拓扑排序,按拓扑序列求出Ve(i)
(2)按逆拓扑序列求出Vl(i)
(3)求出e(k)和l(k)
(4)找出关键活动,从源点到汇点由关键活动形成的路径即关键路径
- 计算Ve(i)
Ve(0)=0
Ve(1)=Max{Ve(0)+w0,1}=6
Ve(2)=Max{Ve(0)+w0,2}=4
Ve(3)=Max{Ve(0)+w0,3}=5
Ve(4)=Max{Ve(1)+w1,4,Ve(2)+w2,4}=7
Ve(5)=Max{Ve(3)+w3,5}=7
Ve(6)=Max{Ve(4)+w4,6}=16
Ve(7)=Max{Ve(4)+w4,7,Ve(5)+w5,7}=14
Ve(8)=Max{Ve(6)+w6,8,Ve(7)+w7,8}=18
- 计算Vl(i)
Vl(8)=Ve(8)=18
Vl(7)=Min{Vl(8) - w7,8}=14
Vl(6)=Min{Vl(8) - w6,8}=16
Vl(5)=Min{Vl(7) - w5,7}=10
Vl(4)=Min{Vl(6) - w4,6,Vl(7) - w4,7}=7
Vl(3)=Min{Vl(5) - w3,5}=8
Vl(2)=Min{Vl(4) - w2,4}=6
Vl(1)=Min{Vl(4) - w1,4}=6
Vl(0)=Min{Vl(1) - w0,1,Vl(2) - w0,2,Vl(3) - w0,3}=0
-
计算e(i)
e(a1)=Ve(0)=0
e(a2)=Ve(0)=0
e(a3)=Ve(0)=0
e(a4)=Ve(1)=6
e(a5)=Ve(2)=4
e(a6)=Ve(3)=5
e(a7)=Ve(4)=7
e(a8)=Ve(4)=7
e(a9)=Ve(5)=7
e(a10)=Ve(6)=16
e(a11)=Ve(7)=14 -
计算l(i)
l(a11)=Vl(8) - w7,8=14
l(a10)=Vl(8) - w6,8=16
l(a9)=Vl(7) - w5,7=10
l(a8)=Vl(7) - w4,7=7
l(a7)=Vl(6) - w4,6=7
l(a6)=Vl(5) - w3,5=8
l(a5)=Vl(4) - w2,4=6
l(a4=Vl(4) - w1,4=6
l(a3)=Vl(3) - w0,3=3
l(a2)=Vl(2) - w0,2=2
l(a1)=Vl(1) - w0,1=0
由上易知,关键活动为a1,a4,a7,a8,a10,a11
有两条关键路径(a1,a4,a7,a10),(a1,a4,a8,a11)
这篇关于AOE-网 关键路径的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!