问题产生:
错误理解:
当前事件的最迟发生时间vl(i)的产生跟与之直接关联的后继事件j和中间活动<i,j>有关,如果要使当前事件发生的时间“最晚”,应当取集合{j}中产生的最大差值。
错误原因:
1. 对于“最迟”一词的片面理解。
2.从线性的角度思考,忽略了树状结构带给当前事件的复杂影响。
3.只考虑后继事件的影响,忽略了前驱事件的限制约束。
正确理解:
首先明确两点:
1. 根据事件的最迟发生时间的定义,首先要求得终点的最迟发生时间,按逆拓扑排序向源点回推,而终点的最迟发生时间等于终点的最早发生时间,说明最迟发生时间的产生是有前提条件的,受限于先前最早发生时间和关键路 径产生的背景约束。
2. 根据AOE网的性质,只有在进入某顶点的活动都已经结束,该顶点所代表的事件才发生,而一个事件可能通过多个活动与多个事件关联,说明事件的发展不是一味发散的,而是最终会合拢的相互约束的关系。
举例说明:
假设当前逆拓扑回溯到事件v5,vl(5)=7,忽略图中其他边和结点可能对结果的影响,单独取出v1,v2,v3,v5所构成的部分观察,无论是取max or min,都得出vl(2)=6,vl(3)=6,对于剩下的v1,事件v2活动a1,事件v3活动a2都与其有关 联,如果是取max,则选取的应当是v3路径,那么vl(1)=2,说明v1可以延迟2个单位后开始,但是验证v2可以发现 由此产生的影响会导致 a1,v2,a4发生延后,也就是说v1-v2-v5路径无法在v1-v3-v5按时完成时完成,根据前面提到的AOE网的性质,v5无法按时展开,导致v5后继结点的也会因此受到影响,各点的最早完成时间实际上已经发生变化,而最晚完成时间本身又是基于最早完成时间求得,这是相互矛盾的,说明max是不可取的。如果是min,这样得到的最晚完成时间很容易证明其兼容性,不会产生前面推导时出现的事件分流后汇聚的不和谐以及矛盾。(例子举的不是很好,主要想突出max的矛盾问题)
最终结论:
标签:vl,最小值,v2,v1,算法,v5,最迟,事件 From: https://www.cnblogs.com/YikesXavier/p/16748514.html