关键路径的计算
从源点到汇点路径长度最长的路径为该project的关键路径,即关键路径可以保证全部路径的活动都可以完毕。
ok,再次进入我们的作业题:
例如以下图所看到的的AOE网(弧上权值代表活动的持续天数)
1)完毕此project最少所须要多少天?
2)哪些是关键活动,在图中表示出关键路径
我们先计算最早发生时间ve和最迟发生时间vl:
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
Ve | 0 | 5 | 6 | 12 | 15 | 16 | 16 | 19 | 21 | 23 |
Vl | 0 | 9 | 6 | 12 | 15 | 21 | 16 | 19 | 21 | 23 |
首先呢,编号1和编号10分别为该project的源点和汇点,我们规定最早发生时间ve(源点)=0,最迟发生时间vl(汇点)=ve(汇点)。那么这两个量该怎样计算呢,看图:
对于事件i来说,ve(i) = Max{ve(m) + dut(<m, i>)},vl(i) = Min{vl(j) – dut(<i, j>)};当中ve(m)代表i前一个事件的最早发生时间,dut(<m, i>)表示从m到i的持续时间,大家能够把它看成一个递归算法,一直调用ve(),直到ve(源点)为止,然后取其最大值,由于它要保证全部路径上的活动都能完毕;而最迟发生时间和前者一样,一直递归调用vl(),直到vl(汇点)为止,然后取其最小值就可以。
回到原题中对比例图能够非常快地得到表格所看到的内容。
我们再来看两个概念:e(i)和l(i),前者为活动ai 的最早可能開始时间,后者为活动ai的最迟同意開始时间。差别于前边的ve和vl,e和l为标识的是某活动的时间,而前者是某事件的时间。
假如从事件m到事件i的活动为af,则有e(f)=ve(m), l(f)=vl(i)–dut(<m,i>) ,即活动af的最早可能開始时间为其弧尾事件最早可能发生时间;最迟同意開始时间为其弧尾事件最迟发生时间与两个事件的持续时间之差。是不是感觉有点别扭,但仅仅要理解了这几个关键词也就非常easy看懂了。于是乎 e(k) = l(k)的活动就是关键活动 ,请看图表:
a1 | a2 | a3 | a4 | a5 | a6 | a7 | a8 | a9 | a10 | a11 | a12 | a13 | |
权 | 5 | 6 | 3 | 6 | 3 | 3 | 4 | 1 | 4 | 5 | 2 | 4 | 2 |
e | 0 | 0 | 5 | 6 | 6 | 12 | 12 | 15 | 15 | 16 | 19 | 16 | 21 |
l | 4 | 0 | 9 | 6 | 12 | 12 | 17 | 15 | 15 | 16 | 19 | 21 | 21 |
由图和前边计算的ve和vl能够得到各活动的e和l,如上表所看到的,则关键活动为a2,a4,a6,a8,a9,a10,a11和a13,所以完毕该project至少须要的天数d=6+6+3+1(4)+5(2)+2=23,该project的关键路径有两条,即1->3->4->5->7->9->10和1->3->4->5->8->9->10。
相关文章
- Intel:2020年实现“零能耗计算”
- 从美国云计算的五年发展看中国
- 【原创】开源Math.NET基础数学类库使用(02)矩阵向量计算
- 新计算 新网络 新旗舰:华为云C6实例首测
- VTK计算网格模型上的最短路径
- Java实现 蓝桥杯 算法提高 计算超阶乘(暴力)
- Java实现 蓝桥杯VIP 算法训练 最大值与最小值的计算
- Python实现计算圆周率π的值到任意位的方法示例
- 基层民警体验大数据、云计算、人工智能带来的巨变
- 自定义抽象类计算计算圆面积
- Python绘制拓扑图(无向图)、有向图、多重图。最短路径计算
- 王坚数博会演讲实录:“计算经济”是社会发展的新动力
- 程序员的算法趣题Q31: 计算最短路径
- Java计算两点间经纬度距离(两种方式)
- Atitit.基于时间戳的农历日历历法日期计算
- 【无人机】基于强化学习的多无人机移动边缘计算与路径规划研究(Matlab代码实现)
- 跳出数据计算拯救人工智能之自然法则
- 知识图谱 知识计算--- 本体推理 规则推理 路径计算 社区计算 相似图计算 链接预测 不一致检测
- 云计算-云平台-国产-华为-FusionSphere
- C#计算一个数的N次幂(包含负数)
- 每日一题:如何计算除去最高、最低工资的部门平均工资
- 量子笔记:量子计算 toy python implementation from scratch