最新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，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
#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;ifor（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;iif（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]weight）//更新顶点j的最早发生时间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;ifor（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;iif（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;iG.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;ifor（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;ivl[i]=ve[G.vexnum-1];/*每个事件的最迟发生时间赋初值为最生事件的最早发生时间
升级会员 