-
2021-11-23 21:00:29
1.AOE网:在一个带权有向图中,用顶点代表事件,用有向边表示活动,边上的权值表示活动的持续时间
(1)源点:整个工程的开始点,其入度为0
(2)终点:整个工程的结束点,其出度为0
(3)性质:
- 只有进入某顶点的各活动都已经结束,该顶点所代表的事件才能发生
- 只有在某顶点所代表的事件发生后,从该顶点出发的各活动才能开始
(4)AOE网能够解决什么问题?
- 完成整个工程至少需要多少时间
- 为缩短完成工程所需的时间, 应当加快哪些活动?
(5)最短工期:从源点到终点的最大路径长度
2.关键路径(不唯一):具有最大路径长度的路径,关键路径上的活动称为关键活动
(1)求最短工期——>求关键路径——>求关键活动
关键活动为什么关键?
- 开始时间不能推迟
- 最早开始时间和最晚开始时间相等
(2)设带权有向图 G=(V,E)含有 n 个顶点 e 条边,设置 4 个一维数组:
- 事件的最早发生时间 ve[n]
- 事件的最迟发生时间 vl[n]
- 活动的最早开始时间 ae[e]
- 活动的最晚开始时间 al[e]
(3)事件的最早发生时间 ve[n]
ve[0] = 0
ve[k] = max{ve[j] + len<vj, vk>} (<vj, vk>∈p[k])
p[k]:所有到达 vk 的有向边
按拓扑顺序求,max(起点+权值)
(4)事件的最迟发生时间 vl[n]
vl[n-1] = ve[n-1]
vl[k] = min{vl[j]-len<vk , vj>}(<vk, vj>∈s[k])
s[k] :所有从 vk 发出的有向边
逆拓扑序求,min(终点-权值)
(5)活动的最早开始时间 ae[e]
起点最早
(6)活动的最晚开始时间 al[e]
终点最迟-权值
3.一些说法
(1)若任意一个关键活动延期,则工期一定延长
(2)若任意一个关键活动加快,则工期不一定加快
(3)若任意一个非关键活动延期,则工期可能延长
(4)若任意一个非关键活动延期,则工期不加快
更多相关内容 -
数据结构-关键路径
2020-09-02 21:57:33(2)关键路径只有一条,关键活动也不是无限制缩短,工期会无限缩短的,因为可能缩到一定程度,这个节点就不是关键活动了。 求解关键路径的主要步骤: (1)求解ve(),求解每个节点(事件)的最早发生时间:规.AOV、AOE都是有权无向图,AOV边不带权值,AOE带权值。
关键路径是AOE中,开始顶点到结束顶点的所有路径中,具有最大路径长度的路径成为关键路径,路径上的点是关键活动。
(1)关键路径如果有多条,至提高一条关键路径上的关键活动并不能缩短工期,必须要加快所有关键路径上的关键活动才能加快工期。
(2)关键路径只有一条,关键活动也不是无限制缩短,工期会无限缩短的,因为可能缩到一定程度,这个节点就不是关键活动了。
求解关键路径的主要步骤:
(1)求解ve(),求解每个节点(事件)的最早发生时间: 规定ve(0) = 0。 ve(n) = max(ve(n-1)+x1,ve(n-2)+x2) 能够到达n的所有路径中最大值。
(2)求解vl(),求解每个节点(事件)的最迟发生时间:规定vl(终点)= ve(终点)。vl=min(vl(n-1)-x1,vl(n-2)-x2) 能够返回n的所有路径中的最小值。
(3)求解e(),求解每个活动的最早开始时间。->活动a连接的两端的顶点的最早发生时间
(4)求解l(),求解每个活动的最迟开始时间。->活动a连接的两端的终点的最迟发生时间-活动a历经的时间。
(5)用e()-l(),找出等于0的点,等于0的路径就是关键路径。
关键路径为:a2,a5,a7. v1->v3->v5->v6
20题。无需将所有步骤都完成,因为可以直接看出。最终选择C
21 ,求解ve(),vl() e() l () ,将e() - l () = 0 可以看出所有关键路径。因此有三条,最终选择C。
-
关键路径--经典算法
2017-11-28 21:36:10在建筑学中也称为关键路线。AOE网常用于估算工程完成时间。例如: 图1 图1 是一个网。其中有9个事件v1,v2,…,v9;11项活动a1,a2,…,a11。每个事件表示在它之前的活动已经完成,在它之后的活动可以开始。如AOE网
用顶点表示事件,弧表示活动,弧上的权值表示活动持续的时间的有向图叫AOE(Activity On Edge Network)网。在建筑学中也称为关键路线。AOE网常用于估算工程完成时间。例如:图1 是一个网。其中有9个事件v1,v2,…,v9;11项活动a1,a2,…,a11。每个事件表示在它之前的活动已经完成,在它之后的活动可以开始。如 v1表示整个工程开始,v9 表示整个工程结束。V5表示,活动a2和a3已经完成,活动a7和a8可以开始。与每个活动相联系的权表示完成该活动所需的时间。如活动a1需要6个时间单位可以完成、
AOE网性质
只有在某顶点所代表的事件发生后,从该顶点出发的各有向边所代表的活动才能开始。只有在进入某一顶点的各有向边所代表的活动都已经结束,该顶点所代表的事件才能发生。表示实际工程计划的AOE网应该是无环的,并且存在唯一的入度过为0的开始顶点和唯一的出度为0的完成顶点。
关键路径
一个AOE网的关键路径可以不止一条,如图7.24的AOE网中有二条关键路径,(v1,v2,v5,v7,v9 ) 和 (v1,v2,v5,v8,v9 )它们的路径长度都是24。如图2所示:研究的问题
(1) 完成整个工程至少需要多少时间;(2) 哪些活动是影响工程的关键。关键路径术语
(1) 关键路径:从源点到汇点的路径长度最长的路径叫关键路径;(2) 活动开始的最早时间e(i);(3) 活动开始的最晚时间l(i) 定义e(i)=l(i)的活动叫关键活动;(4) 事件开始的最早时间ve(i);(5) 事件开始的最晚时间vl(i)。设活动ai由弧<j,k>(即从顶点j到k)表示,其持续时间记为dut(<j,k>),则e(i)=ve(j)l(i)=vl(k)-dut(<j,k>)求ve(i)和vl(j)分两步:1、从ve(1)=0开始向前递推ve(j)=Max{ ve(i)+dut(<i,j>) }<i,j>T,2<=j<=n其中,T是所有以j为弧头的弧的集合。2、 从vl(n)=ve(n)开始向后递推vl(i)=Min{ vl(j)-dut(<i,j>) }<i,j>S,1<=i<=n-1其中,S是所有以i为弧尾的弧的集合。两个递推公式是在拓扑有序和逆拓扑有序的前提下进行。就如上面的图1:可有下表:
求关键路径的算法(1) 输入e条弧<j,k>,建立AOE网的存储结构;(2) 从源点v1出发,令ve(1)=0,求 ve(j) 2<=j<=n;(3) 从汇点vn出发,令vl(n)=ve(n),求 vl(i) 1<=i<=n-1;(4) 根据各顶点的ve和vl值,求每条弧s(活动)的最早开始时间e(s)和最晚开始时间l(s),其中e(s)=l(s)的为关键活动。求关键路径是在 拓扑排序的前提下进行的,不能进行拓扑排序,自然也不能求关键路径。
算法分析
(1) 求关键路径必须在拓扑排序的前提下进行,有环图不能求关键路径;(2) 只有缩短关键活动的工期才有可能缩短工期;(3) 若一个关键活动不在所有的关键路径上,减少它并不能减少工期;(4) 只有在不改变关键路径的前提下,缩短关键活动才能缩短整个工期。测试数据:第一行表示顶点数和弧数;后面每一行就是权值,弧尾,弧头;6 8
3 12
2 13
2 24
3 25
4 34
3 36
2 46
1 56
代码:可能在过程中需要知道拓扑排序,如果不知道的可以在我的另一篇文章中有介绍,此处的数据之间有点绕,可以好好的自己推一下,懂了之后就是很简单的算法;这里我使用的是C++的STL辅助,如果,有不懂的读者可以提前了解,其实,一起可以自己用C语言写一下啦,只是有点麻烦啦,什么队列栈呀的,都可以自己用数组模拟,知识在C++的STL中都有了,那还模拟啥呢,#include <iostream> #include <stack> #include <list> #include <vector> #include <algorithm> #define NUM 20 using namespace std; struct Info{ int num; int value; Info(){} Info(int x,int y):num(x),value(y){}//构造函数 }; int indree[NUM]={0}; int N,M;//表示顶点数和边数; vector<list<Info> > Graph(NUM); stack<int> T;//用来储存拓扑排序的顶点,用来逆序输出; int Ve[NUM]; int Vl[NUM]; //拓扑排序求出事件 的最早发生时间Ve(j)和最迟发生时间Vl(j); bool tuopsort() { int count = 0; stack<int> q; memset(Ve, 0, sizeof(Ve)); for(int i = 1;i<=N;i++) if(!indree[i]) q.push(i); while(!q.empty()){ int t = q.top(); q.pop(); count++; T.push(t); for(list<Info>::iterator it = Graph[t].begin(); it!=Graph[t].end();it++){ int k = it->num; if(!(--indree[k])) q.push(k); Ve[k] = max(Ve[k],Ve[t]+it->value);//不断更新里面的最大值; } } if(count<N) return false; else return true; } bool CritPath() { if(!tuopsort()) return false; memset(Vl, 125, sizeof(Vl)); Vl[N] = Ve[N]; while(!T.empty()){ int t = T.top(); T.pop(); for(list<Info>::iterator it = Graph[t].begin(); it!=Graph[t].end();it++){ int k = it->num; Vl[t] = min(Vl[t],Vl[k]-it->value);//也是不断的更新; } } // for(int i = 1;i<=N;i++){ // cout <<Ve[i]<<" "<<Vl[i]<<endl; // } int ee,el; for(int i = 1;i<=N;i++){ for(list<Info>::iterator it = Graph[i].begin(); it!=Graph[i].end();it++){ int k = it->num; ee= Ve[i]; el = Vl[k]-it->value; int flag = (ee==el)?1:0; cout <<i<<"v->v"<<k<<" "<<it->value<<" "<<ee<<" "<<el<<" "<<flag<<endl; } } return true; } void print(Info f) { cout <<f.num<<"V-"<<f.value<<" "; } int main() { cin>>N>>M; for(int i=1;i<=M;i++){ int v,f,e; cin>>v>>f>>e; if(f!=e) {Graph[f].push_front(Info(e,v));indree[e]++;} } // cout <<"图的邻接表储存:"<<endl; // for(int i= 1;i<=N;i++){ // cout <<i<<" "; // for_each(Graph[i].begin(),Graph[i].end() , print); // cout <<endl; // } // cout <<"每一个顶点的入度:"; // for(int i = 1;i<=N;i++) // cout <<indree[i]<<" "; // cout <<endl; CritPath(); return 0; }
-
关键路径
2020-03-31 10:33:55AOE网:在一个表示工程的带权有向图中,用顶点表示事件(如V0),用有向边表示活动(如<v0,v1> = a1),边上的权值表示活动的持续时间,称这样的有向图为边表示的活动的网,简称AOE网(activity on edge ...AOE网示例图:
AOE网:在一个表示工程的带权有向图中,用顶点表示事件(如V0),用有向边表示活动(如<v0,v1> = a1),边上的权值表示活动的持续时间,称这样的有向图为边表示的活动的网,简称AOE网(activity on edge network)
源点:
在AOE网中,没有入边的顶点称为源点;如顶点V0终点:
在AOE网中,没有出边的顶点称为终点;如顶点V3AOE网的性质:
【1】只有在进入某顶点的活动都已经结束,该顶点所代表的事件才发生;例如:a1和a2活动都结束了,顶点V2所代表的事件才会发生。
【2】只有在某顶点所代表的事件发生后,从该顶点出发的各活动才开始;
例如:只有顶点V1所代表的事件结束之后,活动a2和a4才会开始。
在AOE网中,所有活动都完成才能到达终点,因此完成整个工程所必须花费的时间(即最短工期)应该为源点到终点的最大路径长度。具有最大路径长度的路径称为关键路径。关键路径上的活动称为关键活动:
事件的最早发生时间:ve[k]
根据AOE网的性质,只有进入Vk的所有活动<Vj, Vk>都结束,Vk代表的事件才能发生,而活动<Vj, Vk>的最早结束时间为ve[j]+len<Vj, Vk>。所以,计算Vk的最早发生时间的方法为:ve[0] = 0
ve[k] = max(ve[j] + len<Vj, Vk>)
事件的最迟发生时间:vl[k]
vl[k]是指在不推迟整个工期的前提下,事件Vk允许的最迟发生时间。根据AOE网的性质,只有顶点Vk代表的事件发生,从Vk出发的活动<Vk, Vj>才能开始,而活动<Vk, Vj>的最晚开始时间为 vl[k]=vl[j] - len<Vk, Vj>。活动的最早发生时间:ee[i]
ai由有向边<Vk, Vj>,根据AOE网的性质,只有顶点Vk代表的事件发生,活动ai才能开始,即活动ai的最早开始时间等于事件Vk的最早开始时间, ee[i] = ve[k]活动的最迟发生时间:el[i]
el[i]是指在不推迟整个工期的前提下,活动ai必须开始的最晚时间。若活动ai由有向边<Vk, Vj>表示,则ai的最晚开始时间要保证事件vj的最迟发生时间不拖后,即 el[i]=vj最迟发生时间-ai案例:
原始AOE网:
事件的最早发生时间:ve[k]
从源点向终点方向计算
ve[0] = 0
ve[1] = ve[0] + a0 = 0 + 4 = 4
ve[2] = max( ve[0] + a1, ve[1] + a2 ) = max(0 + 3, 4 + 2 = 6
ve[3] = max(ve[1] + a4, ve[2] + a3) = max(4 + 6, 3 + 4) = 10
事件的最迟发生时间:vl[k]
从终点向源点方向计算
vl[3] = ve[3] = 10
vl[2] = vl[3] - a3 = 10 - 4 = 6
vl[1] = min(vl[3] - a4, vl[2] - a2) = min(10-6, 6-2) = 4
vl[0] = min(vl[2] - a1, vl[1] - a0) = min(4-4, 4-2) = 0
活动的最早发生时间:ee[i]
共有五个活动:
ee[0] = ve[0] = 0
ee[1] = ve[0] = 0
ee[2] = ve[1] = 4
ee[3] = ve[2] = 6
ee[4] = ve[1] = 4
活动的最迟发生时间:el[i]
el[0] = v[1] - a0 = 4 - 4 = 0
el[1] = vl[2] - a1 = 6 - 3 = 3
el[2] = vl[2] - a2 = 6 - 2 = 4
el[3] = vl[3] - a3 = 10 - 4 = 6
el[4] = vl[3] - a4 = 10 - 6 = 4
活动的最早开始时间和最晚开始时间相等,则说明该活动时属于关键路径上的活动,即关键活动。
经过比较,得出关键活动有:a0, a2, a3, a4,画出示意图如下:
该AOE网有两条关键路径。
所以,通过此案例也可以发现,一个AOE网的关键路径可能有多条。
-
关键路径问题内容讲解
2018-03-29 12:06:19关键路径问题讲解,解决最早开始时间,最晚开始时间的问题。 -
关键路径AOE网及其如何求关键路径步骤(C语言)
2021-08-07 16:14:18一、关键路径 (一)AOE网 在带权有向图中,以顶点表示事件,以有向边表示活动,以边上的权值表示完成该活动的开销(如完成活动所需的时间),称之为⽤边表示活动的网络,简称AOE网 (Activity On Edge NetWork) 在... -
【算法专题】关键路径及代码实现
2021-09-07 11:16:30关键路径 一. 问题描述 概念 一项工程计划可以被看成一个有向图,图中的顶点表示事件,边代表活动,边上的权值代表完成这项活动需要的...我们只有减少关键路径上活动用时才能加快工程的进度。 我们的问题就是输 -
关键路径详解
2019-11-22 15:46:36关键路径算法是一种典型的动态规划法,设图 G=(V, E) 是个 AOE 网,结点编号为 1,2,...,n ,其中结点 1 与 n 分别为始点和终点, ak=, j> ∈ E 是 G 的一个活动。算法关键是确定活动的 最早发生时间v e[k] 和 最晚... -
数据结构上机题关键路径
2017-12-21 22:37:27关键路径的权值和,并且从源点输出关键路径上的路径(如果有多条,请输出字典序最小的) 输入样例 9 11 1 2 6 1 3 4 1 4 5 2 5 1 3 5 1 4 6 2 5 7 9 5 8 7 6 8 4 8 9 4 7 9 2 输出样例 18 1 2 2 5 5 7 7 9 -
图——关键路径
2019-04-02 09:10:27AOE网:在一个表示工程的带权有向图中,用顶点表示事件(如V0),用有向边表示活动(如<v0,v1> = a1),边上的权值表示活动的持续时间,称这样的有向图为边表示的活动的网,简称AOE网(activity on edge ... -
关键路径计算
2017-09-03 13:58:48计算关键路径,只需求出上面的四个特征属性,然后取e(i)=l(i)的边即为关键路径上的边(关键路径可能不止一条)。 先来看看四个特征属性的含义: Ø Ve(j):是指从始点开始到顶点Vk的最大路径长度 ... -
如何求关键活动以及存在多条关键路径的输出(数据结构C语言版)
2019-01-10 15:36:47如何求关键活动以及存在多条关键路径的输出(数据结构C语言版) ** 1.问题描述 关键路径: 通常把计划、施工过程、生产流程、程序流程等都当成一个工程。工程通常分为若干个称为“活动”的子工程。完成了这些... -
关键路径实践报告
2014-01-03 22:54:56在AOE网络中,从源点到汇点的有向路径可能不止一条,但只有各条路径上所有活动都完成了,这个工程才算完成。因此,完成整个工程所需的时间取决于从源点到汇点的最长路径长度,即在这条路径上所有活动的持续时间之和... -
关键路径习题.ppt
2020-12-21 09:49:58山东绿邦网络技术集成有限公司 地址:山东省济南市文化西路13号 邮编:250014 电话:0531传真:0531网址: 山东绿邦 关键路径法(Critical Path ethod,CPM) 关键路线法是一种网络图方法,由雷明顿-兰德公司(Remington... -
拓扑排序以及求解关键路径
2019-10-29 17:14:33拓扑排序以及求解关键路径都是属于有向无环网的应用 拓扑排序:解决工程能否顺序进行的问题 介绍2个概念 AOV网:在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示... -
图的关键路径
2020-05-17 09:52:44图的关键路径思想 AOE网是指在有向网中,如果用顶点表示事件,用有向边表示活动,边上的权值表示活动持续的时间,则称这样的有向网为弧表示活动的网(Acticity On Edge,AOE-网)。对仅有一个开始点和一个完成点的... -
图解:什么是关键路径?
2020-05-06 20:31:39小禹禹,五一假期马上结束了,你们过得怎么样呢?有没有玩得很开心,收获满满呢?好想听你们在评论区说一说。哈哈,不过我们还是先来说一说今日景禹要给你们分享的内容,关键路径。何为关键路径?如果... -
数据结构C++——关键路径
2021-06-07 13:19:31文章目录数据结构C++——关键路径一、前言二、关键路径的概念三、关键路径的实现①关键路径的实现原理②关键路径的代码实现③测试的全部代码四、总结 一、前言 理解关键路径需要掌握拓扑排序和邻接表的相关知识,... -
【数据结构】——关键路径 给出一个图,输出所有关键路径
2019-03-13 23:08:07给出一个图,首先判断是否为有向无环图,如果是,则输出要求的边的最早发生时间和最晚发生时间,然后输出所有关键路径。 判断是否为有向无环图,可以用拓扑排序来判断。 二、分析 首先分析拓扑排序。使用邻接矩阵... -
超详细讲解实现拓扑排序、关键路径
2022-03-26 11:07:49今天,小编带着大家来学习图中非常重要的一环,拓扑排序和关键路径! 首先,我们需要知道的是,拓扑排序是关键路径的基础,正因如此,当我们知道了关键路径在生活中的应用,相信大家也就明白这两个算法的重要性了!... -
数据结构之——关键路径
2020-06-06 23:07:571.AOE网 边活动(Activity On Edge, AOE)网是指用带权的边集表示活动,用顶点表示事件的有向图,而用边权表示活动完成需要的时间。 如下图所示,边a1 -a6表示需要学习的课程...(2)只有在进入某一顶点的各有向边所代 -
拓扑排序和关键路径算法----关键路径算法 (C语言实现)
2020-07-22 12:15:267这条红色的路径就是关键路径。关键路径的特征是:从起点 (起点是唯一的,入度为0) 到终点 (终点是唯一的,出度为0) 的一个有向图中,该路径上的弧 (有向图的边称之为“弧”) 的权重的和最大。关键路径可能不是唯一... -
图的应用——关键路径
2020-01-14 18:41:58AOE网、关键路径 -
简单理解关键路径
2020-03-03 20:40:09一,关键路径问题的相关概念 通常,一个项目可以被拆分成多个子项目,多个子项目间会具有并行和串行的特点。 例如造汽车时,造发动机和造车轮是两个可以并行完成的任务,而组装整车又必须等发动机和车轮等部件完成后... -
关键路径法详解【CPM】
2018-09-01 22:26:33CPM(CriticalPathMethod 关键路径法)是项目管理中最基本也是非常关键的一个概念,它上连着WBS(工作分解结构),下连着执行进度控制与监督。关键路径是项目计划中最长的路线。 它决定了项目的总实耗时间。项目经理... -
【数据结构】AOE网——关键路径
2021-05-16 10:01:48在AOE网中,从源点到汇点最长的路径称为关键路径,在关键路径上的活动称为关键活动。 因为AOE网中的活动是可以并行进行的,所以整个工程的时间开销,其实是最长路径的时间开销。即关键路径制约整个工程的工期。 &...