从零开始学数据结构系列之第四章《关键路径之AOV网和AOE网》

作者：你好赵伟 | 2024-08-22 02:48:14

踩

如果不理解的话可以看以下视频，这个讲的十分的不错
光速学会关键路径

AOV网和AOE网

边活动（AOE）网： 顶点表示事件，边集（带权）表示活动，活动一般用时间表示，而事件可以比作中介状态（状态转移->动态规划），当旧活动都结束后才会激活事件以进行新活动；AOE网常用来表示工程的进行过程。

在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动需要的时间），称之为用边表示活动的网络，简称AOE网。

（1）在AOE网中仅有一个入度为0的顶点，称为开始顶点（源点），它表示整个工程的开始；

（2）也仅有一个出度为0的顶点，称为结束顶点（汇点），它表示整个工程的结束。
在这里插入图片描述
（1）只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始；

（2）只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生，另外有些活动是可以并行进行的。

简单来说：

那根据 aoe 网的定义来说的话，那我们拿上图开始类比

那我们拿这上面的 v 1、v2、v3、v4来比作它的事件，

而它的弧/权职，也就是活动一般所用时间的话，我们用 a 1、a2、a3、a 4来类比

我如果想要达成 v2条件的话，只用达成 v 1这种条件就可以了

那也就是说，我达成 v3事件（可以炒了）的同时需要完成，开始加上可以切了这两个步骤，也就是 v 1和 v2两个事件，也就是说，我要同时满足这两个条件之后呢，才能达到 v3这种条件

顶点活动（AOV）网： 顶点表示活动，边集表示活动间的优先关系；AOV网常用来表示活动间的优先关系；

（1）AOV网中的弧表示活动之间存在的某种制约关系。

（2）AOV网中不能出现回路。

1.若是从i到j有一条有向路径，则i是j的前驱，j是i的后继
2、若<i,j> 是网中有向边，则i是j的直接前驱，j是i的直接后继
3、AOV网中不允许有回路，因为如果有回路存在，则表明某项活动以自己为先决条件，显然不可能

简单来说，如下图所示

在这里插入图片描述
这就相当于表示活动以及优先关系，读小学之后（后继）就是中学，读中学前必须是要读小学（前驱）。你总不能读完中学读小学把（倒反天罡是吧），后面也是同样的道理

从定义上来看，很容易看出两种网的不同，AOV网的活动以顶点表示，而AOE网的活动以有向边来表示，AOV网的有向边仅仅表示活动的先后次序。纵观这两种网图，其实它们总体网络结构是一样的，仅仅是活动所表示的方式不同，因此可以猜想从AOV网转换成AOE网应该是可行的。

通常AOE网都是和关键路径联系在一起的，在AOE网中我们可以通过关键路径法来计算影响整个工期的关键路径，达到缩短工期的目的。在传统的AOV网中是没有表示活动时间的权值的，因此传统的AOV网无法估算工期，但是如果我们在AOV网中的活动结点上都标上时间属性，那么AOV网就可以完全转换为AOE网。

☁️ 以上就是所有内容，对大家有用的话点个关注！感谢大家！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/1014456