精华内容
下载资源
问答
  • 数据结构-关键路径

    2020-09-02 21:57:33
    (2)关键路径只有一条,关键活动也不是无限制缩短,工期会无限缩短的,因为可能缩到一定程度,这个节点就不是关键活动了。 求解关键路径的主要步骤: (1)求解ve(),求解每个节点(事件)的最早发生时间:规.

    AOV、AOE都是有权无向图,AOV边不带权值,AOE带权值。

    关键路径是AOE中,开始顶点到结束顶点的所有路径中,具有最大路径长度的路径成为关键路径,路径上的点是关键活动。

    (1)关键路径如果有多条,至提高一条关键路径上的关键活动并不能缩短工期,必须要加快所有关键路径上的关键活动才能加快工期。

    (2)关键路径只有一条,关键活动也不是无限制缩短,工期会无限缩短的,因为可能缩到一定程度,这个节点就不是关键活动了。

    求解关键路径的主要步骤:

    (1)求解ve(),求解每个节点(事件)的最早发生时间: 规定ve(0) = 0。 ve(n) = max(ve(n-1)+x1,ve(n-2)+x2) 能够到达n的所有路径中最大值。

    (2)求解vl(),求解每个节点(事件)的最迟发生时间:规定vl(终点)= ve(终点)。vl=min(vl(n-1)-x1,vl(n-2)-x2) 能够返回n的所有路径中的最小值。

    (3)求解e(),求解每个活动的最早开始时间。->活动a连接的两端的顶点的最早发生时间

    (4)求解l(),求解每个活动的最迟开始时间。->活动a连接的两端的终点的最迟发生时间-活动a历经的时间。

    (5)用e()-l(),找出等于0的点,等于0的路径就是关键路径。

    关键路径为:a2,a5,a7. v1->v3->v5->v6

                   

    20题。无需将所有步骤都完成,因为可以直接看出。最终选择C

                         

    21 ,求解ve(),vl() e() l () ,将e() - l () = 0 可以看出所有关键路径。因此有三条,最终选择C

                  

    展开全文
  • 关键路径

    千次阅读 2017-05-13 16:15:31
    AOE网对工程管理问题的表示: 在有向图中,如果顶点表示事件,有向边表示活动,有向边上的权值表示活动持续时间,这样的有向图...(2)AOV网的入度为0的顶点可以有多个,而AOE网入度为0的顶点只有一个; (3)AOV网的

    AOE网对工程管理问题的表示:

    在有向图中,如果顶点表示事件,有向边表示活动,有向边上的权值表示活动持续时间,这样的有向图称“边表示活动的网”即AOE网。如下图AOE网中,有10个事件,15个活动。


    AOE网对比AOV网:

    (1)AOV网的有向边不考虑权值,而AOE网的有向边考虑权值;

    (2)AOV网的入度为0的顶点可以有多个,而AOE网入度为0的顶点只有一个;

    (3)AOV网的出度为0的顶点可以有多个,而AOE网出度为0的顶点只有一个;

    (4)AOV与AOE网都不允许出现环路。

    AOE网具有如下性质:

    (1)只有在进入某一顶点的各条有向边代表的活动结束后,该顶点所代表的事件才能发生;

    (2)只有在某个顶点代表的事件发生后,从该顶点出发的各条有向边所代表的活动才能开始;

    (3)在一个AOE网中,有一个入度为0的事件,称源点,它表示整个工程的开始。同时,有一个出度为0的事件,称汇点,它表示整个工程的结束。

    AOE网的研究目标:

    (1)完成整个工程需要多少时间?

    (2)哪些活动是影响工程进度的关键?

    基本概念:

    路径长度:AOE网的一条路径上所有活动的总和称为该路径的长度。

    关键路径:在AOE网中,从源点到汇点的所有路径中,具有最大路径长度的路径称为关键路径。

    关键活动:关键路径上的活动称为关键活动。

    显然,完成整个工程的最短时间就是AOE网中关键路径的长度。

    必要说明:为什么最短时间是最大路径长度?

    拿上图说明,以事件v0为起点,0时开始(以秒为单位)。当时间过去5秒活动a1结束,事件v1发生,而此时,活动a2还差两秒才结束;再过3秒活动a3结束,但此时事件v3还不能发生,因为活动a4刚进行1秒还没有结束,必须再等5秒a4结束,事件v3才能发生。

    所以,可以得出某一事件的发生,最早也要等前面的所有活动中最消耗时间(即路径最长)的那个活动完成。

    当一个工程计划用AOE网表示后,所关心的问题就是如何找出关键路径上的关键活动,从而增加关键活动的投入,缩短关键活动持续时间,进而争取整个工程的提前完成。

    参数定义(假设有n个结点),并对上图AOE网进行计算:


    活动持续时间dut(<j,k>):代表有向边(活动)<j,k>的权值。

    事件可能的最早开始时间ve(k):对于顶点vk代表的事件,ve(k)是从源点到该顶点的最大路径长度。递推公式:ve(0)=0;ve(k)=Max{ve(j)+dut(<j,k>)},由公式,我们从源点v0正向计算。

    事件允许的最晚发生时间vl(k):对于顶点vk代表的事件,vl(k)是在保证按时完成整个工程的前提下,该事件最晚必须发生的时间。递推公式:vl(n)=ve(n);vl(k)=Min{vl(j)-dut(<k,j>)},由公式,我们从汇点v9反向计算。

    活动可能的最早开始时间e(i):对于有向边ai代表的活动,e(i)是该活动的狐尾事件可能的最早发生时间。

    活动允许的最晚开始时间l(i):对于有向边ai代表的活动,l(i)是该活动的弧头事件允许的最晚发生时间减去该活动持续的时间。

    每个活动允许的时间余量就是l(i)-e(i),而关键活动l(i)-e(i)=0,即可能的最早开始时间等于允许的最晚开始时间。

    对于上面的AOE网图,把求解的各参数陈述于下表中:

    事件 v0 v1 v2 v3 v4 v5 v6 v7 v8 v9
    ve(k) 0 5 7 13 17 18 23 22 26 31
    vl(k) 0 10 7 13 17 20 23 22 28 31
    活动 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14 a15
    e(i) 0 0 5 7 7 13 13 13 17 17 18 23 23 22 26
    l(i) 5 0 10 7 14 13 15 19 17 17 20 26 23 22 28
    由表1,整个工程需要的最少时间为ve(v9)=31。

    由表2,根据条件l(i)-e(i)=0,得到关键活动有a2,a4,a6,a9,a10,a13,a14;从源点v0到汇点v9的只要经过关键活动的路径就是关键路径,所以该图的关键路径为(v0,v2,v3,v4,v6,v9)和(v0,v2,v3,v4,v7,v9)。

    寻找关键活动的算法:

    (1)建立包含n+1个顶点(这样是为了方便n直接代表下标)、e条有向边的AOE网。其中,顶点v0为源点,顶点vn为汇点。

    (2)根据有向图的拓扑排序算法,求出AOE网的拓扑序列。如果存在环,拓扑序列不存在,则无法得到关键活动,算法失败退出。

    (3)从源点v0开始,令源点v0的最早开始时间为ve[0]=0,按拓扑序列求其余各顶点k(k=1,2,···,n)的最早开始时间ve[k]。

    (4)从汇点vn开始,令汇点vn的最晚发生时间vl[n]=ve[n],按逆拓扑序列求其余各顶点k(k=n-1,n-2,···,0)的最晚发生时间vl[k]。

    (5)计算每个活动的最早开始时间e[k]。

    (6)计算每个活动的最晚开始时间l[k]。

    (7)找出所有e[k]=l[k]的活动k,这些活动即为AOE网的关键活动。


    展开全文
  • 数据结构AOE网关键路径问题,不算活动...不对,这个只是图比较简单,或者关键路径只有一条时可以 如果关键路径并行的比较多,光计算顶点就不行了,只能一条一条弧(有向边)去检验 https://zhidao.baidu.com/question/

    数据结构AOE网关键路径问题,不算活动差,直接看事件最迟最早差,差为0的就是关键路径,这样做对么?

    数据结构AOE网关键路径问题,不算活动差,直接看事件最迟最早差,差为0的就是关键路径,这样做对么?我做了几道6,7个点的简单题,得出的结论是和计算活动时间差的答案一样。既然一样为什么要计算活动的时间差呢?

    不对,这个只是图比较简单,或者关键路径只有一条时可以
    如果关键路径并行的比较多,光计算顶点就不行了,只能一条一条弧(有向边)去检验

    https://zhidao.baidu.com/question/1992311184697397347.html

    展开全文
  • 项目关键路径

    2018-11-06 14:12:00
    项目关键路径,在项目管理中,关键路径是指网络终端元素的元素的序列,...对于个项目而言,只有项目网络中最长的或耗时最多的活动完成之后,项目才能结束,这最长的活动路线就叫关键路径(Critical Path),组成...

    项目关键路径,在项目管理中,关键路径是指网络终端元素的元素的序列,该序列具有最长的总工期并决定了整个项目的最短完成时间。关键路径的工期决定了整个项目的工期。任何关键路径上的终端元素的延迟将直接影响项目的预期完成时间(例如在关键路径上没有浮动时间)

     

    对于一个项目而言,只有项目网络中最长的或耗时最多的活动完成之后,项目才能结束,这条最长的活动路线就叫关键路径(Critical Path),组成关键路径的活动称为关键活动。其通常做法是:
      1) 将项目中的各项活动视为有一个时间属性的结点,从项目起点到终点进行排列;
      2) 用有方向的线段标出各结点的紧前活动和紧后活动的关系,使之成为一个有方向的网络图
      3) 用正推法和逆推法计算出各个活动的最早开始时间,最晚开始时间,最早完工时间和最迟完工时间,并计算出各个活动的时差;
      4) 找出所有时差为零或者为负数的活动所组成的路线,即为关键路径
      5) 识别出准关键路径,为网络优化提供约束条件;
      它具有以下特点:
      1)关键路径上的活动持续时间决定了项目的工期,关键路径上所有活动的持续时间总和就是项目的工期。
      2)关键路径上的任何一个活动都是关键活动,其中任何一个活动的延迟都会导致整个项目完工时间的延迟。
      3)关键路径上的耗时是可以完工的最短时间量,若缩短关键路径的总耗时,会缩短项目工期;反之,则会延长整个项目的总工期。但是如果缩短非关键路径上的各个活动所需要的时间,也不至于影响工程的完工时间。
      4)关键路径上活动是总时差最小的活动,改变其中某个活动的耗时,可能使关键路径发生变化。
      5)可以存在多条关键路径,它们各自的时间总量肯定相等,即可完工的总工期。
      关键路径是相对的,也可以是变化的。在采取一定的技术组织措施之后,关键路径有可能变为非关键路径,而非关键路径也有可能变为关键路径。

     

    转载于:https://www.cnblogs.com/wanglei-xiaoshitou1/p/9914981.html

    展开全文
  • AOE网络-关键路径

    千次阅读 多人点赞 2018-10-15 18:25:32
    拓扑排序的另一个应用就是关键路径的问题,关键路径对应的是另一种网络:AOE网络。...在关键路径这个问题中,AOE网络指的是“Activity On Edge”,即图上的每一条边表示的是一个活动,顶点作为各个“入度...
  • 给出个图,首先判断是否为有向无环图,如果是,则输出要求的边的最早发生时间和最晚发生时间,然后输出所有关键路径。 判断是否为有向无环图,可以用拓扑排序来判断。 二、分析 首先分析拓扑排序。使用邻接矩阵...
  • 关键路径算法

    千次阅读 2016-04-06 18:09:12
    关键路径的算法是建立在拓扑排序的基础之上的,这个算法中用到了拓扑排序,所以在这里先以拓扑排序开篇。 1. 什么是拓扑排序? 举个例子先:个软件专业的学生学习系列的课程,其中一些课程必须再学完它的基础...
  • 图——关键路径

    万次阅读 多人点赞 2019-04-02 09:10:27
    AOE网:在个表示工程的带权有向图中,用顶点表示事件(如V0),用有向边表示活动(如<v0,v1> = a1),边上的权值表示活动的持续时间,称这样的有向图为边表示的活动的网,简称AOE网(activity on edge ...
  • 关键路径详解

    千次阅读 2019-11-22 15:46:36
    关键路径算法是种典型的动态规划法,设图 G=(V, E) 是个 AOE 网,结点编号为 1,2,...,n ,其中结点 1 与 n 分别为始点和终点, ak=, j> ∈ E 是 G 的个活动。算法关键是确定活动的 最早发生时间v e[k] 和 最晚...
  • AOE网络与关键路径

    千次阅读 多人点赞 2014-04-07 00:24:12
    1、与AOV网络密切相关的是AOE网络。...2、由于整个工程只有一个开始点和个完成点,所以称开始点(入度为0)的点为源点,称结束点(出度为0)为汇点; 3、AOE网络在某些方面(如工程估算)非常有用,例如,
  • 关键路径计算

    万次阅读 多人点赞 2017-09-03 13:58:48
    计算关键路径,只需求出上面的四个特征属性,然后取e(i)=l(i)的边即为关键路径上的边(关键路径可能不止一条)。  先来看看四个特征属性的含义:  Ø  Ve(j):是指从始点开始到顶点Vk的最大路径长度 ...
  • AOE网、关键路径
  • 简单理解关键路径

    千次阅读 多人点赞 2020-03-03 20:40:09
    关键路径问题的相关概念 通常,个项目可以被拆分成多个子项目,多个子项目间会具有并行和串行的特点。 例如造汽车时,造发动机和造车轮是两个可以并行完成的任务,而组装整车又必须等发动机和车轮等部件完成后...
  • 这中类型的题是高级中比较常见的,系统分析... <br /> 在这种AOE网中 <br />最长的一条路径就是关键路径,因为图中每个活动都是必须的,只有最长的工期完成后,项目才真正完成了,图中10+9+20+10
  • 【笔记】AOE网与关键路径

    万次阅读 多人点赞 2017-12-02 01:06:32
    AOE网 关键路径关键路径的算法实现
  • 图论_关键路径

    千次阅读 2013-09-18 21:11:27
    一个下午的努力~~~~ ^_^ Description 关键路径的...另一个总工期比关键路径的总工期略少的一条并行路径被称为次关键路径。 最初,关键路径方法只考虑终端元素之间的逻辑依赖关系。关键链方法中增加了资源约束。
  • 图的关键路径

    千次阅读 2012-12-29 17:36:59
    摘 要 介绍求关键路经的算法,对于给出的事件结点网络,要求求出从起点到终点的所有路径,经分析、比较后找出长读最大的路径,从而得出求关键路径的算法,并给出计算机上机实现的源程序。 关键词 关键路径 最少时间...
  • 关键路径的确定

    千次阅读 2013-07-06 14:37:27
    项目管理与招标采购考前复习指导(73) ... ④关键路径的确定。...因此,关键路径就是网络图中由系列活动构成的活动工期最长的那路径,如果关键路径上的某项活动未如期完成,所有处于其后的
  • 7这红色的路径就是关键路径关键路径的特征是:从起点 (起点是唯一的,入度为0) 到终点 (终点是唯一的,出度为0) 的个有向图中,该路径上的弧 (有向图的边称之为“弧”) 的权重的和最大。关键路径可能不是唯一...
  • 关键路径JS实现

    2019-01-09 16:00:00
    我勒个去,毕业论文终于提交了,赶紧完成图基本算法的最后一节。。。 1 定义 ...由于个工程通常总有个开始和个结束,因此AOE网只有一个源点和汇点。 与AOV网区别在于,AOV网是顶点表示活动...
  • 关键路径与最短路径解析

    万次阅读 2016-02-29 16:25:12
    1.最短路径:如果从某顶点出发,这个顶点称为源点,经图的边到达另一顶点,这个顶点称为终点,所经过的路径不止一条,找出一条路径使的沿此路径上各边的权值之和为最小。(从源点到终点走得最短的路线权值之和)...
  • 5.4.4 关键路径

    千次阅读 2016-09-18 15:41:27
    在带权有向图中,以顶点表示时间,有向边表示活动,...②只有在进入某顶点的各有向边所代表的活动都已经结束,该顶点所代表的时间才能发生。 在AOE网中仅有个入度为0的顶点,称为开始顶点(源点),它表示整个工程
  • Project的关键路径、关键任务

    千次阅读 2019-12-07 14:07:44
    Project中网络图的关键路径 project功能很强大 ...上面这些均会自动生成,若过你的project突然不能显示关键任务关键路径了,不要慌,将你设置的完成百分比设回到0,然后你就会发现关键路径神奇的出来了 ...
  • C语言关键路径实现

    千次阅读 2017-01-22 11:07:57
    在工程中,要估算工程完成最短时间,就是要找到一条从源点到汇点的带权路劲长度最长的路径,成为关键路径。 确定关键路径的四个描述量: 1. 事件vi的最早发生时间ve(i): 进入世界vi的每一活动都结束,vi才有可...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 142,168
精华内容 56,867
关键字:

关键路径只有一条