对关键路径定义的疑惑

qjing
  • 343

网上说:关键路径是aoe网中从源点到终点的最长路径
王道书上:


这个关键路径是1->3->2->5>6 总权值为27对吧。如果我把f权值改为20,此时按定义的说法1->3->5->6不是权值最大即关键路径了吗?但是我们其实可以绕过走f这条路径仍然可以遍历其他节点,这样子f这条路径显得就不关键了啊?

我参考了大话数据结构,感觉我的想法没有问题。换句话说,绕过f的其他路径仍然满足制约关系,而且整体工程时间还变少了。
大话数据结构:

回复
阅读 422
2 个回答

你好像觉得任一路径达到就完事了?
AOE是某点全部前置边都完成,才算达到该点啊。要达到5需要e、f都完成。

老实说,这些东西早都忘了,只是凭自己仅存的一点印象来说 …… 所以,如果说得不对请直接指出来。

关键路径是找的最大路径长度,目的是找到需要完成某项任务所需要的最小时间。举个例来说:

说明:
  1. 原图顶点不带字母,说起来感觉不爽,所以都前缀一个字母 V
  2. 为了描述得形象一点,路径长度用单位“天”来描述
  • 比如说,要达到 V2,就必须经过 a 和 b 两个活动,而 b 活动的前提是 c 活动;a 活动和 b、c 活动没有直接关系,可认为并行

    所以,要达到 V2,就至少需要 max(a, b + c) 天,也就是 max(3, 4 + 8) = 12 天,我们把它记为 V2X(不要在意为什么是 X,只是给个名字而已,虽然可能不标准,但能描述清楚)。

  • 同理,可以看出来 V3X = 8(不用解释了吧)
  • V5 则需要从两个路径中去判断,是 V5X = max(V2X + 6, V3X + 10) = 18,结果很神奇,两条路径都是 18 天,无差别,都可以选择。

接下来的情况就不细说了,直接给个图出来

image.png

节点右上的蓝色色就是到达此节点所需要的必要时间(即最大路径长度)。而蓝色的线条就是关键路径。只有一点,到 V5 那里两条路径(红色路径和紫色路径)无差别。所以一共有两条关键路径。两条关键路径可能增加了分析的复杂性,但结果是,完成工程需要 27 天。

关键路径的作用在于,路径上任意一个活动延期都会造成整体工期延后。而非关键路径则有一定的“伸缩性”。比如 a 活动最长可延期 11 天都不会影响到整体工期,但关键路径上的任意一个活动 (b, c, e, f, h) 只要延期,哪怕 1 天,就一定会造成工期延迟。

一般只要存在活动时间变化(路径长度变化)都应该重新计算关键路径。

  • 如果 b 活动延期,关键路径就会变成 c ⇒ b ⇒ e ⇒ h
  • 如果 a 延迟 15 天,关键路径就会变成 a ⇒ e ⇒ h
  • ……

所以,结论:关键路径是完成工程的最小完成时间。至于题主说的,绕过 f 会减少工程整体时间,应该是有算错。注意我们针对某个顶来来说,找的是进入此顶点的最大路径,因为路径表示活动依赖,必须要顺序完成

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
你知道吗?

宣传栏