精华内容
下载资源
问答
  • 有几个基本的概念我们要先了解,在带权有向图中,顶点表示事件,有向边表示活动,以边上的权值表示活动的开销,比如完成活动所需要的时间。这样的网络称为用边表示活动的网络,也就是AOE网。 分清发生和开始 这里...

    在学习数据结构的过程中,我发现关键路径的中的概念取名使得第一印象让人容易产生误解,所以我用最通俗易懂的例子来解释解释这些概念的实际含义。

    基本概念——AOE网

    有几个最基本的概念我们要先了解,在带权有向图中,顶点表示事件,有向边表示活动,以边上的权值表示活动的开销,比如完成活动所需要的时间。这样的网络称为用边表示活动的网络,也就是AOE网。

    分清发生和开始

    这里要首先弄明白的是两个词,也就是后面要学到的概念中的 “发生” 和 “开始”。

    “发生”是针对于事件的,也就是图中的顶点。什么叫事件发生了呢?

    只有在指向该顶点的所有有向边对应的活动结束,该顶点所代表的事件才发生。

    举个例子,一个事件C,它仅被两条边a, b指向,仅当a,b两活动都完成时,事件C发生。

    “开始”是针对于活动的,也就是图中的边。

    只有在一个顶点所代表的事件发生后,从该顶点出发的所有边对应的活动才能开始。

    什么时候开始?即可以在事件一完成就立马开始接下来的活动,也可以推迟活动开始的时间。

    最早发生时间——VE

    到这里就已经能解释我们要说的第一个概念了,最早发生时间。

    我猜这里应该经常会有人有疑惑,为什么是最长的路径长度决定最早的发生时间?我越想要早发生不是越应该走短的路径吗?

    且听我说,摆脱困惑的重点是我们要和求最短路径的思路区分开,求最短路径是找尽可能短的路来保证路径长度最小,你只需要找出一条最短的路就行。但是在关键路径里,一个顶点是有多个前提的,只有前提的路径都走完,才能发生该顶点的事件,那么只有最长的路径走完,保证其余短的路都早已经走完,该事件才发生。

    我们前面说过,发生是针对于事件的,一个事件要发生,首先要指向它的活动都完成。一个事件C,被两个活动a,b指向,a活动的耗费时间是3, b活动的耗费时间是5。那么看下图,从开始到C事件的发生要多久呢?

    在这里插入图片描述
    是最大路径长度5,因为C事件发生的前提必须是a,b两活动完成(活动可同时进行),C事件只有等到b完成才发生,最早完成时间由耗时最久的路决定,所以这就是为什么要取最长路径长度。

    (我想吐槽这个命名,根本就没有什么最早,一个顶点的发生时间就只有一个,就是最长路径长。可能命名是为了和最晚发生时间对称吧。)

    所以求目标顶点最早发生时间的方法是:

    目标顶点的所有前提顶点(比如上图中C的前提顶点为A顶点和B顶点)的最早完成时间+对应的前提顶点到目标顶点的活动消耗 中的最大值。

    比如C的最早完成时间是: Max{ A的最早完成时间+A到C的活动消耗时间, B的最早完成时间+B到C的活动消耗时间}

    具体递推公式:

    1、ve(源点)=0
    2、ve(k) = Max{ ve{j} + Weight(j, k) }, j为k的任意前提顶点, Weight(j, k)表示<j, k>上的权值 。
    只要从源点开始一直递推到汇点(终点)就好了。

    最迟发生时间——VL

    最迟发生时间的定义是这样的:在不推迟整个工程完成的前提下,保证后继事件j能在其最迟发生时间vl(j)能够发生时,该事件最迟必须发生的时间。

    嚯!好家伙,自己的定义里套着自己,这一波套娃是真存心不想让人看懂。

    首先,我们要知道,汇点的最迟发生时间就是它的最早发生时间(可以理解为汇点的最早发生时间就是工期),求VL的过程我们是从汇点倒着推回去的。

    其次,为什么会有最迟发生时间呢?这是因为一个工程中,通常会存在某条路径耗时比其他路径久的多,所以耗时短的事件可以不必太早发生,也就是存在着缓冲时间。

    为了方便理解,我举一个数据大小相差较大的例子:
    在这里插入图片描述
    看看这个图,我在顶点上方写了它的最早发生时间,D是汇点,110是它的最早发生时间(也是最迟发生时间)。

    此时我们可以这样理解,如果在110天时工程必须完成,那么A事件最迟什么时候要发生?

    我们可以用110减去a活动用时,得到105,也就是说A事件最迟可以在第105天发生(一旦发生就要立刻开始a活动,否则将推迟整个工期),指向A的活动可以在第100天才开始。

    而A事件最早可以在第5天就发生(这里说最早才有意义了),最早第5天完成,但是可以推迟到第105天完成,中间差了100天了。

    同理可得B事件的最迟发生时间是第10天,它一刻也不能拖。

    这时候再回去看看最迟发生时间的定义,应该就可以理解了吧

    再刚刚举的例子里,AB事件是相互独立的,如果我再添加一个不独立的事件:
    在这里插入图片描述
    这个图中我添加了一个C顶点,它是B顶点的前提。我把已知的最迟发生时间用绿色笔迹写在了最早发生时间右边。一起看看C事件的最迟发生时间是多少吧。

    这里我们可以看到,和上图不同,C顶点有2个出度,也就意味着它影响着两个后继顶点。

    如果我们仍用上次的方法,用110-10得100,可以认为C事件最迟在第100天发生吗?

    仔细看看是不对的,B顶点的发生前提是C顶点要发生,如果C在第100天才发生,那么B事件等不了啊,B最迟在第10天就要发生,等到第100天干脆毁灭吧

    正确的做法应该是B事件的最迟发生时间减4天得第6天。由此可见,一个顶点的最迟发生时间其实是由它的后继节点所决定的,这也就解答了为什么我们要从汇点开始倒着往起点推。

    我想你也可以理解了为什么公式中使用的是 Min{} 取最小。就比如刚刚的例子,C有两个选择——第6天或者第100天,你必须得选最小的以保证你不会耽误任何后继节点的最迟发生。

    递推公式:

    vl(汇点) = ve(汇点)

    vl(k) = Min{ vl(j) - Weight(k, j) } ,k为j的任意前驱

    活动的最早开始时间——e和最迟开始时间——l

    这两个概念相比之前的就简单多了,首先,还记得我在一开始说的吗,“开始”是针对活动,也就是图中的边的概念。

    活动的最早开始时间,理解起来非常容易,边的起点事件一旦发生就立刻开始,就是最早开始时间了。

    公式:若边<k, j> 表示活动i,则有e(i) = ve(k)

    那最迟开始时间呢,这要和该边指向事件的最迟发生时间挂钩,假如在10点必须写完作业(事件),写作业(活动)要2小时,那最晚啥时候开始写作业呢?8点对吧,也就是边所指向的事件最晚发生时间 - 边对应的活动所需时间。

    公式: 若边<k, j> 表示活动i,则有l(i) = vl(j) - Weight(k,j)

    时间余量d

    d(i) = l(i) - e(i),即活动最迟开始时间与最早开始时间的差额,这代表着活动可以拖延的时间。如果一个活动的时间余量为0,就意味着该活动不能拖延时间,称为关键活动,必须立即完成,否则就将拖延整个工期。

    而时间余量为0的所有边连起来,就是关键路径了。

    要求时间余量d, 就要先求活动的最早开始时间e和最迟开始时间l,要求e和l就要先求事件最早发生时间ve和最迟发生时间vl。所以做题步骤就出来啦,最后来做一题试试看吧!
    在这里插入图片描述
    答案:
    在这里插入图片描述
    在这里插入图片描述
    最终得到的关键路径为(v1, v3, v4, v6)

    最后注意的几点:

    1、关键路径上的所有活动都是关键活动, 它是决定整个工程的关键因素,因此可以通过加快关键活动来缩短整个工期。但是也不能任意缩短,因为一旦缩短到一定的程度,该关键活动就可能变成非关键活动了

    2、网中的关键路径不唯一,对于有好几条关键路径的网,只加快其中某一条关键路径上的活动并不能缩短工期。只有加快存在于所有关键路径上的关键活动才能达到缩短工期的目的。

    写作不易 ,各位看官留个赞吧

    本文转载自知乎:Eee帆
    侵删
    链接:你一定看得懂的关键路径概念

    展开全文
  • 关键路径中最早/迟发生时间

    千次阅读 多人点赞 2021-01-06 17:17:35
    概念:在AOE网中,顶点表示事件,弧表示活动,权表示...1.事件Vi的最早发生时间ve(i):要找事件(即图中顶点)的最早发生时间只需找到开始事件V0到该事件的最长路径即可,可以看到这里V0到V4有两条路,V0->V1-&g

    概念:在AOE网中,顶点表示事件,弧表示活动,权表示活动持续的时间。一般求的是关键路径,而要求关键路径则要找到以下四个值

    • 1.事件Vi的最早发生时间ve(i)
    • 2.事件Vi的最迟发生时间vl(i)
    • 3.活动ai的最早发生时间e(i)
    • 4.活动ai的最迟发生时间l(i)
      例子:在这里插入图片描述

    求V4和a4的以上四个值(下面有全部活动和事件的参考)
    1.事件Vi的最早发生时间ve(i):要找事件(即图中顶点)的最早发生时间只需找到开始事件V0到该事件的最长路径即可,可以看到这里V0到V4有两条路,V0->V1->V4,权值为5,V0->V2->V4,权值为7,选其中最大的即为7,所以V4的最早发生时间为7天;

    2.事件Vi的最迟发生时间vl(i):最迟发生事件与上相反,要先找出最终事件的最长路径,为18,然后在减去从V8到V4中最长的路径,这里有V8<-V6<-V4,权值为11,V8<-V7<-V4,权值为11,得出最迟发生时间为18-11=7天,注意这里是要减去最长路径,也就是要找到最短的路径;

    3.活动ai的最早发生时间e(i):这里可以看到a4前面只有a1,所以活动ai的最早发生时间e(i)就是a1的值6(不包含自己的值);

    4.活动ai的最迟发生时间l(i):与事件Vi的最迟发生时间vl(i)相似,用最长路径18减去其中时间的最长路径,所以活动ai的最迟发生时间l(i)就是MIN(18-2-9-1,18-4-7-1)为6(包含了自己的值);

    以下为所有参考:
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    参考书籍:数据结构C语言版

    展开全文
  • AOE网活动的最早、最迟发生时间及关键路径问题

    万次阅读 多人点赞 2018-05-22 18:10:12
    上个学期学数据结构的时候有学到,这学期的离散数学又要考。。复习复习 有向图中,用顶点表示事件,用有向边表示活动之间开始的先后顺序,则称这种有向图为AOV(Activity On Vertex)网络;AOV网络可以反应任务完成...

    免费浏览请前往:https://zhuanlan.zhihu.com/p/337438327

    上个学期学数据结构的时候有学到,这学期的离散数学又要考。。复习复习

    有向图中,用顶点表示事件,用有向边表示活动之间开始的先后顺序,则称这种有向图为AOV(Activity On Vertex)网络;AOV网络可以反应任务完成的先后顺序(拓扑排序)。

    在AOV网的边上加上权值表示完成该活动所需的时间,则称这样的AOV网为AOE(Activity On Edge)网,如图: 

    如何求AOE网中各事件(节点)和各活动(边)的最早开始时间和最迟开始时间以及工程的关键路径?

    整个活动的完成时间是AOE图中从始点到终点的最长路径的长度,这条路径称为关键路径。关键路径上的活动称作关键活动。

    注意:关键路径不一定只有一条。

    1.最早发生时间:从前往后,前驱结点到当前结点所需时间,取最大值。

    如上图中的节点4有两个前驱结点(节点2和3),节点2到节点4的最早发生时间是a1+

    展开全文
  •   在思考这个问题之前,我们先来了解一下,在关键路径中,开始和发生有什么区别? 开始和发生   “发生”是针对于...最早发生时间   刚开始我也很疑惑,为什么是最长的路径长度决定最早的发生时间呢?难道不应该

      在思考这个问题之前,我们先来了解一下,在关键路径中,开始和发生有什么区别?

    开始和发生

      “发生”是针对于事件的,也就是图中的顶点。只有在指向该顶点的所有有向边对应的活动结束,该顶点所代表的事件才发生。

      举个例子,一个事件C,它仅被两条边a, b指向,仅当a,b两活动都完成时,事件C发生。

      “开始”是针对于活动的,也就是图中的边。只有在一个顶点所代表的事件发生后,从该顶点出发的所有边对应的活动才能开始。

    最早发生时间

      刚开始我也很疑惑,为什么是最长的路径长度决定最早的发生时间呢?难道不应该是越想要早发生就越应该走短的路径吗?

      后面我才明白,最短路径和关键路径根本不是一回事,求最短路径是找尽可能短的路来保证路径长度最小,你只需要找出一条最短的路就行。但是在关键路径里,一个顶点是有多个前提的,只有前提的路径都走完,才能发生该顶点的事件,那么只有最长的路径走完,保证其余短的路都早已经走完,该事件才发生。

      我们前面说过,发生是针对于事件的,一个事件要发生,首先要指向它的活动都完成。一个事件C,被两个活动a,b指向,a活动的耗费时间是3, b活动的耗费时间是5。那么看下图,从开始到C事件的发生要多久呢?
    在这里插入图片描述
      是最大路径长度5,因为C事件发生的前提必须是a,b两活动完成(活动可同时进行),C事件只有等到b完成才发生,最早完成时间由耗时最久的路决定,所以这就是为什么要取最长路径长度。

    最迟发生时间

      最迟发生时间的定义是这样的:在不推迟整个工程完成的前提下,保证后继事件j能在其最迟发生时间vl(j)能够发生时,该事件最迟必须发生的时间。

      首先,我们要知道,汇点的最迟发生时间就是它的最早发生时间(可以理解为汇点的最早发生时间就是工期),求VL的过程我们是从汇点倒着推回去的。

      其次,为什么会有最迟发生时间呢?这是因为一个工程中,通常会存在某条路径耗时比其他路径久的多,所以耗时短的事件可以不必太早发生,也就是存在着缓冲时间。

      我们来看一下下面这个例子,看看最迟发生时间是多少?
    在这里插入图片描述
      看看这个图,我在顶点上方写了它的最早发生时间,D是汇点,110是它的最早发生时间(也是最迟发生时间)。

      此时我们可以这样理解,如果在110天时工程必须完成,那么A事件最迟什么时候要发生?

      我们可以用110减去a活动用时,得到105,也就是说A事件最迟可以在第105天发生(一旦发生就要立刻开始a活动,否则将推迟整个工期),指向A的活动可以在第100天才开始。

      而A事件最早可以在第5天就发生(这里说最早才有意义了),最早第5天完成,但是可以推迟到第105天完成,中间差了100天了。

      同理可得B事件的最迟发生时间是第10天,它一刻也不能拖。

      这时候再回去看看最迟发生时间的定义,应该就可以理解了吧。

    时间余量

      d(i) = l(i) - e(i),即活动最迟开始时间与最早开始时间的差额,这代表着活动可以拖延的时间。如果一个活动的时间余量为0,就意味着该活动不能拖延时间,称为关键活动,必须立即完成,否则就将拖延整个工期。

      而时间余量为0的所有边连起来,就是关键路径了。

      要求时间余量d, 就要先求活动的最早开始时间e和最迟开始时间l,要求e和l就要先求事件最早发生时间ve和最迟发生时间vl。所以做题步骤就出来啦,最后来做一题试试看吧!
    在这里插入图片描述
    答案如下:
    在这里插入图片描述
    在这里插入图片描述
    最终得到的关键路径为(v1, v3, v4, v6)

    最后注意的几点:

    1、关键路径上的所有活动都是关键活动, 它是决定整个工程的关键因素,因此可以通过加快关键活动来缩短整个工期。但是也不能任意缩短,因为一旦缩短到一定的程度,该关键活动就可能变成非关键活动了

    2、网中的关键路径不唯一,对于有好几条关键路径的网,只加快其中某一条关键路径上的活动并不能缩短工期。只有加快存在于所有关键路径上的关键活动才能达到缩短工期的目的。

    展开全文
  • 关键路径:最早开始时间 计算方式:每个节点找它到下个节点的最大路径 具有最大路径长度的路径为关键路径。因为你得保证每个人都到场才能去看电影嘛,那你肯定得等到最后一个人到了才能走。图中就是v...
  • (1):根据各项活动的活动时间计算各个事件最早时间与最迟时间,并填入图中事件2-8相应位置。 (2):写出关键事件。 答:最早时间:从前往后计算; 最迟时间:从后往前计算。 关键事件:即开始时间和结束时间...
  • 数据结构AOE网关键路径问题,不算活动差,直接看事件最迟最早差,差为0的就是关键路径,这样做对么? 数据结构AOE网关键路径问题,不算活动差,直接看事件最迟最早差,差为0的就是关键路径,这样做对么?我做了几道...
  • 每次从队列中弹出一个结点作为当前结点进行处理,将其后继结点的入度减一,若为0则入队列,若当前结点的最早开始时间加上该结点到后继节点的路径时间大于后继节点原有的最早开始时间,则更新后继节点的最早开始时间...
  • 查询每天最早一次时间和最晚一次时间 mysql部分 left(str,10)是指str自动从左往右取10个字段 select xx,xx,MIN(datetime) as am,MAX(datetime) as pm from xxxx GROUP BY left(datetime,10); 后台判断比较时间 ...
  • 工作M的最迟开始时间为第23天(23+5=28,第28天要开始另外的工作了,所以最晚必须第23天开始),最早开始时间为第16天,所以总时差有7天。 最早完成工作M的时间是第21天,下次项目开始的最早是第25天,所以自由时差...
  • 1)一个点的最早/最晚时间是有公式或者技巧求出来的 2)一个活动的最晚开始几天不影响,或者一个活动可以耽搁的时间,是有公式计算的 3)关键路径为起点到终点权值加起来最大的路径 直接例题 首先,关键路径为最大...
  • 活动i的最早时间 = 头节点的最早时间; 活动i的最晚时间 = 尾节点的最晚时间 - 活动i的持续时间; 也就是将e(i)和l(i)转换到计算Event的ee值和le值上面去,这两个值就是最早时间和最晚时间,它们可以...
  • 关键路径法将项目分解成为多个独立的活动并确定每个活动的工期,然后用逻辑关系(结束-开始、结束-结束、开始-开始和开始结束)将活动连接,从而能够计算项目的工期、各个活动时间特点(最早最晚时间、时差)等。...
  • 最早截止时间有限(EDF)算法: 截止时间越早,优先级越高 最低松弛度优先(LLF)算法: 松弛度=完成截止时间-仍需运行时间-当前时间 松弛度越低优先级越高,当正在执行时有其他松弛度更低的进程进入队列也不会暂停当前...
  • 表结构如下: create talbe test ( id varchar2(20), val1 number, val2 number, val3 number, ...例如id为001的val1、val2、val3发生了变化,过一段时间又变回去了,我想选取出每次变化最开始的那一行
  • 书上求关键路径的时候利用了事件最早发生时间etv数组和事件最迟发生时间ltv数组,其中事件最迟发生时间ltv数组初始化为ltv[i]=etv[GL->numVertexes-1]。那假设有9个顶点,V8最后进栈(拓扑序列的最后一位),V9倒数...
  • etv:事件最早发生时间 ltv:事件的最晚发生时间 (再晚会耽误工期) 关键路径是源点到汇点权值最大的一条路径,这条路径决定了整个工期。关键路径上的关键活动的最早开始的时间和最晚开始的时间应该是相同的(etv...
  • C语言-AOE网与关键路径

    千次阅读 2020-07-16 15:54:56
    事件vi的最早发生时间ve(i):事件vi的最早发生时间是等待vi之前的所有活动都完成,所以ve(i)是从源点到vi的最长路径长度。起始点(源点)的最早发生时间为0。(vk是vi的前驱事件) 所以可以推出: ve(0) = 0;(源点...
  • Flink在流处理程序中支持不同的... 例如,如果应用程序在上午9:15开始运行,则第一个每小时处理时间窗口将包括在上午9:15到10:00之间处理的事件,下一个窗口将包括在上午10:00到11:00之间处理的事件,以此类推。 处理
  • JavaScript和HTML的交互是通过事件实现的。JavaScript采用异步事件驱动编程模型,当文档、浏览器、元素或与之相关对象...Netscape的事件捕获:不太具体的节点更接收事件,而具体的元素最后接收事件,和事件冒泡相
  • 根据 topo 中的值,按照从前向后的拓扑次序,依次求每个事件最早发生时间,循环几次,执行以下操作: ① 取得拓扑序列中顶点序号 k,k = topo[i] ② 用指针 p 依次指向 k 的每个邻接顶点,取得每个邻接顶点的...
  • AOE网活动和关键路径

    2011-07-04 20:36:05
    求出AOE网每个活动的最早开始时间和最迟开始时间;该工程完成的最早时间以及判断出那些是关键路径。
  • 某个数据库表中每个人对应许多条记录,每条记录对应一个时间,她想找到用一条语句找到最早时间和最近的时间两个记录(在规定时间段内),如下所示 name mdate cj 小芳 2005-8-2 58 小芳 2006-3-1 58 小芳 2007-3-12 60...
  • SQL SERVER找出最早最迟日期

    千次阅读 2010-08-17 16:51:39
    用max或min能找到SQL Sever的最早或最迟日期
  • 关键路径确定的过程

    千次阅读 2020-02-13 16:38:41
    关键路径的确定 从源点到汇点具有最大路径长度的...事件最早发生时间ve[k] 顺拓扑序列求,ve[i]=max{紧挨权值+ve[到此点前一点]},即5->8权值为3,6->8权值为5,则ve[8]=max{ve[5]+3,ve[6]+5} 事件的最迟发...
  • Flink事件时间处理和水印

    万次阅读 多人点赞 2017-09-22 16:57:18
    最近找到这个对事件时间处理和水印说的比较好的...如果您正在构建实时流媒体应用程序,则事件时间处理是您必须迟早使用的功能之一。由于在大多数现实世界的用例中,消息到达无序,应该有一些方法,您建立的系统了解消
  • js面试题

    千次阅读 多人点赞 2019-04-09 19:42:32
    中 href 属性,转换成 property 的时候需要通过转换得到完整 URL 一些 attribute 和 property 不是一一对应如:form 控件中 对应的是 defaultValue,修改或设置 value property 修改的是控件当前值,setAttribute...
  • 事件

    千次阅读 2016-07-25 22:33:07
    下述内容主要讲述了《JavaScript高级程序设计(第3版)》第13章关于“事件”。 JavaScript与HTML之间的交互式通过事件实现的。 事件,就是文档或浏览器...1. 事件冒泡事件冒泡(event bubbling),即事件开始时有具体
  • AOE 关键路径

    2012-09-16 20:27:20
    以边表示活动,以顶点表示事件的有向网称为AOE(activity on edge)网.AOE网是一个 有向无环图,权值表示活动持续的时间。可以用AOE网来估计工程完成的时间。由于工程 只有一个开始点和一个完成点,所以在无环路的...
  • JavaScript DOM事件事件捕获事件冒泡

    千次阅读 2020-09-08 09:31:17
    事件 在讲事件流之前,我们先来了解一下事件。 JavaScript与HTML之间的交互是通过事件来实现的。事件:就是文档或浏览器窗口中发生的一些特定的交互瞬间。...事件最早是在IE3和Netscape Navigator2 中出现的,当

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 379,404
精华内容 151,761
关键字:

事件的最早发生时间