首页 > 编程语言 >对于关键路径算法中最迟发生时间取最小值的理解

对于关键路径算法中最迟发生时间取最小值的理解

时间:2022-10-02 11:55:14浏览次数:53  
标签:vl 最小值 v2 v1 算法 v5 最迟 事件

问题产生:

错误理解:

  当前事件的最迟发生时间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

相关文章

  • 基础算法五大板块
    基础动态规划基础的DP题目,模板题等。基础图论基础的最短路,最小生成树,拓扑排序等算法基础数学基础数论基础字符串基础算法骗分必备......
  • python关于算法题的输入
    关于Python算法题的输入处理最近在准备蓝桥杯,打算报Python组,所以开始尝试用Python刷算法题。【python&ACM输入输出的处理:sys.stdin.readline().strip().split())】上......
  • 高级算法/数据结构
    AhoCorasick自动机用于多模式字符串匹配。可持久化线段树利用前缀和思想求区间第k小等不易直接求出的值。后缀数组Manacher求最长回文串。......
  • 【WSN定位】基于改进chan算法和talor算法实现多基站目标定位附matlab代码
    ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,matlab项目合作可私信。......
  • 【无人机】基于A星算法和B次样条实现危险模型实现无人机三维航迹规划附matlab代码
    ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,matlab项目合作可私信。......
  • 算法题目(1)
    题目1给定一个有序数组arr,代表坐落在X轴上的点给定一个正数K,代表绳子的长度返回绳子最多压中几个点?即使绳子边缘处盖住点也算盖住输入:第一行arr的size,k第二行arr......
  • LeetCode 斐波那契数算法题解 All In One
    LeetCode斐波那契数算法题解AllInOneFibonacciNumber斐波那契数最佳实践性能优化"usestrict";/****@authorxgqfrms*@licenseMIT*@cop......
  • 18 -- 排序算法之快速排序
         从中可以发现:每次以哪个数为基准,哪个数就能被放置在最终拍好顺序的正确位置,示意图中是以每组数中的最后一个数作为基准的,需要指出的是:基准的选择不是确定的......
  • 数据结构与算法【Java】08---树结构的实际应用
    前言数据data结构(structure)是一门研究组织数据方式的学科,有了编程语言也就有了数据结构.学好数据结构才可以编写出更加漂亮,更加有效率的代码。要学习好数据结构就......
  • AcWing 算法提高课 筛质数
    例题:1、求区间中的质数筛质数是O(n)或O(nloglogn)但是如果n很大,则会超时。 但是如果要筛[l,r]区间中的全部质数且l和r比较大,但是r-l比较小时。可以用O(nloglogn)......