AOE关键路径

6.4.4 关键路径 一、AOE网 与AOV-网相对应的是AOE-网(Activity On Edge)即边示活动的网。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-网中有些活动可以并行地进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度(这里所说的路径长度是指路径上各活动持续时间之和，不是路径上弧的数目)。路径长度最长的路径叫做关键路径(Critical Path)。假设开始点是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，1≤i≤n-1 其中，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，0≤i≤n-2 其中，S是所有以vi为尾的弧的集合，wi,k是弧的权值。 (3)活动ai=的最早开始时间e(i) 只有事件vj发生了，活动ai才能开始。所以，活动ai的最早开始时间等于事件vj的最早发生时间ve(j)，即： e(i)=ve(j) (4)活动ai=的最晚开始时间l(i) 活动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条弧，建立AOE-网的存储结构。 (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]weight) ve[j]= ve[k]+p->weight; (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]weight) vl[k]= vl[j]－p->weight; (6)从源点开始，对于每个顶点i，用指针p依次指向i的每个邻接顶点，取得每个顶点的序号j=p->adjvex，分别计算活动的最早发生时间和最迟发生时间e和l。 e=ve[i]； l=vl[j]－p->weight; 如果e和l相等，则活动为关键活动，输出弧。 【算法6.13】 图的关键路径问题的算法之一AOE.CPP /*2013年5月14日修改**图的关键路径问题的算法之一AOE.CPP*/ #include #define MAXVEX 100 #define TRUE 1 #define FALSE 0 typedef char VertexType[MAXVEX]; //存放顶点信息的字符串 typedef struct ArcNode { int adjvex; //相邻顶点字段 float weight; struct ArcNode *nextarc; // 链字段 }ArcNode; // 边表中的结点 typedef struct VNode { VertexType data; // 顶点信息 ArcNode *firstarc; // 边表头指针 }VNode,AdjList[MAXVEX]; // 顶点表中的结点 typedef struct { AdjList vertices; int vexnum,arcnum; //图的顶点个数和弧的条数 }ALGraph; /* 求出图中所有顶点的入度，方法是搜索整个邻接表 */ void FindInDegree(ALGraph G,int inDegree[]) { int i; ArcNode *p; for(i=0;iadjvex]++; p=p->nextarc; } } } int TopologicalSort(ALGraph G,int *topo) //拓扑排序算法 { ArcNode *p; int i,j,k,count=0,top=-1; int indegree[MAXVEX]; FindInDegree(G,indegree); // 求出图中所有顶点的入度 for(i=0;iadjvex; indegree[k]--; if(indegree[k]==0) //将新的入度为零的边入栈 { indegree[k]=top; top=k; } p=p->nextarc; } } if(countadjvex=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; } } int CriticalPath(ALGraph G)//G为有向网，输出G的各项关键活动。 { int i,k,j,n,topo[MAXVEX]; ArcNode *p; float ve[MAXVEX],vl[MAXVEX],e,l; if(!TopologicalSort(G,topo)) return FALSE; //调用拓扑排序算法，使拓扑序列保存在topo中，若调用失败，则存在有向环，返回FALSE n=G.vexnum; //n为顶点个数 for(i=0;iadjvex; //j为邻接顶点的序号 if(ve[j]weight) //更新顶点j的最早发生时间ve[j] ve[j]=ve[k]+p->weight; p=p->nextarc; //p指向k的下一个邻接顶点 }//while }//for for(i=0;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;iadjvex; //j为i的邻接顶点的序号 e=ve[i]; //计算活动的最早开始时间 l=vl[j]-p->weight; //计算活动的最迟开始时间 if(e==l) cout<<"<"<,"; p=p->nextarc; //p指向i的下一个邻接顶点 }//while }//for return TRUE; }//CriticalPath void main() //主函数 { ALGraph G={"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<<"There is no critical path!\n"; } 拓扑序列为：v0 v2 v3 v5 v1 v4 v7 v6 v8 ，，，，， 有两条关键路径：(v0，v1，v4，v6，v8)和(v0，v1，v4，v7，v8) 图的关键路径问题的算法之二AOE.CPP /*2013年4月29日修改**图的关键路径问题的算法AOE.CPP*/ #include #define MAXVEX 100 #define TRUE 1 #define FALSE 0 typedef char VertexType[MAXVEX]; /*存放顶点信息的字符串*/ typedef float AdjType; typedef struct ArcNode { int adjvex; /* 相邻顶点字段 */ AdjType weight; struct ArcNode *nextarc; /* 链字段 */ }ArcNode; /* 边表中的结点 */ typedef struct VNode { VertexType data; /* 顶点信息 */ ArcNode *firstarc; /* 边表头指针 */ }VNode,AdjList[MAXVEX]; /* 顶点表中的结点 */ typedef struct { AdjList vertices; int vexnum,arcnum; /* 图的顶点个数 */ }ALGraph; /* 求出图中所有顶点的入度，方法是搜索整个邻接表 */ void FindInDegree(ALGraph G,int inDegree[]) { int i; ArcNode *p; for(i=0;iadjvex]++; p=p->nextarc; } } } void makeNewAOV(ArcNode *p,int *indegree, int &top) { int k; while(p) /* 删除以该顶点为起点的边 */ { k=p->adjvex; indegree[k]--; if(indegree[k]==0) /* 将新的入度为零的边入栈 */ { indegree[k]=top; top=k; } p=p->nextarc; } } int topoSort(ALGraph G,int *topo) /*拓扑排序算法*/ { ArcNode *p; int i,j,count=0,top=-1; int indegree[MAXVEX]; FindInDegree(G,indegree); /* 求出图中所有顶点的入度 */ for(i=0;iadjvex=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; } } void makeList(ALGraph &G) /*邻接表的构造*/ { int i; G.vexnum=9; for(i=0;iadjvex; if(ve[i]+p->weight>ve[j]) ve[j]=ve[i]+p->weight; p=p->nextarc; } } } void countvl(ALGraph G,int *topo,AdjType *ve, AdjType *vl) /*计算各事件的最迟发生时间*/ { int i,j,k; ArcNode *p; for(i=0;i=0;k--) /*下标从0开始，最后一个顶点无后继，所以减2*/ { i=topo[k]; p=G.vertices[i].firstarc; while(p!=NULL) { j=p->adjvex; if(vl[j]-p->weightweight; p=p->nextarc; } } } void counte_l(ALGraph G,AdjType *ve,AdjType *vl,AdjType *ee,AdjType *el) /*计算各活动的最早发生时间和最迟发生时间，并输出关键路径*/ { int i=0,j,k; ArcNode *p; cout<<"关键路径是： "; for(j=0;jadjvex; ee[i]=ve[j]; el[i]=vl[k]-p->weight; if(ee[i]==el[i]) cout<<","; i++; //i表示弧的序号。弧的序号自第一个顶点开始到最后一个顶点止顺序编号。 p=p->nextarc; } } } int CriticalPath(ALGraph G) /*关键路径算法*/ { AdjType ve[MAXVEX],vl[MAXVEX],ee[MAXEDGE],el[MAXEDGE]; int topo[MAXVEX]; if(topoSort(G,topo)==FALSE) /*求AOE网的一个拓扑序列*/ return FALSE; /*若有环则返回FALSE*/ countve(G,topo,ve); /*计算数组ve，ve存放事件可能的最早发生时间*/ countvl(G,topo,ve,vl); /*计算数组vl，vl存放事件可能的最迟发生时间*/ counte_l(G,ve,vl,ee,el); /*计算数组ee,el并输出结果*/ cout<<"\n"; /*数组ee存放活动的最早开始时间,数组el存放活动的最晚开始时间*/ return TRUE; } void main() /*主程序*/ { ALGraph G; makeList(G); if(CriticalPath(G)==FALSE) cout<<"There is no critical path!\n"; } 图的关键路径问题的算法之三 /*2013年4月29日修改**图的关键路径问题的算法之三AOE.CPP*/ #include #define MAXVEX 100 #define TRUE 1 #define FALSE 0 typedef char VertexType[MAXVEX]; /*存放顶点信息的字符串*/ typedef float AdjType; typedef struct ArcNode { int adjvex; /* 相邻顶点字段 */ AdjType weight; struct ArcNode *nextarc; /* 链字段 */ }ArcNode; /* 边表中的结点 */ typedef struct VNode { VertexType data; /* 顶点信息 */ ArcNode *firstarc; /* 边表头指针 */ }VNode,AdjList[MAXVEX]; /* 顶点表中的结点 */ typedef struct { AdjList vertices; int vexnum,arcnum; /* 图的顶点个数 */ }ALGraph; /* 求出图中所有顶点的入度，方法是搜索整个邻接表 */ void FindInDegree(ALGraph G,int inDegree[]) { int i; ArcNode *p; for(i=0;iadjvex]++; p=p->nextarc; } } } void makeNewAOV(ArcNode *p,int *indegree, int &top) { int k; while(p) /* 删除以该顶点为起点的边 */ { k=p->adjvex; indegree[k]--; if(indegree[k]==0) /* 将新的入度为零的边入栈 */ { indegree[k]=top; top=k; } p=p->nextarc; } } int topoSort(ALGraph G,int *topo) /*拓扑排序算法*/ { ArcNode *p; int i,j,count=0,top=-1; int indegree[MAXVEX]; FindInDegree(G,indegree); /* 求出图中所有顶点的入度 */ for(i=0;iadjvex=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; } } void makeList(ALGraph &G) /*邻接表的构造*/ { int i; G.vexnum=9; for(i=0;iadjvex; if(ve[i]+p->weight>ve[j]) ve[j]=ve[i]+p->weight; p=p->nextarc; } } } void countvl(ALGraph G,int *topo,AdjType *ve, AdjType *vl) /*计算各事件的最迟发生时间*/ { int i,j,k; ArcNode *p; for(i=0;i=0;k--) /*下标从0开始，最后一个顶点无后继，所以减2*/ { i=topo[k]; p=G.vertices[i].firstarc; while(p!=NULL) { j=p->adjvex; if(vl[j]-p->weightweight; p=p->nextarc; } } } void counte_l(ALGraph G,AdjType *ve,AdjType *vl,AdjType *ee,AdjType *el) /*计算各活动的最早发生时间和最迟发生时间，并输出关键路径*/ { int i=0,j,k; ArcNode *p; cout<<"关键路径是： "; for(j=0;jadjvex; ee[i]=ve[j]; el[i]=vl[k]-p->weight; if(ee[i]==el[i]) cout<<"→"; i++; //i表示弧的序号。弧的序号自第一个顶点开始到最后一个顶点止顺序编号。 p=p->nextarc; } } } int CriticalPath(ALGraph G) /*关键路径算法*/ { AdjType ve[MAXVEX],vl[MAXVEX],ee[MAXEDGE],el[MAXEDGE]; int topo[MAXVEX]; if(topoSort(G,topo)==FALSE) /*求AOE网的一个拓扑序列*/ return FALSE; /*若有环则返回FALSE*/ countve(G,topo,ve); /*计算数组ve，ve存放事件可能的最早发生时间*/ countvl(G,topo,ve,vl); /*计算数组vl，vl存放事件可能的最迟发生时间*/ counte_l(G,ve,vl,ee,el); /*计算数组ee,el并输出结果*/ cout<<"\n"; /*数组ee存放活动的最早开始时间,数组el存放活动的最晚开始时间*/ return TRUE; } void main() /*主程序*/ { ALGraph G; makeList(G); if(CriticalPath(G)==FALSE) cout<<"There is no critical path!\n"; } 图6.22 上图的邻接表 各事件的最早发生时间数组ve变化情况： k 0 1 2 3 4 5 6 7 8 i=topo[k] 0 2 3 5 1 4 7 6 8 V0 0 0 0 0 0 0 0 0 0 0 0 V1 1 0 6 6 6 6 6 6 6 6 6 V2 2 0 4 4 4 4 4 4 4 4 4 V3 3 0 5 5 5 5 5 5 5 5 5 V4 4 0 0 5 5 5 7 7 7 7 7 V5 5 0 0 0 7 7 7 7 7 7 7 V6 6 0 0 0 0 0 0 16 16 16 16 V7 7 0 0 0 0 11 11 14 14 14 14 V8 8 0 0 0 0 0 0 0 18 18 18 各事件的最迟发生时间数组vl变化情况： k 7 6 5 4 3 2 1 0 i=topo[k] 6 7 4 1 5 3 2 0 V0 0 18 18 18 18 18 18 18 18 0 V1 1 18 18 18 18 6 6 6 6 6 V2 2 18 18 18 18 18 18 18 6 6 V3 3 18 18 18 18 18 18 7 8 8 V4 4 18 18 18 7 7 7 7 7 7 V5 5 18 18 18 18 18 10 10 10 10 V6 6 18 16 16 16 16 16 16 16 16 V7 7 18 18 14 14 14 14 14 14 14 V8 8 18 18 18 18 18 18 18 18 18 各事件和各活动的最早与最迟开始时间 下标 顶点（事件） ve vl 活动（弧） e(i) l(i) l(i)-e(i) 0 V0 0 0 a1 0 0 0 1 V1 6 6 a2 0 2 2 2 V2 4 6 a3 0 3 3 3 V3 5 8 a4 6 6 0 4 V4 7 7 a5 4 6 2 5 V5 7 10 a6 5 8 3 6 V6 16 16 a7 7 7 0 7 V7 14 14 a8 7 7 0 8 V8 18 18 a9 7 10 3 9 a10 16 16 0 10 a11 14 14 0 拓扑序列为：v0 v2 v3 v5 v1 v4 v7 v6 v8 关键路径是：，，，，， 即有两条关键路径：（v0，v1，v4，v6，v8）和（v0，v1，v4，v7，v8） 图6.23 图6.22所示图的关键路径 【算法分析】在算法6.13中，在求每个事件的最早和最迟发生时间，以及活动的最早和最迟开始时间时，都要对所有顶点及每个顶点边表中所有的边结点进行检查，由此，求关键路径算法的时间复杂度为O(n＋e)。 实践已经证明：用AOE-网来估算某些工程完成的时间是非常有用的。实际上，求关键路径的方法本身最初就是与维修和建造工程一起发展的。但是，由于网中各项活动是互相牵涉的，因此，影响关键活动的因素亦是多方面的，任何一项活动持续时间的改变都会影响关键路径的改变。由此可见，关键活动的速度提高是有限度的。只有在不改变网的关键路径的情况下，提高关键活动的速度才有效。 另一方面，若网中有几条关键路径，那么，单是提高一条关键路径上的关键活动的速度，还不能导致整个工程缩短工期，而必须提高同时在几条关键路径上的活动的速度。 PAGE 45