AOE专题

2023-12-30 01:50
文章标签 专题 aoe

本文主要是介绍AOE专题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一.AOE本质

每一个事件的发生表示以该事件相应的顶点为弧头所代表的活动完成,以该事件相应的顶点的弧尾的弧所代表的活动可以开始。

二.AOE举例

Ve:从始点开始到各顶点的最大(与本质联系)路径长度。

(从前往后,取最大值,Ve[0]=0即起始值为0)

Ve[j]=Max{Ve[i]+dis<i,j>}

Vl:在不推迟整个工期前提下,事件允许的最晚时间(从后往前,取小值,Vl[n]=Ve[n])

Vl[i]=Min{Vl-dis<i,j>}

      A B  C  D  E  F  G

Ve 0  3   2  6   7  5  10

Vl  0  3   3  6   7  6  10 

e:活动ai最早开始时间,边活动的最早开始时间=它的发出顶点的最早发生时间(e(i)=Ve(k))

l:活动最晚开始时间,为边的到达顶点的最晚发生时间 - 边的权值

(L(i)=Vl(j)-dis<Vk,Vj>)

e[k]=l[k]即为关键活动

关键路径为(a1,a4,a9)和(a2,a8,a9)

PS:

(1)只有减少所有关键路径上共有的关键活动的时间才可能缩短工期

(2)只有在不改变最关键路径的前提下减少关键活动的时间才能缩短工期(如下题真题)

此处的AOE有3条关键路径:bdcg、bdeh和bfh。只有关键路径上的活动同时减少时,才能缩短工期。

【解析】活动d的最早开始时间=该活动弧的起点所表示的事件(事件2)的最早发生时间=max{a,b+c}=max{3,12}=12。

活动d的最迟开始时间=该活动弧的终点所表示的事件的最迟发生时间 - 该活动用时。

图中关键路径=27=c+b+e+h(简单选择题就求出所有路径长度取max),

时间4的最迟发生时间=min{27-g}=min{27-6}=21,

活动d的最迟开始时间=21-d=21-7=14.

求关键路径例题

先求事件(点)的最早发生和最迟发生,再计算所有活动的最早和最迟发生时间。 

iV1V2V3V4V5V6V7V8
最早发生时间023713111617
最晚发生时间023713111617

最晚发生时间:首先直接将V8的最早发生时间17写进V8的最晚发生时间,然后看V7(17-1=16);接着看V6,而因为V6的出度有两处(V5和V8),而V5还没算,所以可以先康V5的(由于V5的出边为3,所以V5的最晚发生时间为16-3=13),再回来康V6(一条去往V5求得11,一条去往V8也求得11,取min所以V6最晚发生时间为11)。

后两条:活动V3->V5最早发生时间是V3时间的最早开始时间,活动V3->V5的最晚开始时间是V5的最晚发生时间-前路径长度。

如V2-V4的最晚开始时间=V4的最晚发生时间 - dis【V2,V4】

最后,时间余量(活动的最早开始时间=最晚开始时间)为0的活动即关键路径,即把V3-V4边删去后的三条路径都是关键路径。

求V1结点到各点的最短路径和距离:

注意:虽然(3)中删去的是V3-V4的边(只是指关键路径V1到V8中),(4)的V1到其他顶点的最短路径是可以包括V3-V4边的。

老实人的算法流程

事件k的最迟发生时间:在不推迟整个工程完成的前提下,该事件最迟必须发生的时间。

事件的最早发生时间:由这个事件所发出的活动的最早发生时间。

活动的最迟发生时间:事件的最迟发生时间减去以它为结束点的活动的持续时间。

这篇关于AOE专题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/551346

相关文章

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

音视频入门基础:WAV专题(10)——FFmpeg源码中计算WAV音频文件每个packet的pts、dts的实现

一、引言 从文章《音视频入门基础:WAV专题(6)——通过FFprobe显示WAV音频文件每个数据包的信息》中我们可以知道,通过FFprobe命令可以打印WAV音频文件每个packet(也称为数据包或多媒体包)的信息,这些信息包含该packet的pts、dts: 打印出来的“pts”实际是AVPacket结构体中的成员变量pts,是以AVStream->time_base为单位的显

专题二_滑动窗口_算法专题详细总结

目录 滑动窗口,引入: 滑动窗口,本质:就是同向双指针; 1.⻓度最⼩的⼦数组(medium) 1.解析:给我们一个数组nums,要我们找出最小子数组的和==target,首先想到的就是暴力解法 1)暴力: 2)优化,滑动窗口: 1.进窗口 2.出窗口 3.更新值 2.⽆重复字符的最⻓⼦串(medium) 1)仍然是暴力解法: 2)优化: 进窗口:hash[s[rig

hot100刷题第1-9题,三个专题哈希,双指针,滑动窗口

求满足条件的子数组,一般是前缀和、滑动窗口,经常结合哈希表; 区间操作元素,一般是前缀和、差分数组 数组有序,更大概率会用到二分搜索 目前已经掌握一些基本套路,重零刷起leetcode hot 100, 套路题按套路来,非套路题适当参考gpt解法。 一、梦开始的地方, 两数之和 class Solution:#注意要返回的是数组下标def twoSum(self, nums: Lis

数字电路专题:verilog 阻塞赋值和非阻塞赋值

verilog 阻塞赋值 和 非阻塞赋值 “=”阻塞赋值, ”<=”非阻塞赋值。阻塞赋值为执行完一条赋值语句,再执行下一条,可理解为顺序执行,而且赋值是立即执行; 非阻塞赋值可理解为并行执行,不考虑顺序,在 always 块语句执行完成后,才进行赋值。 如下面的阻塞赋值: //代码如下:module top(din,a,b,c,clk);input din;input clk;out

算法专题一: 双指针

目录 前言1. 移动零(easy)2. 复写零(easy)3. 快乐数(medium)4. 盛水最多的容器(medium)5. 有效三角形的个数(medium)6. 和为 s 的两个数字(easy)7. 三数之和(medium)8. 四数之和(medium) 前言 常见的双指针有两种形式,一种是对撞指针,一种是左右指针。 1. 对撞指针: ⼀般用于顺序结构中,也称左右指针。

《黑神话:悟空》专题合集MOD/修改器/壁纸/音乐/CG剧情

《黑神话:悟空》专题合集」 链接:https://pan.quark.cn/s/d67857f4e308 包含内容: 《黑神话:悟空》MOD合集 《黑神话:悟空》修改器(风灵月影) 《黑神话:悟空》壁纸合集 《黑神话:悟空》3小时CG完整剧情合集 4K120帧最高画质!国语 简中字幕 附:4K 结尾动画合集 ​​​国语 简中字幕 《黑神话:悟空》主题曲 《黑神话

2014暑假集训搜索专题

A - 漫步校园 Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u Submit Status Description LL最近沉迷于AC不能自拔,每天寝室、机房两点一线。由于长时间坐在电脑边,缺乏运动。他决定充分利用每次从寝室到机房的时间,在校园里散散步。整个HDU校园呈方形布局,可划

2014级寒假特训之并查集专题

Problem A: Double和XXZ的生日宴请 Time Limit: 1 Sec   Memory Limit: 128 MB Submit: 9   Solved: 7 [ Submit][ Status][ Web Board] [ Edit] [ TestData] Description Double 和 XXZ同一天生日,他们俩30岁生日那天,当年

算法_栈专题---持续更新

文章目录 前言删除字符中的所有相邻重复项题目要求题目解析代码如下 比较含退格的字符串题目要求题目解析代码如下 基本计算器II题目要求题目解析 字符串解码题目要求题目解析代码如下 验证栈序列题目要求题目解析代码如下 前言 本文将会向你介绍有关栈的相关题目:删除字符中的所有相邻重复项、比较含退格的字符串、基本计算器II、字符串解码、验证栈序列 删除字符中的所有相邻重复项 htt