算法:AOE网(Activity On edge Network)与关键路径简介

前面我们说过的拓扑排序主要是为解决一个工程能否顺序进行的问题,但有时我们还需要解决工程完成需要的最短时间问题。如果我们要对一个流程图获得最短时间,就必须要分析它们的拓扑关系,并且找到当中最关键的流程,这个流程的时间就是最短时间。

在前面讲了AOV网的基础上,来介绍一个新的概念。在一个表示工程的带权有向图中,用顶点表示事件,用有向边表示活动,用边上的权值表示活动的持续时间,这种有向图的边表示活动的网,称之为AOE网(Activity On edge Network)。由于一个工程,总有一个开始,一个结束,在正常情况下,AOE网只有一个源点一个汇点。

既然AOE网是表示工程流程的,所以就具有明显的工程属性。只有在某顶点代表的事件发生后,从该顶点出发的各活动才能开始。只有在进入某顶点的各活动都已经结束,该顶点代表的事件才能发生。

尽管AOV网和AOE网都是用来对工程建模的,但它们还是有很大的区别,主要体现在AOV网是顶点表示活动的网,它只描述活动之间的制约关系,而AOE网是用边表示活动的网,边上的权值表示活动持续的时间,如图7-9-3所示两图的对比。因此,AOE网是要建立在活动之间制约关系没有矛盾的基础之上,再来分析完成整个工程需要多少时间,或者为缩短完成工程所需时间,应当加快哪些活动等问题。

我们把路径上各个活动所持续的时间之后称为路径长度,从源点到汇点具有最大长度的路径叫关键路径,在关键路径上完成的活动叫关键活动。显然就图7-9-3的AOE网而言,开始->发动机完成->部件集中到位->组装完成就是关键路径,路径长度为5.5。

如果我们需要缩短整个工期,去改进轮子的生产效率,哪怕改动成0.1也无益于整个工期的变化,只有缩短关键路径上的关键活动时间才才可以减少整个工期长度。例如如果发动机制造缩短为2.5,整车组装缩短为1.5,那么关键路径就为4.5,整整缩短了一天的时间。

如果某项活动的最早开始时间和最晚开始时间一样,表示中间没有空隙,则此项活动就为关键活动。为此,我们需要定义以下几个参数。

1、事件的最早发生时间 etv(earliest time of vertex):即顶点vk 的最早发生时间。

2、事件的最晚发生时间 ltv(latest time of vertex):即顶点vk 的最短发生时间。也就是每个顶点对应的事件最晚需要开始的时间,超出此时间将会延误整个工期。

3、活动的最早开工时间 ete (earliest time of edge):即弧ak 的最早发生时间。

4、活动的最晚开工时间 lte (latest time of edge ):即弧ak 的最晚发生时间,也就是不推迟工期的最晚开工时间。

我们首先求得1和2,而 ete 本来是表示活动<vk, vj> 的最早开工时间,是针对弧来说的,但只有此弧的弧尾顶点vk的事件发生了,它才可以开始,因此ete = etv[k]。

而lte 表示的是活动<vk, vj> 的最晚开工时间,但此活动再晚也不能等vj 事件发生才开始,所以lte = ltv[j] - len<vk, vj> 。

最终,我们再来判断ete 和 lte 是否相等,相等意味着活动没有任何空闲,是关键路径,否则就不是。

现在来谈谈如何求etv 和 ltv。

假设我们现在已经求得顶点v0对应的 etv[0] = 0,顶点v1对应的etv[1] = 3, 顶点v2对应的etv[2] = 4, 现在我们需要求顶点v3对应的etv[3],其实就是求etv[1] + len<v1, v3> 与 etv[2] + len<v2, v3> 的较大值。显然 3+5 < 4+8, 得到etv[3] = 12, 如图7-9-5所示。

由此我们也可以得出计算顶点vk的最早发生时间即求etv[k]的公式是:

其中P[k] 表示所有到达顶点vk的弧的集合。比如图7-9-5的P[3]就是<v1, v3> 和 <v2, v3> 两条弧。len<vi, vk> 是弧<vi, vk>上的权值。

假如我们现在已经求得v9~ v5 顶点的ltv值,现在要求v4 的ltv 值,由邻接表可得到v4 有两条弧<v4, v6>, <v4, v7>,可以得到

ltv[4] = min(ltv[7] - 4, ltv[6] - 9) = 15,如图7-9-8所示。

可以发现,在计算ltv时,其实是把拓扑序列倒过来进行而已,因此可以得到计算顶点vk最晚发生时间即求ltv[k] 的公式是:

其中S[K]表示所有从顶点vk出发的弧的集合。比如图7-9-8的S[4] 就是<v4, v6>和<v4, v7>两条弧,len<vk, vj> 是弧<vk, vj> 上的权值。

具体代码分析参见《求解AOE网的关键路径》。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏顶级程序员

自己动手做一辆无人车!

我刚刚帮助我的朋友Kendrick完成了一个小的项目。我们制作了一个小汽车,你可以教会它怎么行驶,让它成为一辆小型无人车。我负责了所有的硬件和arduino软件...

4057
来自专栏大数据文摘

快问快答 | 助教带你学习数据科学(附答疑视频领取)

1442
来自专栏机器人网

技术猿 | ABB机器人在激光切割上的技术分析及案例分享

导读:随着汽车业、军工及重工等行业的飞速发展,这些行业中的三维钣金零部件和特殊型材的切割加工呈现小批量化、多样化、高精度化的趋势。工业机器人和光纤激光所组成的机...

3105
来自专栏花叔的专栏

最强坦克小游戏V2.0 强势发布

玩家可提早召回探险队,或等探险队自动归来,如果是自动归来所获得坦币会有加成,每次派遣归航时间0-24小时不等。

791
来自专栏一名叫大蕉的程序员

手把脚教你实现第一个在线预测系统No.21

本来呢,最近看了人类简史,想写一篇偏见相关的,思路还没整理好不好放出来,先写个技术的吧。最近真是忙成狗,搬职场,找房子租,参加各种各样的会议,还有开发任务,做屁...

24210
来自专栏阮一峰的网络日志

PhotoSynth:图像识别建模技术

PhotoSynth是微软公司从华盛顿大学购买来的一项技术,主要作用是通过平面照片自动建立空间模型,目前已经接近即将发布的前夕。 举例来说,游客来到上海,外滩...

35710
来自专栏FreeBuf

这下好了,家里的智能灯泡都会泄露数据了

近日,来自国外的研究人员提出了一种新的技术,可以从智能灯泡获取用户的数据。举个例子,研究人员能够从远处记录智能灯泡的亮度模式来获取用户的偏好。

903
来自专栏申龙斌的程序人生

如何在6-8小时之内读完300页的书?

Michigan大学的一位老师Paul N. Edwards写了一篇学术文章《How to Read a Book》,当前已经更新到v5.0版本,个人感觉好过另...

38610
来自专栏mwangblog

组块构建——《学习之道》(Barbara Oakley)读书笔记二

高质量的组块构成的神经模型,不仅能与我们钻研的学科产生共鸣,也能在其他学科或生活领域产生反响。

1852
来自专栏Crossin的编程教室

一道大数据习题

现在到处都说“大数据”,我也跟着标题党一下。今天要说的这个,还算不上大数据,只能说跟以前的习题相比,数据量略大了一点。 前阵子我们做了个抓取热映电影的程序。有个...

2906

扫码关注云+社区

领取腾讯云代金券