本文主要是介绍关键路径(AOE网),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
关键路径
1.概念介绍
主要解决工程完成需要的最短时间问题
AOE是在AOV基础上概念,即将工程的工序进行拓扑排列后加入活动持续时间
下图中AOE网中,弧上的2代表制造外壳这个活动的持续时间,顶点(外壳完成)是这个活动结束的标志事件。
下面这些活动是可以同时进行的
AOE网:边代表活动,边的权值代表活动的持续时间,顶点代表事件
源点:工程的开始
汇点:工程的结束
顶点 V 0 , V 1 … … V_0,V_1…… V0,V1……表示事件
弧 < V 0 , V 1 > <V_0,V_1> <V0,V1>, < V 0 , V 2 > … … <V_0,V_2>…… <V0,V2>……表示活动,用 a 0 a_0 a0, a 1 a_1 a1表示,权值代表活动持续时间
路径长度:路径上各个活动所持续的时间之和(权值大小)
关键路径:从源点到汇点具有最大长度的路径(耗时最长)
关键活动:关键路径上的活动(弧)
上图的关键路径为:( v 0 v_0 v0, v 2 v_2 v2, v 3 v_3 v3, v 4 v_4 v4, v 7 v_7 v7, v 8 v_8 v8, v 9 v_9 v9)
采用邻接表作为有向图的存储结构
2.关键路径的例子
以下面这个例子引出关键路径算法
下图中的关键路径为:
( v 0 v_0 v0, v 1 v_1 v1, v 4 v_4 v4, v 6 v_6 v6, v 8 v_8 v8) 关键路径长度为18
( v 0 v_0 v0, v 1 v_1 v1, v 4 v_4 v4, v 7 v_7 v7, v 8 v_8 v8) 关键路径长度为18
关键活动为:
( a 1 a_1 a1, a 4 a_4 a4, a 7 a_7 a7, a 10 a_{10} a10)
( a 1 a_1 a1, a 4 a_4 a4, a 8 a_8 a8, a 11 a_{11} a11)
3.事件(顶点)的发生时间
事件(顶点) v i v_i vi 的最早发生时间 v e ( i ) ve(i) ve(i)
v e ( i ) ve(i) ve(i) 是从源点到 v i v_i vi 的最长路径长度
例如:
事件 v 2 v_2 v2代表着活动 a 2 a_2 a2的结束,同时也代表着活动 a 5 a_5 a5的开始,相当于一个标志
活动 a 2 a_2 a2持续的时间为4,该活动结束的标志是事件 v 2 v_2 v2的发生,活动 a 2 a_2 a2结束后紧接着事件 v 2 v_2 v2发生,所以事件 v 2 v_2 v2的最早发生时间是 v e ( v 2 ) = 4 ve(v_2)=4 ve(v2)=4
图中 w 0 , 1 w_{0,1} w0,1 代表弧< v 0 v_0 v0, v 1 v_1 v1>对应的权值
事件 v i v_i vi 的最迟发生时间 v l ( i ) vl(i) vl(i)
v i v_i vi的发生不得延误 v i v_i vi的每一后继事件的最迟发生时间
例如:
整个工程完成需要18分钟,要给活动 a 11 a_{11} a11 留出4分钟的时间,活动 a 11 a_{11} a11 开始的标志是事件 v 7 v_7 v7 的发生,即事件 v 7 v_7 v7 的最迟发生时间 v l ( v 7 ) = 18 − 4 = 14 vl(v_7)=18-4=14 vl(v7)=18−4=14
求出 v e ( i ) ve(i) ve(i) 后,根据逆拓扑序列从汇点开始向源点递推,求 v l ( i ) vl(i) vl(i)
事件(顶点)的发生时间
4.活动(弧)的发生时间
活动 a i a_i ai=< v j v_j vj, v k v_k vk>的最早开始时间 e ( i ) e(i) e(i)
只有事件 v j v_j vj 发生了,活动 a i a_i ai 才能开始
例如:
活动 a 4 a_4 a4 在活动 a 1 a_1 a1完成后即可开始,所以活动 a 4 a_4 a4的最早开始时间 e ( a 4 ) = 6 e(a_4)=6 e(a4)=6
活动 a i a_i ai=< v j v_j vj, v k v_k vk>的最晚开始时间 l ( i ) l(i) l(i)
活动 a i a_i ai 的开始时间需保证不延误事件 v k v_k vk 的最迟发生时间
例如:
整个工程完成需要 18 分钟,给活动 a 11 a_{11} a11 预留最后的 4 分钟,活动 a 8 a_8 a8 持续时间需要 7 分钟,所以活动 a 8 a_8 a8 最晚开始时间 l ( a 8 ) = 18 − 4 − 7 = 7 l(a_8)=18-4-7=7 l(a8)=18−4−7=7分钟,活动 a 8 a_8 a8 最晚要在第 7 分钟的时候开始
一个活动 a i a_i ai 的最迟开始时间 l ( i ) l(i) l(i) 和其最早开始时间 e ( i ) e(i) e(i) 的差值 l ( i ) − e ( i ) l(i)-e(i) l(i)−e(i) 是该活动完成的时间余量
关键活动
l ( i ) − e ( i ) = 0 l(i)-e(i)=0 l(i)−e(i)=0,即 l ( i ) = e ( i ) l(i)=e(i) l(i)=e(i) 时的活动 a i a_i ai 是关键活动。当活动时间余量为0时,说明该活动必须如期完成,不可拖延
非关键活动
l ( i ) − e ( i ) = C o n s t a n t l(i)-e(i) = Constant l(i)−e(i)=Constant 的值是该工程的期限余量,在此范围内的适度延误不会影响整个工程的工期。表示如果完成整个工程所需的总时间不变的情况下,活动 a i a_i ai 可以拖延的时间
活动(弧)的开始时间
5.关键路径的算法实现
G为邻接表存储的有向网,输出G的各项关键活动
Status CriticalPath(){if(!TopologicalOrder(G,topo)) //调用拓扑排序算法,使拓扑序列保存在toporeturn ERROR; //调用失败n=G.vexnum; //顶点个数for(i=0; i<n; i++) //初始化事件(顶点)的最早发生时刻ve[i]=0;
//按拓扑排序求每个事件(顶点)的最早发生时刻for(i=0; i<n; i++){k=topo[i]; //拓扑序列存储的是按工序排好的事件(顶点)的下标p=G.vertices[k].firstarc; //指向顶点V_i的第一邻接点V_kwhile(p != NULL){ //所指的第一邻接点非空j = p->adjvex; //第一邻接点V_k的下标if(ve[j] < ve[k]+p->weight) //ve[j]是从源点到下标为j的当前路径长度ve[j] = ve[k]+p->weight;//更新ve[j]后变为最长的路径长度p=p->nextarc; //重命名p->nextarc为p以便下一次循环寻找顶点的下一个邻接点}}for(i=0; i<n; i++) //初始化数组vlvl[i]=ve[n-1]; //下标从0开始,共n个顶点,所以最后一个顶点下标应该是n-1
//按逆拓扑排序求每个事件(顶点)的最迟发生时间for(i=n-1; i>=0; i--){ //逆拓扑序列k=topo[i];p=G.vertices[k].firstarc; //指向顶点V_i的第一邻接点V_kwhile(p != NULL){j=p->adjvex; //第一邻接点V_k的下标if(vl[k] > vl[j]-p->weight) //vl[k]是从汇点到下标为k的当前路径长度vl[k] = vl[j]-p->weight; //更新顶点k的最迟发生时刻vl[k]p=p->nextarc; //重命名p->nextarc为p以便下一次循环寻找顶点的下一个邻接点}}
//判断每一个活动(弧)是否为关键活动for(i=0; i<n; i++){p=G.vertices[i].firstarc;while(p != NULL){j=p->adjvex; //顶点i的第一邻接点je=ve[i]; //顶点i的最早发生时刻l=vl[j]-p->weight; //顶点j的最迟发生时刻if(e==l) //工程的期限余量为0,意味着不可拖延,所以为关键活动cout << G.vertices[i].data << G.vertices[j].data;p=p->nextarc; //重命名p->nextarc为p以便下一次循环寻找顶点的下一个邻接点}}
}
这篇关于关键路径(AOE网)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!