AOE关键路径步骤+例题

这篇具有很好参考价值的文章主要介绍了AOE关键路径步骤+例题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、 基本概念

在带权有向图中,以顶点表示事件,以有向边表示活动,以边上的权值表示完成该活动的开销(如完成活动所需的时间),称之为用边表示活动的网络,简称AOE网(Activity On Edge NetWork)

AOE网具有以下两个性质

  1. 只有在某顶点所代表的事件发生后,从该顶点出发的各有向边所代表的活动才能开始;
  2. 只有在进入某顶点的各有向边所代表的活动都已结束时,该顶点所代表的事件才能发生
    另外,有些活动是可以并行进行的

在AOE网中仅有一个入度为0的顶点,称为开始顶点(源点),它表示整个工程的开始;也仅有一个出度为0的顶点,称为结束顶点(汇点),它表示整个工程的结束。

从源点到汇点的有向路径可能有多条,所有路径中,具有最大路径长度的路径称为
关键路径,而把关键路径上的活动称为关键活动

完成整个工程的最短时间就是关键路径的长度
eg1.
关键路径例题,打基础,算法,图论
图中,源点为V1,汇点为V4。从V1到V4有两条路径,2更长。故2为关键路径。长度为6


1.1 ve(k),e(i),vl(k),l(i)的定义

事件 v k v_k vk(结点)的最早发生时间设为 v e ( k ) ve(k) ve(k)。只有指向该结点的所有活动 a i a_i ai都完成后,才可发生事件 v k v_k vk

活动 a i a_i ai(边)的最早开始时间设为 e ( i ) e(i) e(i)。只有活动的弧头的时事件完成后,才可进行活动 a i a_i ai

事件 v k v_k vk最迟发生时间 v l ( k ) vl(k) vl(k)。它是指在不推迟整个工程完成的前提下,该事件最迟必须发生的时间。

活动 a i a_i ai最迟开始时间 l ( i ) l(i) l(i)。它是指该活动弧的终点所表示事件 v k v_k vk的最迟发生时间 v l ( k ) vl(k) vl(k)与该活动所需时间 a ( i ) a(i) a(i)之差。

活动 a i a_i ai的时间余量 d ( i ) = l ( i ) − e ( i ) d(i)=l(i)-e(i) d(i)=l(i)e(i),表示在不增加完成整个工程所需总时间的情况下,活动 a i a_i ai,可以拖延的时间。
若一个活动的时间余量为零,则说明该活动必须要如期完成, d ( i ) = 0 d(i)=0 d(i)=0 l ( i ) = e ( i ) l(i)=e(i) l(i)=e(i)的活动 a i a_i ai是关键活动

二、例题

关键路径例题,打基础,算法,图论

  1. 求最早发生时间
0 1 2 3 4
ve(k) 0 1 4 6
e(i) 0 0 1 4

e(i)通过ve(k)得出

  1. 若必须在6分钟之后结束
    求各个事件和活动的最迟发生时间
0 1 2 3 4
vl(k) 0 1 4 6
l(i) 2 0 1 4

三、求关键路径的步骤

思路:通过 d ( i ) = 0 d(i)=0 d(i)=0求得关键活动
d ( i ) = 0 d(i)=0 d(i)=0通过求ve()…等四个量得出
关键路径例题,打基础,算法,图论

关键路径例题,打基础,算法,图论
关键路径例题,打基础,算法,图论
关键路径例题,打基础,算法,图论

关键路径例题,打基础,算法,图论
关键路径例题,打基础,算法,图论文章来源地址https://www.toymoban.com/news/detail-771397.html

3.1关键活动、关键路径的特性

  • 若关键活动耗时增加,则整个工程的工期将增长
  • 缩短关键活动的时间,可以缩短整个工程的工期
  • 当缩短到一定程度时,关键活动可能会变成非关键活动
  • 可能有多条关键路径,只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期。只有加快那些包括在所有关键路径上的关键话动才能达到缩短工期的目的。

到了这里,关于AOE关键路径步骤+例题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 创建OneNET新版MQTT设备:实现远程控制单片机 为微信小程序与单片机通信打基础(微信小程序通信单片机前置任务)

    本项目教程总共分为四节 1.(当前文章)创建OneNET新版MQTT设备:为微信小程序与单片机通信打基础(微信小程序通信单片机前置任务) 2.ESP8266-01s入门:烧录AT固件与OneNET MQTT通信教程包含MQTT.fx1.7.1教程(微信小程序通信单片机前置任务) 3.物联网实践教程:微信小程序结合

    2024年02月04日
    浏览(79)
  • 关键路径——AOE-网

    与AOV-网有所不同,AOE-网是 以顶点存储事件 ,以 弧vi,vj表示活动 的 带权的有向无环图 , 权值表示活动vi,vj的持续时间 。一般的工程中除了 子工程之间存在着先决关系 外,每一项子工程或活动的完成都需要 特定时间 。各个子工程的完成时间参差不齐,为了统筹一个工程的

    2024年02月04日
    浏览(48)
  • AOE-网 关键路径

    关键路径:在AOE-网中,从始点到终点具有最大路径长度(该路径上的各个活动所持续的时间之和)的路径称为关键路径。 关键活动:关键路径上的活动称为关键活动。 关键路径可能不只一条,重要的是找到关键活动 事件Vi 的最早可能开始时间Ve(i) 是从源点V0 到顶点Vi 的最长

    2024年02月09日
    浏览(34)
  • 【数据结构】有向无环图(AOE-网)的关键路径(C语言)

    把用顶点表示事件,用弧表示活动,弧的权值表示活动所需要的时间的有向无环图称为 边表示活动的网 ,简称 AOE-网 。 在AOE-网中存在唯一的、入度为0的顶点,称为 源点 ;存在唯一的、出度为0的顶点,称为 汇点 。从源点到汇点的最长路径长度即为完成整个工程任务所需的

    2024年02月07日
    浏览(42)
  • 关键路径(算法笔记)

    本文内容基于《算法笔记》和官方配套练题网站“晴问算法”,是我作为小白的学习记录,如有错误还请体谅,可以留下您的宝贵意见,不胜感激。 顶点活动(AOV)网: 顶点表示活动,边集表示活动间的优先关系;AOV网常用来表示活动间的优先关系; 边活动(AOE)网: 顶点

    2024年02月04日
    浏览(36)
  • golang实现关键路径算法

    关键路径算法(Critical Path Method,简称CPM)是一种用于项目管理的技术,主要用于计算项目中的关键路径和关键活动。关键路径是指项目中的最长路径,决定了项目的最短完成时间。关键活动是指在关键路径上的活动,必须按时完成才能确保项目按计划完成。 关键路径算法通

    2024年02月03日
    浏览(38)
  • 贪心算法基础及leetcode例题

    参考 本质: 找到每个阶段的局部最优,然后去推导得到全局最优 两个极端: 常识很难: 很多同学通过了贪心的题目,但都不知道自己用了贪心算法,因为贪心有时候就是常识性的推导,所以会认为本应该就这么做! 套路: 贪心没有套路,说白了就是常识性推导加上举反例

    2023年04月20日
    浏览(73)
  • 算法基础(二)(共有30道例题)

    (一)数组 定义:数组是存放在连续内存空间上的相同类型数据的集合。数组可以方便的通过下标索引的方式获取到下标下对应的数据。 注意: (1)数组下标都是从0开始的。 (2)数组内存空间的地址是连续的。正是因为数组的在内存空间的地址是连续的,所以我们在删除

    2024年02月01日
    浏览(41)
  • 基础算法之搜素(bfs和dfs模板和例题)

    之前学习了暴力枚举策略,将所有可能的情况都枚举一遍以获得最优解,但是枚举全部元素的效率如同愚公移山,无法应付数据范围稍大的情形。 本节在暴力枚举的基础上介绍搜索算法,包括 深度优先搜索和广度优先搜索 , 从起点开始,逐渐扩大寻找范围,直到找到需要的

    2024年02月16日
    浏览(32)
  • 【数据结构】拓扑网络(AOE算法举例+源码)

    博主介绍:✌专研于前后端领域优质创作者、本质互联网精神开源贡献答疑解惑、坚持优质作品共享、掘金/腾讯云/阿里云等平台优质作者、擅长前后端项目开发和毕业项目实战,深受全网粉丝喜爱与支持✌有需要可以联系作者我哦! 🍅文末获取源码联系🍅 👇🏻 精彩专栏

    2024年02月22日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包