【算法】基于AOE网的关键路径算法

梦里梦外; 2022-06-08 14:45 295阅读 0赞

这是图算法的最后一个比较重要的部分，就是关键路径。这里主要介绍手工求解的方法和思路，至于代码嘛，我自己在写我们学校OJ的时候虽然是可以AC的，但是经测试是有BUG的，so，就不拿出来献丑了~

什么是关键路径，关键路径有什么用呢？我又去抱了抱度娘的大腿，发现这个是杜邦公司发明的算法，是用来算工期的。在工程上，我们都很讨厌工程的延期，同时一个工程由分为很多的节点，我们不知道哪些节点决定着这个工程是否会延期，每一个部分有没有可以伸缩的时间，于是，这个用来计划工程的关键路径算法就诞生了。看来，数据结构的应用真的不仅仅局限于处理计算机本身的问题上，也应用到了工程中。

下面要解释一下AOE网，AOE是Activity On Edge的缩写，即活动在边上的网。是一个**有向带权图。图中的边表示活动，顶点表示事件。 **要注意与AOV网的区别，AOV是**有向不带权图，图中的顶点表示活动，边表示活动间的先后关系**。

在AOE网中还有几个需要解释的名词：

1、源点：在AOE网中，只存在一个入度为0的点，这个点叫源点。

2、汇点：在AOE网中，只存在一个出度为0的点，这个点叫汇点。

现在就可以说说什么叫关键路径了：从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径。关键路径上的活动叫做关键活动。

关键路径是图中的最长路径，同时也是这个工程完成的最短时间。关于这句话，我是这样理解的：画在工程图上的事件都不是可有可无的事件，活动也是如此，都是要执行的。但是，活动的时间有长有短，那么，把每个部分活动的最长者取出来，不就是整个工程的最短完成时间吗？这个就有点像水桶效应，判断一个水桶能装多少水，不是看组成这个水桶最长的木板，相反，是看最短的木板。同样，要判断一个工程完成的最短时间，不是看在这个工程中每一部分中的最小者，应该看其最大者，因为它们都是要执行的嘛~短的执行完，而长的没有，这个工程依然没有完成啊！所以应该关注图中的最长的路径。

对于关键路径，依然有几个名词，下面先做个列举，后面遇到了再说明：

1、事件的最早发生时间

2、事件的最迟发生时间

3、活动的最早发生时间

4、活动的最迟发生时间

下面就进入算法的正题了，我们直接看例题，根据这个例子，来走一遍关键路径算法。

比如我们要求下图的关键路径

![20171004114721816][]

S1：先对这幅图的顶点(即事件)进行[拓扑排序][Link 1]

排序序列为：V1 V2 V3 V4 V5 V6

S2：根据这个拓扑排序序列，求出事件的最早发生时间

事件的最早发生时间是指，触发这个事件开始的所有活动中最长的那个活动。(注意标蓝的那两个)

我们定事件V1(源点)的最早发生时间为0

V1    0

V2    V1+3 = 0 + 3 = 3

V3    V1 + 2 = 0 + 2 = 2

V4    max\{V2 + 2 , V3 + 4\} = max\{5 , 6\} = 6

V5    V2 + 3 = 6

V6    max\{V5 + 1 , V4 + 2 , V3 + 3\} = max\{7 , 8 , 5\} = 8

S3：推算出这幅图顶点(即事件)的**逆**拓扑排序序列

逆拓扑排序序列为：V6 V5 V4 V3 V2 V1

虽然逆拓扑的定义是从图中找到一个出度为0的顶点，但是我感觉某种程度上可以直接把拓扑序列逆过来。（有错的话欢迎指出~）

S4：根据逆拓扑排序序列，求出事件的最迟发生时间

事件的最迟发生事件是指，在不推迟整个工程完成的前提下，该事件最迟必须发生的时间。

汇点(V6)的最迟发生时间与最早发生时间相同，也就是8

V6     8

V5     V6 - 1 = 8 - 1 = 7

V4     V6 - 2 = 8 - 2 = 6

V3     min\{V4 - 4 , V6 - 3\} = min\{2 , 5\} = 2

V2     min\{V5 - 3 , V4 - 2\} = min\{4 , 4\} = 4

V1     min\{V2 - 3 , V3 - 2\} = min\{1 , 0\} = 0

可以发现，求事件的最迟发生时间时，是看某个顶点的出度，出度引申的，是这个事件的后继事件。我们是知道这些后继事件的最迟发生时间的，现在我们只需要将每一个后继的最迟发生时间减去其对应的，到达现在这个事件的代价，就可以得到一个序列，这个序列的元素可能是一个或多个(上面蓝色标注的是多个的情况，也就是说当前这个事件有多个后继)。

根据事件最迟发生时间的定义，为了不拖延工期，又要使得事件迟发生，是不是应该选择差比较小的呢？粗粗的想过去，如果选择差比较大的，事件是不是就会比较”早“发生呢？想象一下我们切木头，从后面往前切，是不是切的长度短，保留的就会比较多呢？这里也差不多意思。（这个真的是纯粹个人理解哈，为了是应对考试，可能不是十分合理）

S5：求每一个活动的最早发生时间

活动的最早发生时间就是引出这个活动的事件的最早发生时间。

Vx(早)表示某一个事件的最早发生时间

A = V1(早) = 0

B = V1(早) = 0

C = V2(早) = 3

D = V2(早) = 3

E = V3(早) = 2

F = V3(早) = 2

G = V4(早) = 6

H = V5(早) = 6

S6：求每一个活动的最迟发生时间