加载中…
个人资料
_陌上花开7_
_陌上花开7_
  • 博客等级:
  • 博客积分:0
  • 博客访问:68,244
  • 关注人气:29
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

AOE网与关键路径

(2013-08-20 22:04:42)
标签:

关键路径

aoe网

拓扑算法

it

分类: 数据结构

与AOV-网相对应的是AOE-网(Activity On Edge)即边表示活动的网。AOE-网是一个带权的有向无环图,其中,顶点表示事件(Event),弧表示活动,权表示活动持续的时间。通常,AOE-网可用来估算工程的完成时间。

最短路径只是某一点到另一点走的最快最短的路径,而关键路径以点为事件,线为过程,需要将所有工程完成时的路径,所以选最长路径为关键路径才能确保所有工程都完成。

AOV 网具有的性质

(1)只有在某顶点所代表的事件发生后,从该顶点出发的各有向边所代表的活动才能开始。

(2) 只有在进入某一顶点的各有向边所代表的活动都已经结束,该顶点所代表的事件才能发生。

(3)表示实际工程计划的 AOE 网应该是无环的,并且存在唯一的入度过为 的开始顶点和唯一的出度为 的完成顶点。

 

例如,如图是一个假想的有11项活动的AOE-网。其中有9个事件v1,v2,v3,…,v9,每个事件表示在它之前的活动已经完成,在它之后的活动可以开始。如v1表示整个工程开始,v9表示整个工程结束,v5表示a4和a5已经完成,a7和a8可以开始。与每个活动相联系的数是执行该活动所需的时间。比如,活动a1需要6天, a2需要4天等。

AOE网与关键路径

和AOV-网不同,对AOE-网有待研究的问题是:

      (1)完成整项工程至少需要多少时间?

      (2)哪些活动是影响工程进度的关键?

    由于在AOE-网中有些活动可以并行地进行,所以完成工程的最短时间是从开始点到完成点的最长路径的长度(这里所说的路径长度是指路径上各活动持续时间之和,不是路径上弧的数目)。路径长度最长的路径叫做关键路径(Critical Path)。假设开始点是v1,从v1到vi的最长路径长度叫做事件vi的最早发生时间。这个时间决定了所有以vi为尾的弧所表示的活动的最早开始时间。我们用e(i)表示活动ai的最早开始时间。还可以定义一个活动的最迟开始时间l(i),这是在不推迟整个工程完成的前提下,活动ai最迟必须开始进行的时间。两者之差l(i)-e(i)意味着完成活动ai的时间余量。我们把l(i)=e(i)的活动叫做关键活动。显然,关键路径上的所有活动都是关键活动,因此提前完成非关键活动并不能加快工程的进度。因此,分析关键路径的目的是辨别哪些是关键活动,以便争取提高关键活动的工效,缩短整个工期。

 

由上分析可知,辨别关键活动就是要找e(i)=l(i)的活动。为了求得AOE-网中活动的e(i)和l(i),首先求事件的最早发生时间ve(j)和最迟发生时间vl(j)。如果活动ai由弧表示,其持续时间记为dut(),则有如下关系:

            e(i) = ve(j)                                  

            l(i) = vl(k)-dut(<j,k>)  

      求ve(j)和vl(j)需分两步进行:

    (1)从ve(0)开始向前递推

           ve(j) = Max{ve(i)+(<i,j>)}

            i

            <i,j> ∈T, j=1,2,3,…,n-1            

     其中,T是所有以第j个顶点为尾的弧的结合。

(2)从vl(n-1)=ve(n-1)起向后递推

           vl(i) = Min{ vl (j) – dut(<i,j>)}

           j

            <i,j> ∈S ,   i=n-2,…,0    

其中,S是所有以第i个顶点为头的弧的集合。

    这两个递推公式的计算必须分别在拓扑有序和逆拓扑有序的前提下进行。也就是说ve(j-1)必须在vj的所有前驱的最早发生时间求得之后才能确定,而vl(j-1)则必须在vj的所有后继的最迟发生时间求得之后才能确定。因此,可以在拓扑排序的基础上计算ve(j-1)和vl(j-1)。

由此得到求关键路径的算法:

(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值,求每条弧s的最早开始时间e(s)和最迟开始时间 l(s)。若某条弧满足条件e(s)=l(s),则为关键活动。

先求拓扑排序算法再求关键路径的算法。

具体C++算法如下:

头文件algraph.h具体内容:

//---------------求出一个拓扑排序序列-----------------//

//
#ifndef ALGRAPH_H
#define ALGRAPH_H_

const int MaxSize=10;             //图中最大的顶点数
#define MaxEdge 100
struct ArcNode                   //定义边表结点
{
 int adjvex;                  //邻接点域
 int weight;
 ArcNode *next;
};

struct VertexNode                 //定义定点表
{
 int vertext;
 ArcNode *firstedge;
 int in;
};

class ALGraph
{
 public:
  ALGraph();
  ALGraph(int a[],int n,int e);   //构造函数,建立一个有n个顶点e条边的图
  ~ALGraph();
  void TopSort(ALGraph G);

  void countve(ALGraph G,int *topo,int *ve);//各事件的最早发生时间
  void countvl(ALGraph G,int *topo,int *ve,int *vl);//各事件的最迟发生时间
  void counte_l(ALGraph G,int *ve,int *vl,int *ee,int *el);//计算各活动的最早发生时间和最迟发生时间
  
 private:
  VertexNode adjlist[MaxSize];
  int vertexNum,arcNum;             //定义顶点数和边数
};
#endif

 

aoe.cpp内容如下:

#include <iostream>
#include"ALGraph.h"
#include<stack>

using namespace std;

//各事件的最早发生时间
void ALGraph::countve(ALGraph G,int *topo,int *ve)
{
 int i,j,k;
 ArcNode *p;
 for(i=0;i<G.vertexNum;i++)
  ve[i]=0;                     

 int count=0;
 int topo[MaxSize];

 stack<int> S;

 for(int i=0;i<G.vertexNum;i++)
  if(G.adjlist[i].in==0)
   S.push(i);
  
//   cout<<S.top();
//   S.pop();
//  
//   cout<<S.top();
//   S.pop();
  
  while(S.empty()==false)
  {
   int m=S.top();
   S.pop();
   std::cout<<G.adjlist[m].vertext<<"---";
   topo[count++]=G.adjlist[m].vertext;        //把拓扑结构存入topo数组中

 

  // count++;
   ArcNode *p;
   p=G.adjlist[m].firstedge;
   while (p!=NULL)
   {
    int k=p->adjvex;
    G.adjlist[k].in--;
    if (G.adjlist[k].in==0)
     S.push(k);
     
    p=p->next;
    
   }
  }
  if(count<G.vertexNum)
   std::cout<<"有回路";
  
   int ve[MaxSize];
   int vl[MaxSize];
   int ee[MaxEdge];
   int el[MaxEdge];
   //计算各事件的最早发生时间

   countve(G,topo,ve);
   countvl(G,topo,ve,vl);
   counte_l(G,ve,vl,ee,el);
}

主函数文件main.cpp如下:

#include <iostream>
#include "ALGraph.h"

using namespace std;
int main()
{
 //初始化
 int b[MaxSize];
 for(int i=0;i<MaxSize;i++)
 {
  b[i]=i;
 }

 ALGraph G(b,9,11);
 G.TopSort(G);

 return 0;
}

输出:

AOE网与关键路径

 

由图可知:

拓扑序列为:v1  v3  v4  v6  v2  v5  v8  v7  v9

关键路径是:,,,,,

即有两条关键路径:(v1,v2,v5,v7,v9)和(v1,v2,v5,v8,v9) ‘

AOE网与关键路径

实践已经证明:用AOE-网来估算某些工程完成的时间是非常有用的。实际上,求关键路径的方法本身最初就是与维修和建造工程一起发展的。但是,由于网中各项活动是互相牵涉的,因此,影响关键活动的因素亦是多方面的,任何一项活动持续时间的改变都会影响关键路径的改变。由此可见,关键活动的速度提高是有限度的。只有在不改变网的关键路径的情况下,提高关键活动的速度才有效。

    另一方面,若网中有几条关键路径,那么,单是提高一条关键路径上的关键活动的速度,还不能导致整个工程缩短工期,而必须提高同时在几条关键路径上的活动的速度。

 

注意:

并不是加快任何一个关键活动都可以缩短整个工程完成的时间,只有加快那些包括在所有的关键路径上的关键活动才能达到这个目的。只有在不改变AOE 网的关键路径的前提下,加快包含在关键路径上的关键活动才可以缩短整个工程的完成时间。

(1) 求关键路径必须在拓扑排序的前提下进行,有环图不能求关键路径;
(2) 只有缩短关键活动的工期才有可能缩短工期;
(3) 若一个关键活动不在所有的关键路径上,减少它并不能减少工期;
(4) 只有在不改变关键路径的前提下,缩短关键活动才能缩短整个工期。

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有