数据结构 — 图 之 关键路径、关键活动 (文字表述)
发布日期:2021-06-30 19:49:34
浏览次数:3
分类:技术文章
本文共 469 字,大约阅读时间需要 1 分钟。
1、AOE网:
边表示活动的网络,边表示活动,顶点表示事件,当该事件发生了,就说明触发该事件发生的所有的活动已经完成。一个工程所需的最短时间 就是 完成从开始顶点到终止顶点的最长路径的长度。
2、关键路径:
关键路径就是从开始顶点到结束顶点之间 一条具有最长路径长度的路径。关键路径可能不止一条。
3、活动的early(i):
一个事件(顶点vi)的最早发生时间 -> 最长路径的长度 -> early(i)活动ai的最早开始时间 -> vi 是 ai 开始的前提 -> vi最早完成时间
4、活动的late(i):
活动(边ai)最迟开始时间 -> 不增加工程工期的前提下,最多推迟几天 -> late(i)活动ai最迟开始时间 -> 工期 -( 该活动所需的时间 + 之后活动所需的时间和)
5、关键活动:
满足early(i) = late(i) 的活动,这足以说明该活动的关键程度。
6、确定关键路径的算法:
1)early(i) 2)late*(i) 3)得出关键活动 4)删除非关键活动 5)得到一条从开始顶点到终止顶点的路径
转载地址:https://lipenglin.blog.csdn.net/article/details/50061357 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
能坚持,总会有不一样的收获!
[***.219.124.196]2024年04月17日 07时00分05秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Python鼠标点击图片,获取点击点的像素坐标
2019-04-30
路径规划(一) —— 环境描述(Grid Map & Feature Map) & 全局路径规划(最优路径规划(Dijkstra&A*star) & 概率路径规划(PRM&RRT))
2019-04-30
RRT算法(快速拓展随机树)的Python实现
2019-04-30
D*算法
2019-04-30
强化学习(四) —— Actor-Critic演员评论家 & code
2019-04-30
RESTful API
2019-04-30
优化算法(四)——粒子群优化算法(PSO)
2019-04-30
数据在Oracle中的存储
2019-04-30
轨迹规划 trajectory planning
2019-04-30
AGV自动导引运输车
2019-04-30
Trie树(字典树)
2019-04-30
COMP7404 Machine Learing——KNN
2019-04-30
COMP7404 Machine Learing——SVM
2019-04-30