关键路径(防止题目重复)

超、凢脫俗 2022-12-18 13:57 198阅读 0赞

DAG(Directed AcyclineGraph) 有向无环图  
用来描述一个工程或系统的进行过程。  
一个工程可以分为若干个子工程，只有完成了这些子工程，  
就可以导致整个工程的完成

怎么表示子工程（活动）？  
一种是用节点表示活动  
另一种使用便表示活动  
AOV网：拓扑排序  
顶点表示活动，弧表示活动之间的优先制约关系  
称这种有向图为顶点表示活动的网，简称AOV网(Activity On Vertex network)

AOE网：关键路径  
以弧表示活动，以节点表示活动的开始或结束事件，  
称为边表示活动的网，简称AOE网(Activity On Edge)

拓扑排序：

AOV网不允许有贿赂，若有贿赂，则表明某项活动以自己为先决条件，这是荒谬的

在AOV网中没有回路的奇纳提下，将全部活动排列成一个线性序列，  
使得若AOV网中有 弧<i, j>存在， 则这个序列中， i一定排在j的前面  
则有这种性质的线性序列称为 拓扑有序序列， 相应的拓扑有序排序的算法成为拓扑排序

如何判断AOV网是否存在回路？

拓扑排序的方法：

在有向图中选一个没有钱去的顶点 且 输出  
从图中删除该顶点和所有以他为尾的弧  
重复上述两部，知道全部顶点全部取出  
或者途中不存在无前驱的节点为止

关键路径

AOE网 弧表示活动 权表示时间 节点表示事件

例一：  
某项目的任务是对A公司的办公室重新装修  
如果10月1日前完成装修工程，项目最迟应该何时开始？

例二：  
准备宴会，晚六点开始，最迟几点开始准备？  
压缩哪项活动时间可以失踪事件减少？

关于AOE网，我们关心两个问题：  
（1）完成整项工程至少需要多少时间？  
（2）哪些活动是影响工程进度的关键？

关键路径——路径长度最长的路径（不唯一）  
关键路径上的活动是关键活动

4个描述量

ve(vj)——表示事件vj的最早发生时间  
ve(v1) = 0

vl(vj)——表示事件vj的最迟发生时间

e(i)——表示活动ai的最早开始时间  
l(i)——表示ai的最迟开始时间

l(i) - e(i) ——表示完成后动ai的时间余量  
关键活动——l(i) == e(i)

如何找关键活动？  
设活动ai用弧<j, k>表示，其持续时间记为:wj,k  
则有：  
活动的最早开始时间即为j的最早发生时间  
(1)e(i) = ve(j);  
活动的最晚开始时间等于k的最晚发生时间 - 活动的时间  
(2)l(i) = vl(k) - wj,k  
【注意】l(i) != vl(j);

如何求ve(j)和vl(j)？  
（1）  
从ve(1)==0开始  
ve(j) = max(ve(i) + wi, j)  
一个顶点的做早开始时间就是 从上一个顶点（可能有好几个）  
的最早开始时间 + 弧的权值 的最大值（得等所有的活动都完成）  
（2）  
从vl(n) = ve(n)开始  
最后一个事件 的 最早开始时间 == 最晚开始时间

vl(i) = min(vl(j) - wi, j)  
一个节点的最晚开始时间  
就是从下一个顶点的（可能有好几个）  
的最晚开始时间 - 弧的权值

保证所有的活动都能完成  
所以要求最小值

发表评论取消回复

表情：

评论列表（有 0 条评论，198人围观）

还没有评论，来说两句吧...

相关阅读

相关作业24-归并排序与基数排序(防止题目重复)

1-3 对N个记录进行归并排序，归并趟数的数量级是O(NlogN)。() \[解析\]归并的数量级在O(logN)? 每上下相邻的两层之间,从上层到下层的过程就是一

太过爱你忘了你带给我的痛/ 2022年12月28日 00:44/ 0 赞/ 194 阅读

相关快速排序-笔记(防止题目重复)

快速排序冒泡排序每次循环,相邻两元素两两比较,不符合则交换,最大元素沉底 //随便写的,好像不对 void BmbleSort(SqList &L)

野性酷女/ 2022年12月27日 07:50/ 0 赞/ 103 阅读

相关希尔排序-笔记(防止题目重复)

希尔排序子序列内部移动依次可能会消除多个逆序对(同时造成排序的不稳定) 1 算法思想设一个递减的增量序列如\{5, 3, 1\} 每一趟都将序列分成若干子

末蓝、/ 2022年12月27日 07:47/ 0 赞/ 123 阅读

相关作业8-栈与递归(防止题目重复)

2-1 令P代表入栈，O代表出栈。若利用堆栈将中缀表达式3\2+8/4 转为后缀表达式，则相应的堆栈操作序列是：© A.PPPOOO B.POPOPO C.

野性酷女/ 2022年12月27日 01:19/ 0 赞/ 212 阅读

相关作业7-栈及其应用(防止题目重复)

1-1 通过对堆栈S操作：Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为：123。(F)

Bertha 。/ 2022年12月26日 15:28/ 0 赞/ 145 阅读

相关算法的时间复杂度和空间复杂度(防止题目重复)

1-1 算法分析的两个主要方面是时间复杂度和空间复杂度的分析。(T) 1-2 N2logN和NlogN2具有相同的增长速度(F) \[解析\]一个N^2logN

秒速五厘米/ 2022年12月24日 13:59/ 0 赞/ 106 阅读

相关关键路径(防止题目重复)

DAG(Directed AcyclineGraph) 有向无环图用来描述一个工程或系统的进行过程。一个工程可以分为若干个子工程，只有完成了这些子工程，就可以

超、凢脫俗/ 2022年12月18日 13:57/ 0 赞/ 199 阅读

相关关键路径详解

在这里我们引入AOV（Activity-On-Edge）网概念，用顶点表示事件，用边来表示活动。区别于AOV网，AOE网的边是有权值的，代表完成事件的时间。你需要先了解拓扑

你的名字/ 2022年06月10日 13:29/ 0 赞/ 214 阅读

相关关键路径计算

转自http://blog.csdn.net/wang379275614/article/details/13990163 认识AOE网　　有向图中，

偏执的太偏执、/ 2022年06月09日 10:11/ 0 赞/ 199 阅读

相关异地防止重复登录

异地防止重复登录将用户的登录信息保存在Application内置作用域中，利用session监听每一个登录用户的登录情况。用户登录成功后将用户的登录信息已键值对的

小灰灰/ 2022年06月01日 12:43/ 0 赞/ 200 阅读