十五分钟逐步掌握关键路径问题(时间余量、关键活动以及关键路径的求解)

本文主要是介绍十五分钟逐步掌握关键路径问题(时间余量、关键活动以及关键路径的求解),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

关键路径问题

名人说:莫听穿林打叶声,何妨吟啸且徐行。—— 苏轼《定风波·莫听穿林打叶声》
本篇笔记整理:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊)

目录

  • 关键路径问题
      • 〇、概念说明
        • 1、AOE网
        • 2、关键路径
        • 3、快速理解求解思路(个人心得)
      • 一、问题描述
      • 二、问题求解
        • ①求事件v最早发生的时间 ve(i)
        • ②求事件v最晚发生的时间 vl(i)
        • ③求活动a最早开始时间e(i)
        • ④求活动a最迟开始时间l(i)
        • ⑤求时间余量(d(i))
        • ⑥关键活动
        • ⑦关键路径
      • 三、扩展解法

以下内容,仅供学习交流,且仅在CSDN平台发布,未经授权禁止二次转发。

〇、概念说明

1、AOE网

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

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

2、关键路径

在AOE网中,有些活动是可以并行进行的。从源点到汇点的有向路径可能有多条,并且这些路径长度可能不同。完成不同路径上的活动所需的时间虽然不同,但是只有所有路径上的活动都已完成,整个工程才能算结束。因此,从源点到汇点的所有路径中具有最大路径长度的路径称为关键路径,而把关键路径上的活动称为关键活动

(以上概念参考自王道数据结构)

3、快速理解求解思路(个人心得)

求解关键路径时需要求解事件、活动早晚时间,自己总结了一些心得如下

  • 只要把事件的早晚时间算出来就可以,后面的可以省略的,因为活动的早晚是通过事件的早晚来求解的;
  • 活动早还是事件早(弧尾顶点对应的事件最早发生时间就是活动的最早发生时间),活动晚则是事件晚减去边权。

在了解了这些之后,我们来看一下下面的问题,逐步讲解(等后期练习多了之后,就没有那么繁琐了,可以在下面的例子中,重点体会一下我上面总结的心得),帮你加深理解。

一、问题描述

以2022统考真题为例

【2022统考真题】下面是一个有10个活动的AOE图,时间余量最大的活动是()
在这里插入图片描述

  • A.c
  • B.g(✔)
  • C.h
  • D.j

二、问题求解

该类问题的步骤简要来说为以下五步:

  • 1️⃣求事件v最早发生的时间 ve(i)正向、事件、顶点
  • 2️⃣求事件v最晚发生的时间 vl(i)逆向、事件、顶点
  • 3️⃣求活动a最早开始时间e(i)正向、活动、有向边
  • 4️⃣求活动a最迟开始时间l(i)逆向、活动、有向边
  • 5️⃣求时间余量d(i)l(i) - e(i)

其中

  • 正向表示:从源点到汇点,正向推导
  • 逆向表示:从汇点到源点,逆向推导
  • 事件表示:v
  • 活动表示:a
  • 顶点表示:图中各个顶点
  • 有向边表示:图中各个箭头有向边

✔ 补充:求时间余量其实就是求4和3的差值(用d(i)来表示),这个差值也就是该活动完成的时间余量。
如果时间余量为0,说明该活动是关键活动,没有缓冲延迟的时间,必须要如期完成。

接下来对以上五个步骤从上到下依次展开计算,具体如下:

①求事件v最早发生的时间 ve(i)

求所有事件的最早发生时间ve[i],按照拓扑排序序列,依次求各个顶点的ve;

设置ve[1]=0,ve[i]=Max {ve[j]+weight(vj,vi)},vj为vi的任意前驱,weight则表示<vj,vi>上的权值。

根据上面的AOE图,可得其拓扑排序序列为:1、2、3、4、5、6。
从源点到汇点顺着来推导事件(顶点)的最早发生事件ve。

ve(1) = 0

在这里插入图片描述

由图可以得出
ve(2) = 0+2 = 1

在这里插入图片描述

ve(3) = Max{ve(2)+1,ve(1)+5} = Max{3,5} = 5

依次类推,可得表格中所示数据:

123456
ve(i)0258912
②求事件v最晚发生的时间 vl(i)

求所有事件的最迟发生时间vl[i],按照逆拓扑排序序列,依次求各个顶点的vl;设置vl[汇点]=ve[汇点],vl[i]=Min {vl[j]-weight(vi,vj)},vi为vj的任意前驱。

根据①中所得的拓扑排序,可得逆拓扑排序序列为:6、5、4、3、2、1
从汇点到源点逆着来推导事件(顶点)的最晚发生时间vl。

vl(6) = ve(6) = 12
在这里插入图片描述
vl(5) = 12 - 1 = 11

在这里插入图片描述

vl(4) = Min {vl(5)-1,vl(6)-4}= Min{10,8} = 8

依次类推,最终可得:

123456
vl(i)04581112
③求活动a最早开始时间e(i)

求所有活动的最早开始时间e[i],若边<vi,vj>表示活动i,则有e[j]=ve[i]。
从源点到汇点推导活动(有向边)的最早发生时间e。
在这里插入图片描述

e(a) = ve(1) = 0
在这里插入图片描述

e(b) = ve(1) = 0
在这里插入图片描述

e(c ) = ve(2) = 2

依次类推,最终可得:

abcdefghij
e(i)0022555889
④求活动a最迟开始时间l(i)

求所有活动的最迟开始时间l,若边<vi,vj>表示活动i,则有l[i]=vl[j]-weight(vi,vj)。
从汇点到源点推导活动(有向边)的最晚发生时间l。

在这里插入图片描述

l(j) = vl(6) - 1 = 12 - 1 = 11
在这里插入图片描述

l(i) = vl(6) - 4 = 12 - 8 = 4

在这里插入图片描述

l(h) = vl(5) - 1 = 11 - 1 = 10

依次类推,最终可得l的值如下表:

abcdefghij
l(i)2045571110811
⑤求时间余量(d(i))

最后,让l(i)-e(i)得到d(i)
d(a) = l(a) - e(a) = 2 - 0 = 2
d(b) = l(b) - e(b) = 0 - 0 = 0

依次类推,即可得出我们要求的时间余量d:

abcdefghij
d(i)2023026202

整体表格如下:

abcdefghij
e(i)0022555889
l(i)2045571110811
d(i)2023026202

根据表格中所得,时间余量最大的活动是 g,余量为6

补充一下关键活动和关键路径,具体内容如下:

⑥关键活动
abcdefghi j
e(i)0022555889
l(i)2045571110811
d(i)2 0 2302620 2

根据关键活动的定义,可得关键活动有b、e、i,这些活动都是无法延迟进行的活动,必须如期进行。

⑦关键路径
abcdefghi j
e(i)0022555889
l(i)2045571110811
d(i)2 0 2302620 2

根据关键活动,可以画出关键路径如下:
在这里插入图片描述

那么问题来了,关于上面时间余量那一块的求解,有没有其它一些简便一些的算法呢?

自然是有的(但方法不能保证百分百正确率,存在一定的技巧性),可以看看以下的一种扩展解法,但是算法思路肯定不止这一种,大家可以集思广益在评论区分享一下!

三、扩展解法

扩展解法思路参考自一位博主写的408真题篇:2022 408真题数据结构篇,个人进行了改善。

可以借助贪心算法的思想来选择。

可以先找出里面最长的几条边构造关键路径,b=5、f=4、i=4、d=3、e=3,枚举到这里就差不多了,我们发现 b=5、e=3、i=4 已经能将起点终点连通了。

假设这就是起点到终点的最长路径,下面开始看看起点到终点的最短路径 a=2、c=1、g=1,我们可以观察到反差最明显的,就是路径3 -> 6 可以分解为3->4->6,g 的时间余量明显是很大的。

但是要注意的是,这种贪心解法高效,但是正确率并非 100%

  • 如果想保证正确率,第一种解法较为妥当;
  • 如果追求高效,可以从尝试一下贪心或者其它算法的求解方法。

以上就是本文的全部内容,感谢观看!

Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder)
点赞加关注,文章收藏不迷路!本篇文章对你有帮助的话,还请多多点赞支持!

这篇关于十五分钟逐步掌握关键路径问题(时间余量、关键活动以及关键路径的求解)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

MySQL主从同步延迟问题的全面解决方案

《MySQL主从同步延迟问题的全面解决方案》MySQL主从同步延迟是分布式数据库系统中的常见问题,会导致从库读取到过期数据,影响业务一致性,下面我将深入分析延迟原因并提供多层次的解决方案,需要的朋友可... 目录一、同步延迟原因深度分析1.1 主从复制原理回顾1.2 延迟产生的关键环节二、实时监控与诊断方案

SQLyog中DELIMITER执行存储过程时出现前置缩进问题的解决方法

《SQLyog中DELIMITER执行存储过程时出现前置缩进问题的解决方法》在SQLyog中执行存储过程时出现的前置缩进问题,实际上反映了SQLyog对SQL语句解析的一个特殊行为,本文给大家介绍了详... 目录问题根源正确写法示例永久解决方案为什么命令行不受影响?最佳实践建议问题根源SQLyog的语句分

解决IDEA报错:编码GBK的不可映射字符问题

《解决IDEA报错:编码GBK的不可映射字符问题》:本文主要介绍解决IDEA报错:编码GBK的不可映射字符问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录IDEA报错:编码GBK的不可映射字符终端软件问题描述原因分析解决方案方法1:将命令改为方法2:右下jav

Java controller接口出入参时间序列化转换操作方法(两种)

《Javacontroller接口出入参时间序列化转换操作方法(两种)》:本文主要介绍Javacontroller接口出入参时间序列化转换操作方法,本文给大家列举两种简单方法,感兴趣的朋友一起看... 目录方式一、使用注解方式二、统一配置场景:在controller编写的接口,在前后端交互过程中一般都会涉及

MyBatis模糊查询报错:ParserException: not supported.pos 问题解决

《MyBatis模糊查询报错:ParserException:notsupported.pos问题解决》本文主要介绍了MyBatis模糊查询报错:ParserException:notsuppo... 目录问题描述问题根源错误SQL解析逻辑深层原因分析三种解决方案方案一:使用CONCAT函数(推荐)方案二:

python处理带有时区的日期和时间数据

《python处理带有时区的日期和时间数据》这篇文章主要为大家详细介绍了如何在Python中使用pytz库处理时区信息,包括获取当前UTC时间,转换为特定时区等,有需要的小伙伴可以参考一下... 目录时区基本信息python datetime使用timezonepandas处理时区数据知识延展时区基本信息

Redis 热 key 和大 key 问题小结

《Redis热key和大key问题小结》:本文主要介绍Redis热key和大key问题小结,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、什么是 Redis 热 key?热 key(Hot Key)定义: 热 key 常见表现:热 key 的风险:二、

IntelliJ IDEA 中配置 Spring MVC 环境的详细步骤及问题解决

《IntelliJIDEA中配置SpringMVC环境的详细步骤及问题解决》:本文主要介绍IntelliJIDEA中配置SpringMVC环境的详细步骤及问题解决,本文分步骤结合实例给大... 目录步骤 1:创建 Maven Web 项目步骤 2:添加 Spring MVC 依赖1、保存后执行2、将新的依赖

使用Python实现矢量路径的压缩、解压与可视化

《使用Python实现矢量路径的压缩、解压与可视化》在图形设计和Web开发中,矢量路径数据的高效存储与传输至关重要,本文将通过一个Python示例,展示如何将复杂的矢量路径命令序列压缩为JSON格式,... 目录引言核心功能概述1. 路径命令解析2. 路径数据压缩3. 路径数据解压4. 可视化代码实现详解1

Spring 中的循环引用问题解决方法

《Spring中的循环引用问题解决方法》:本文主要介绍Spring中的循环引用问题解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录什么是循环引用?循环依赖三级缓存解决循环依赖二级缓存三级缓存本章来聊聊Spring 中的循环引用问题该如何解决。这里聊