最新AOE关键路径汇总.docx
- 文档编号:2077967
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:27
- 大小:50.27KB
最新AOE关键路径汇总.docx
《最新AOE关键路径汇总.docx》由会员分享,可在线阅读,更多相关《最新AOE关键路径汇总.docx(27页珍藏版)》请在冰点文库上搜索。
最新AOE关键路径汇总
AOE关键路径
6.4.4关键路径
一、AOE网
与AOV-网相对应的是AOE-网(ActivityOnEdge)即边表示活动的网。
AOE-网是一个带权的有向无环图,其中,顶点表示事件(Event),弧表示活动,权表示活动持续的时间。
通常,AOE-网可用来估算工程的完成时间。
例如,图6.22是一个假想的有11项活动的AOE-网。
其中有9个事件v0,v1,v2,…,v8,每个事件表示在它之前的活动已经完成,在它之后的活动可以开始。
如v0表示整个工程开始,v8表示整个工程结束,v4表示a4和a5已经完成,a7和a8可以开始。
与每个活动相联系的数是执行该活动所需的时间。
比如,活动a1需要6天,a2需要4天等。
图6.22一个AOE网
和AOV-网不同,对AOE-网有待研究的问题是:
(1)完成整项工程至少需要多少时间?
(2)哪些活动是影响工程进度的关键?
由于在AOE-网中有些活动可以并行地进行,所以完成工程的最短时间是从开始点到完成点的最长路径的长度(这里所说的路径长度是指路径上各活动持续时间之和,不是路径上弧的数目)。
路径长度最长的路径叫做关键路径(CriticalPath)。
假设开始点是v0,从v0到vi的最长路径长度叫做事件vi的最早发生时间。
这个时间决定了所有以vi为尾的弧所表示的活动的最早开始时间。
我们用e(i)表示活动ai的最早开始时间。
还可以定义一个活动的最迟开始时间l(i),这是在不推迟整个工程完成的前提下,活动ai最迟必须开始进行的时间。
两者之差l(i)-e(i)意味着完成活动ai的时间余量。
我们把l(i)=e(i)的活动叫做关键活动。
显然,关键路径上的所有活动都是关键活动,因此提前完成非关键活动并不能加快工程的进度。
因此,分析关键路径的目的是辨别哪些是关键活动,以便争取提高关键活动的工效,缩短整个工期。
例如在图6.22中,v0是源点,v8是汇点,关键路径有两条:
(v0,v1,v4,v6,v8)或(v0,v1,v4,v7,v8),长序均为18。
关键活动为(a1,a4,a7,a10)或(a1,a4,a8,a11)。
比如,关键活动a1需要6天完成,如果a1提前1天,整个工程也可提前1天完成。
所以不论是估算工期,还是研究如何加快工程进度,主要问题就在于找到AOE-网的关键路径。
如何确定关键路径,首先定义4个描述量。
(1)事件vi的最早发生时间ve(i)
进入事件vi的每一活动都结束,vi才可发生,所以ve(i)是从源点到vi的最长路径长度。
求ve(i)的值,可根据拓扑顺序从源点开始到汇点递推,通常将工程开始顶点事件v0的最早发生时间定义为0,即:
ve(0)=0
ve(i)=Max{ve(k)+wk,i}
其中,T是所有以vi为头的弧的集合,wk,i是弧
(2)事件vi的最迟发生时间vl(i)
事件vi的发生不得延误vi的每一后继事件的最迟发生时间。
为了不拖延工期,vi的最迟发生时间不得迟于其后继事件vk的最迟发生时间减去活动
求出ve(i)后可根据逆拓扑顺序从汇点开始向源点递推,求出vl(i)。
vl(n-1)=ve(n-1)
vl(i)=Min{vl(k)-wi,k}
其中,S是所有以vi为尾的弧的集合,wi,k是弧
(3)活动ai=
只有事件vj发生了,活动ai才能开始。
所以,活动ai的最早开始时间等于事件vj的最早发生时间ve(j),即:
e(i)=ve(j)
(4)活动ai=
活动ai的开始时间需保证不延误事件vk的最迟发生时间。
所以活动ai的最迟开始时间l(i)等于事件vk的最迟发生时间vl(k)减去活动ai的持续时间wj,k,即:
l(i)=vl(k)-wj,k
显然,对于关键活动而言,e(i)=l(i)。
对于非关键活动,l(i)-e(i)的值是该工程的期限余量,在此范围内的适度延误不会影响整个工程的工期。
一个活动ai的最晚开始时间l(i)和最早开始时间e(i)的差值l(i)-e(i)是该活动完成的时间余量。
它是在不增加完成整个工程所需的总时间的情况下,活动ai可以拖延的时间。
当一活动的时间余量为零时,说明该活动必须如期完成,否则就会拖延整个工程的进度。
所以称l(i)-e(i)=0,即l(i)=e(i)时的ai是关键活动。
二、关键路径求解的过程
(1)输入e条弧
(2)从源点v0出发,令ve[0]=0,按拓扑有序求其余各顶点的最早发生时间ve[i](1≤i≤n-1)。
如果得到的拓扑有序序列中顶点个数小于网中顶点数n,则说明网中存在环,不能求关键路径,算法终止;否则执行步骤(3)。
(3)从汇点vn出发,令vl[n-1]=ve[n-1],按逆拓扑有序求其余各顶点的最迟发生时间vl[i](n—2≥i≥2);
(4)根据各顶点的ve和vl值,求每条弧(活动)ai的最早开始时间e(i)和最迟开始时间l(i)。
(5)找出e(i)=l(i)的活动,则为关键活动。
由关键活动形成的由源点到汇点的每一条路径就是关键路径,关键路径有可能不止一条。
三、关键路径算法的实现
由于每个事件的最早发生时间ve(i)和vl(i)要在拓扑序列的基础上进行计算,所以关键路径算法的实现要基于拓扑排序算法,我们仍采用邻接表做有向图的存储结构。
算法的实现要引入以下辅助的数据结构:
(1)一维数组ve(i):
事件vi的最早发生时间。
(2)一维数组vl(i):
事件vi的最迟发生时间。
(3)一维数组topo(i):
记录拓扑序列的顶点序号。
【算法思想】
(1)调用拓扑排序算法,使拓扑序列保存在topo中。
(2)将每个事件的最早发生时间ve(i)初始化为0,ve[i]=0。
(3)根据topo中的值,按从前向后的拓扑次序依次求每个事件的最早发生时间。
①取得拓扑序列中的顶点k,k=topo[i];
②用指针p依次指向k的每个邻接顶点,取得每个邻接顶点的序号j=p->adjvex,依次更新顶点j的最早发生时间ve[j]:
if(ve[j]
(4)将每个事件的最迟发生时间vl(i)初始化为汇点的最早发生时间,vl[i]=ve(n-1)。
(5)根据topo中的值,按从后向前的逆拓扑次序依次求每个事件的最迟发生时间vl[i]。
①取得拓扑序列中的顶点k,k=topo[i];
②用指针p依次指向k的每个邻接顶点,取得每个邻接顶点的序号j=p->adjvex,依次更新顶点k的最迟发生时间:
if(vl[k]
(6)从源点开始,对于每个顶点i,用指针p依次指向i的每个邻接顶点,取得每个顶点的序号j=p->adjvex,分别计算活动
e=ve[i];l=vl[j]-p->weight;
如果e和l相等,则活动
【算法6.13】
图的关键路径问题的算法之一AOE.CPP
/*2013年5月14日修改**图的关键路径问题的算法之一AOE.CPP*/
#include
#defineMAXVEX100
#defineTRUE1
#defineFALSE0
typedefcharVertexType[MAXVEX];//存放顶点信息的字符串
typedefstructArcNode
{intadjvex;//相邻顶点字段
floatweight;
structArcNode*nextarc;//链字段
}ArcNode;//边表中的结点
typedefstructVNode
{VertexTypedata;//顶点信息
ArcNode*firstarc;//边表头指针
}VNode,AdjList[MAXVEX];//顶点表中的结点
typedefstruct
{AdjListvertices;
intvexnum,arcnum;//图的顶点个数和弧的条数
}ALGraph;
/*求出图中所有顶点的入度,方法是搜索整个邻接表*/
voidFindInDegree(ALGraphG,intinDegree[])
{inti;
ArcNode*p;
for(i=0;i for(i=0;i {p=G.vertices[i].firstarc; while(p) {inDegree[p->adjvex]++; p=p->nextarc; } } } intTopologicalSort(ALGraphG,int*topo)//拓扑排序算法 {ArcNode*p; inti,j,k,count=0,top=-1; intindegree[MAXVEX]; FindInDegree(G,indegree);//求出图中所有顶点的入度 for(i=0;i if(indegree[i]==0)//将入度为零的顶点入栈 {indegree[i]=top; top=i; } while(top! =-1)//栈不为空 {j=top; top=indegree[top];//取出当前栈顶元素 topo[count++]=j;//topo数组存放拓扑序列 p=G.vertices[j].firstarc; /*取该元素边表中的第一个边结点,删除该结点,构造新的AOV网*/ while(p)//删除以该顶点为起点的边 {k=p->adjvex; indegree[k]--; if(indegree[k]==0)//将新的入度为零的边入栈 {indegree[k]=top; top=k; } p=p->nextarc; } } if(count {cout<<"Theaovnetworkhasacycle\n"; returnFALSE; } cout<<"拓扑序列为: "; for(i=0;i /*输出拓扑序列*/ returnTRUE; } voidinsert(ALGraph&G,inta,intb,floatweight) /*在表尾插入表结点*/ {ArcNode*p,*temp; temp=newArcNode; temp->adjvex=b; temp->nextarc=NULL; temp->weight=weight; p=G.vertices[a].firstarc; if(p==NULL) G.vertices[a].firstarc=temp; else {while(p->nextarc! =NULL)p=p->nextarc;//找表尾 p->nextarc=temp; } } intCriticalPath(ALGraphG)//G为有向网,输出G的各项关键活动。 {inti,k,j,n,topo[MAXVEX]; ArcNode*p; floatve[MAXVEX],vl[MAXVEX],e,l; if(! TopologicalSort(G,topo))returnFALSE; //调用拓扑排序算法,使拓扑序列保存在topo中,若调用失败,则存在有向环,返回FALSE n=G.vexnum;//n为顶点个数 for(i=0;i /*----------按拓扑次序求每个事件的最早发生时间---------*/ for(i=0;i {k=topo[i];//取得拓扑序列中的顶点序号k p=G.vertices[k].firstarc;//p指向k的第一个邻接顶点 while(p! =NULL)//依次更新k的所有邻接点的最早发生时间 {j=p->adjvex;//j为邻接顶点的序号 if(ve[j] ve[j]=ve[k]+p->weight; p=p->nextarc;//p指向k的下一个邻接顶点 }//while }//for for(i=0;i /*----------按逆拓扑次序求每个事件的最迟发生时间---------*/ for(i=n-1;i>=0;i--) {k=topo[i];//取得拓扑序列中的顶点序号k p=G.vertices[k].firstarc;//p指向k的第一个邻接顶点 while(p! =NULL)//依次更新k的所有邻接点的最迟发生时间 {j=p->adjvex;//j为邻接顶点的序号 if(vl[k]>vl[j]-p->weight)//更新顶点k的最迟发生时间vl[k] vl[k]=vl[j]-p->weight; p=p->nextarc;//p指向k的下一个邻接顶点 }//while }//for /*----------判断每一活动是否为关键活动---------*/ for(i=0;i {p=G.vertices[i].firstarc;//p指向i的第一个邻接顶点 while(p! =NULL) {j=p->adjvex;//j为i的邻接顶点的序号 e=ve[i];//计算活动 l=vl[j]-p->weight;//计算活动 if(e==l)cout<<"<"< p=p->nextarc;//p指向i的下一个邻接顶点 }//while }//for returnTRUE; }//CriticalPath voidmain()//主函数 {ALGraphG={"V0",NULL,"V1",NULL,"V2",NULL,"V3",NULL,"V4",NULL, "V5",NULL,"V6",NULL,"V7",NULL,"V8",NULL};//顶点初始化 G.vexnum=9; insert(G,0,1,6);insert(G,0,3,5);insert(G,0,2,4); insert(G,1,4,1);insert(G,2,4,1);insert(G,3,5,2); insert(G,4,6,9);insert(G,4,7,7);insert(G,5,7,4); insert(G,6,8,2);insert(G,7,8,4); if(CriticalPath(G)==FALSE) cout<<"Thereisnocriticalpath! \n"; } 拓扑序列为: v0v2v3v5v1v4v7v6v8 有两条关键路径: (v0,v1,v4,v6,v8)和(v0,v1,v4,v7,v8) 图的关键路径问题的算法之二AOE.CPP /*2013年4月29日修改**图的关键路径问题的算法AOE.CPP*/ #include #defineMAXVEX100 #defineTRUE1 #defineFALSE0 typedefcharVertexType[MAXVEX];/*存放顶点信息的字符串*/ typedeffloatAdjType; typedefstructArcNode {intadjvex;/*相邻顶点字段*/ AdjTypeweight; structArcNode*nextarc;/*链字段*/ }ArcNode;/*边表中的结点*/ typedefstructVNode {VertexTypedata;/*顶点信息*/ ArcNode*firstarc;/*边表头指针*/ }VNode,AdjList[MAXVEX];/*顶点表中的结点*/ typedefstruct {AdjListvertices; intvexnum,arcnum;/*图的顶点个数*/ }ALGraph; /*求出图中所有顶点的入度,方法是搜索整个邻接表*/ voidFindInDegree(ALGraphG,intinDegree[]) {inti; ArcNode*p; for(i=0;i for(i=0;i {p=G.vertices[i].firstarc; while(p) {inDegree[p->adjvex]++; p=p->nextarc; } } } voidmakeNewAOV(ArcNode*p,int*indegree,int&top) {intk; while(p)/*删除以该顶点为起点的边*/ {k=p->adjvex; indegree[k]--; if(indegree[k]==0)/*将新的入度为零的边入栈*/ {indegree[k]=top; top=k; } p=p->nextarc; } } inttopoSort(ALGraphG,int*topo)/*拓扑排序算法*/ {ArcNode*p; inti,j,count=0,top=-1; intindegree[MAXVEX]; FindInDegree(G,indegree);/*求出图中所有顶点的入度*/ for(i=0;i if(indegree[i]==0)/*将入度为零的顶点入栈*/ {indegree[i]=top; top=i; } while(top! =-1)/*栈不为空*/ {j=top; top=indegree[top];/*取出当前栈顶元素*/ topo[count++]=j;/*ptopo数组存放拓扑序列*/ p=G.vertices[j].firstarc; /*取该元素边表中的第一个边结点,删除该结点,构造新的AOV网*/ makeNewAOV(p,indegree,top);/*对indegree数组进行修改*/ } if(count {cout<<"Theaovnetworkhasacycle\n"; returnFALSE; } cout<<"拓扑序列为: "; for(i=0;i /*输出拓扑序列*/ returnTRUE; } voidinsert(ALGraph&G,inta,intb,floatweight) /*在表尾插入表结点*/ {ArcNode*p,*temp; temp=newArcNode; temp->adjvex=b; temp->nextarc=NULL; temp->weight=weight; p=G.vertices[a].firstarc; if(p==NULL) G.vertices[a].firstarc=temp; else {while(p->nextarc! =NULL)p=p->nextarc;/*找表尾*/ p->nextarc=temp; } } voidmakeList(ALGraph&G)/*邻接表的构造*/ {inti; G.vexnum=9; for(i=0;i G.vertices[i].firstarc=NULL; insert(G,0,1,6);insert(G,0,3,5);insert(G,0,2,4); insert(G,1,4,1);insert(G,2,4,1);insert(G,3,5,2); insert(G,4,6,9);insert(G,4,7,7);insert(G,5,7,4); insert(G,6,8,2);insert(G,7,8,4); } #defineMAXEDGE100/*MAXEDEG为边的最大数目*/ voidcountve(ALGraphG,int*topo,AdjType*ve)/*计算各事件的最早发生时间*/ {inti,j,k; ArcNode*p; for(i=0;i for(k=0;k {i=topo[k];//k仅起控制作用 p=G.vertices[i].firstarc; while(p! =NULL) {j=p->adjvex; if(ve[i]+p->weight>ve[j])ve[j]=ve[i]+p->weight; p=p->nextarc; } } } voidcountvl(ALGraphG,int*topo,AdjType*ve,AdjType*vl)/*计算各事件的最迟发生时间*/ {inti,j,k; ArcNode*p; for(i=0;i vl[i]=ve[G.vexnum-1];/*每个事件的最迟发生时间赋初值为最生事件的最早发生时间
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最新 AOE 关键 路径 汇总