精华内容
下载资源
问答
  • AOE网求关键路径

    千次阅读 2014-08-05 11:23:06
    下表给出了某工程各工序之间的优先关系和各工序所需的时问(其中“一”表示无先驱工序),请完成...(3) 关键路径并指明完成该工程所需的最短时间。 工序代号 A B C D

    下表给出了某工程各工序之间的优先关系和各工序所需的时问(其中“一”表示无先驱工序),请完成以下各题:

    (1)      画出相应的AOE网。

    (2)      列出各事件的最早发生时间和最迟发生时间。

    (3)      求出关键路径并指明完成该工程所需的最短时间。

    工序代号

    A

    B

    C

    D

    E

    F

    G

    H

    所需时间

    3

    2

    2

    3

    4

    3

    2

    1

    先驱工序

    A

    A

    B

    A

    CE

    D

      

    【例题分析】

    ·       试题考核AOE网和关键路径问题。要求熟悉AOE网的概念和如何求关键路径的方法及步骤。

    【例题解答】

    (1)     根据表的数据,可得AOE网,如图所示。

    ☆求解AOE网关键路径例题 - 浮山园 - 〓 浮山园 〓

     

       (2)      所有事件的最早发生时间ve,如下所示:

    ve(v1)= 0          ve(v2)= 3            ve(v3)= 2

    ve(v4)= Max{ ve(v2)+2,ve(v3)+4}= 6 

    ve(v5)= ve(v2)+3 = 6  

    ve(v6)= Max{ ve(v3)+3,ve(v4)+2,ve(v5)+1}= 8

        所有事件的最迟发生时间vl,如下所示:

        vl(v6)= 8    vl(v5)=vl(v6)-1= 7   vl(v4)=vl(v6)-2 = 6

    vl(v3)= Min{ vl(v4)-4,vl(v6)-3}= 2

    vl(v2)= Min{ vl(v4)-2,vl(v5)-3}= 4

    vl(v1)= Min{ vl(v2)-3,vl(v3)-2}= 0

    (3)      求所有活动的最早发生时间e、最迟发生时间l和时间余量l-e。

    e(A)=ve(v1)= 0    l(A)=vl(v2)-3= 1   l(A)-e(A)= 1

    e(B)=ve(v1)= 0    l(B)=vl(v3)-2= 0   l(B)-e(B)= 0

    e(C)=ve(v2)= 3    l(C)=vl(v4)-2= 4   l(C)-e(C)= 1

    e(D)=ve(v2)= 3    l(D)=vl(v5)-3= 4   l(D)-e(D)= 1

    e(E)=ve(v3)= 2    l(E)=vl(v4)-4= 2    l(E)-e(E)= 0

    e(F)=ve(v3)= 2    l(F)=vl(v6)-3= 5    l(F)-e(F)= 3

    e(G)=ve(v4)= 6    l(G)=vl(v6)-2= 6   l(G)-e(G)= 0

    e(H)=ve(v5)= 6    l(H)=vl(v6)-1= 7   l(H)-e(H)= 1

    所以,关键路径为:B、E、G。

    完成该工程最少需要8天时间。

    展开全文
  • AOE网求关键路径(关键活动): AOE网求解关键路径,所需的是有向无环图,注意的是,只有一个源点,有一个汇顶点,然后关键路径不一定只有一条。注意,这里要理解: 顶点:事件 边:活动 还有四个数组下面有介绍: ...

    AOE网求关键路径(关键活动):

    AOE网求解关键路径,所需的是有向无环图(利用拓扑排序,如果序列长度为顶点数,则是无环,小于顶点数则是有环图,有环图是不满足求AOE网的),注意的是,只有一个源点,有一个汇顶点,然后关键路径不一定只有一条。注意,这里要理解:

    顶点:事件
    边:活动

    还有四个数组下面有介绍:
    在这里插入图片描述
    在这里插入图片描述
    这里我们用到的图:

    关键活动已经用红色标记出来
    在这里插入图片描述

    代码如下:

    #include <stdio.h>
    #include <malloc.h>
    #define inf 330 
    #define max 50
    typedef struct node{
    	int adjvex;
    	int weight; //权值 
    	struct node *nextarc;
    }arcnode;//定义结点的结构体类型 
    
    typedef struct {
    	arcnode *firstarc;
    	int count; 
    }vnnode; //定义头结点的结构体 
    
    typedef struct {
    	vnnode  adjlist[max];
    	int n;
    	int e; 
    }adjgraph; //定义图表的结构体类型 
    
    typedef struct{
    	int sno;
    	int lno;
    }keynode; //关键活动 
    
    
    //创建邻接图 
    void createadj(adjgraph *&g, int a[max][max], int n, int e)
    {
    	arcnode *p;
    	
    	//分配一段空间,并做相应的赋值操作。 
    	g = (adjgraph *)malloc(sizeof(adjgraph));
    	g->n = n;
    	g->e = e;
    	
    	//对头结点初始化为NULL 
    	for(int i = 0 ;i <n; i++)
    	{
    		g->adjlist[i].firstarc = NULL;
    		g->adjlist[i].count = 0;
    	}
    	
    	 //循环找结点 
    	for(int i =0; i<n; i++)
    	 for(int j = n-1; j>=0; j--)
    	 	 if(a[i][j]!=0 && a[i][j]!=inf)//如果有边 
    		 {
    		 	p = (arcnode *)malloc(sizeof(arcnode));
    		 	p->adjvex =j;
    		 	p->weight = a[i][j];
    		 	g->adjlist[j].count++;
    		     
    		    //这里采用头插发 
    		 	p->nextarc = g->adjlist[i].firstarc;
    			g->adjlist[i].firstarc = p;  
    		  } 
     } 
     
    
    //输入图的邻接表 
     void showadj(adjgraph *g)
     {
     	arcnode *p;
     	for(int i =0; i< g->n; i++)
     	{
     		//首先指向头结点。 
     		p = g->adjlist[i].firstarc;
     		printf("%d 入度:(%d): ",i,g->adjlist[i].count);
     		
     		//这里是循环输出每个头结点的链表 
     		while(p!=NULL)
     		{
     			printf("%d -->",p->adjvex);
     			p = p->nextarc;
    		 }
    		 printf("/\\");
    		 printf("\n"); 
    	 }
     }
     
    
    //拓扑排序输出 
    /*算法的主要思想,一个是找入度为0的顶点进栈,二个每次出栈一个顶点,
    就要遍历其他相关有边的顶点,修改顶点入度,并判断是否入栈,不满足就寻找下一个相关有边的顶点。 
    */ 
    int  tp(adjgraph *g,int toplist[]) //参数数组toplist是用来保存拓扑序列的,用来判断是否成环 
    {
    	arcnode *p;
    	
    	//定义一个数组栈以及数组下标 
    	int st[max]; 
    	int top = -1; 
    	int d=0;
    	
    	int j,k;//定义两个变量,下面需要用到 
    	
    	//这个循环用来遍历所有点,找到入度为0的点将其进栈。 
    	for(int i=0; i<g->n; i++)
    	  if(g->adjlist[i].count ==0)
    	  {
    	  	 top++;
    	  	 st[top] = i;
    	   } 
    	   
    	 //在栈不空的情况下,出栈一个顶点,然后将这个顶点的所有有边的另外一端的顶点循环判断,如果入度为0,则进栈。遍历完之后接着出栈一个顶点,在遍历....循环同样的操作 
    	 while(top>-1)
    	 {
    	 	//出栈一个顶点 
    	   k = st[top--];
    	   toplist[d++]=k;
    	   printf("%d ",k);
    	   
    	   //在遍历该出栈顶点的其他有边的顶点 
    	   p = g->adjlist[k].firstarc;
    	   while(p!=NULL)
    	   {
    	   	 //度数-1 
    	   	   j = p->adjvex;
    		   g->adjlist[j].count--;
    		   
    		   //在判断是否可以入栈 
    			if(g->adjlist[j].count == 0 )
    			{
    				top++;
    				st[top] =j;
    			} 
    			
    		//遍历下一个顶点。 
    		 p =p ->nextarc;
    	   }
    	 }
        return d; //返回拓扑数组的长度 ,注意下标 
     } 
     
     
     //aoe求关键活动 
     /*算法的主要思想是求出事件的最早开始时间,(ve[max])
     事件的最迟开始时间,(vl[max])
     活动的最早开始时间,(ea[max])
     活动的最迟开始时间。(el(max))
      然后用一个结构体数组保存关键活动以及两端的顶点。 
     */ 
     bool aoesearch(adjgraph *g, keynode ky[max], int &d)///结构体数组,以及下标d 
     {
     	arcnode *p;
    
        int toplist[max]; //这里用来保存调用拓扑排序函数是保存拓扑序列 
        
     	int w;
     	
     	int ve[max]; //用来保存事件(顶点)最早开始时间 
     	int vl[max];//用来保存事件(顶点)最迟开始时间 
     	
     	int length = tp(g,toplist);//拓扑排序 
     	
        if(length  < g->n) //拓扑排序长度若小于顶点数,则说明有回路 
        return false;
        
        int inode = toplist[0]; //找打源点 
        int lnode = toplist[g->n-1];//找到汇点 
       
       
    	//初始化,每个事件的最早开始时间为0 
    	for(int i=0;i< g->n; i++)
    	{
        	ve[i] = 0;	
    	}
    	//找每个事件的最早开始事件。(找最大) 
    	for(int i =0; i<g->n; i++)
    	{
    		p = g->adjlist[i].firstarc;
    		while(p!=NULL)
    		{
    		    w = p->adjvex;
    			if(ve[i]+ p->weight> ve[w])
    			  ve[w] = ve[i]+ p->weight;
    			p = p->nextarc;
    		}
    	}
    	
    	//初始化,每个事件的最晚开始事件为汇点的最早开始时间 
    	for(int i =0; i<g->n; i++)
    	   vl[i] = ve[lnode];
    	   
    	//逆序找每个事件的最晚开始事件(找最小) 
    	for(int i= g->n-2; i>=0; i--)//
    	{
    		p = g->adjlist[i].firstarc;
    		while(p!=NULL)
    		{
    			w = p->adjvex;
    			if( vl[w] - p->weight <vl[i])
    				vl[i] = vl[w] - p->weight;
    			p = p->nextarc;
    		}
    	}
    
        //找关键活动((存储到结构体数组中)
        for(int i =0; i<g->n; i++)
    	{	
    		p = g->adjlist[i].firstarc;
    		
    		while(p!= NULL)
    		{
    			w = p->adjvex;
    			//注意,由于没定义活动(边)的最早开始时间ae[i]和最迟开始时间al[j],这里ae[i] = i,al[i] = vl[w] - p->weight,这里的ae和al表示活动的最早开始时间和最迟开始时间。 
    			if(ve[i] == (vl[w] - p->weight)) 
    			{
    				d++;
    				ky[d].sno = i;
    				ky[d].lno = w;
    			}
    		 p = p->nextarc; 
    		}
    	}   	  
    	return true;  
    }
    void showpath(adjgraph *g, keynode ky[],int d)
    {
       
    	arcnode *p;
    	int w;
    	int length =d;
        
    	for(int i =0; i<g->n; i++)
    	{
    		p = g->adjlist[i].firstarc;
    		
    		     while(p!=NULL)
    	     	{
    	     		
    		    	w = p->adjvex;
    		    	for(int j =0; j<=length; j++)  //这里之所以等于0,是因为d是从-1开始,第一个值的下标就是0,而不是从0开始,第一个值下标是1; 
    			    if(i == ky[j].sno && w == ky[j].lno)
    			    {
    			    	printf("(%d,%d):%d  \n",i,w,p->weight);
    				}
    				p = p->nextarc;
    		    }
    			
    		
    	}
    }
    
    int main() 
    {
    	adjgraph *b;
    	int d=-1; //用于结构体数组的下标 
    	
    	keynode ky[max];
    	int toplist[max];
    	
    	int a[max][max] = {{0,6,4,5,inf,inf,inf,inf,inf},
    	                   {inf,0,inf,inf,1,inf,inf,inf,inf},
    					   {inf,inf,0,inf,1,inf,inf,inf,inf},
    					   {inf,inf,inf,0,inf,inf,inf,2,inf},
    					   {inf,inf,inf,inf,0,9,7,inf,inf},
    					   {inf,inf,inf,inf,inf,0,inf,inf,2},
    					   {inf,inf,inf,inf,inf,inf,0,inf,4},
    					   {inf,inf,inf,inf,inf,inf,inf,0,4},
    					   {inf,inf,inf,inf,inf,inf,inf,inf,0}};
    	int n= 9;
    	int e= 11;
    	createadj(b,a,n,e);
    	showadj(b);
    	printf("\n拓扑排序输出序列为: "); 
    	aoesearch(b,ky,d);
    	printf("\n ");
    	printf("\n关键活动如下:\n");
    	showpath(b,ky,d);
    	return 0;
    }
    
    

    程序运行如下:
    在这里插入图片描述

    展开全文
  • 有良好界面的JAVA编写的AOE网络关键路径,比较完善
  • 在学习拓扑排序一节时讲到拓扑排序只适用于 AOV ,本节所介绍的求关键路径针对的是和 AOV 相近的 AOE 。什么是AOE网AOE 是在 AOV 的基础上,其中每一个边都具有各自的权值,是一个有向无环。其中权值...

    在学习拓扑排序一节时讲到拓扑排序只适用于 AOV 网,本节所介绍的求关键路径针对的是和 AOV 网相近的 AOE 网。

    什么是AOE网

    AOE 网是在 AOV 网的基础上,其中每一个边都具有各自的权值,是一个有向无环网。其中权值表示活动持续的时间。

    165eeadfa38120343f367bd9d2935224.png

    图 1 AOE网

    如图 1 所示就是一个 AOE 网,例如 a1=6 表示完成 a1 活动完成需要 6 天;AOE 网中每个顶点表示在它之前的活动已经完成,可以开始后边的活动,例如 V5 表示 a4 和 a5 活动已经完成,a7 和 a8 可以开始。

    使用 AOE 网可以帮助解决这样的问题:如果将 AOE 网看做整个项目,那么完成整个项目至少需要多少时间?

    解决这个问题的关键在于从 AOE 网中找到一条从起始点到结束点长度最长的路径,这样就能保证所有的活动在结束之前都能完成。

    起始点是入度为 0 的点,称为“源点”;结束点是出度为 0 的点,称为“汇点”。这条最长的路径,被称为”关键路径“。

    为了求出一个给定 AOE 网的关键路径,需要知道以下 4 个统计数据:

    对于 AOE 网中的顶点有两个时间:最早发生时间(用 Ve(j) 表示)和最晚发生时间(用 Vl(j) 表示);

    对于边来说,也有两个时间:最早开始时间(用 e(i) 表示)和最晚开始时间( l(i) 表示)。

    Ve(j):对于 AOE 网中的任意一个顶点来说,从源点到该点的最长路径代表着该顶点的最早发生时间,通常用 Ve(j) 表示。

    例如,图 1 中从 V1 到 V5 有两条路径,V1 作为源点开始后,a1 和 a2 同时开始活动,但由于 a1 和 a2 活动的时间长度不同,最终 V1-V3-V5 的这条路径率先完成。但是并不是说 V5 之后的活动就可以开始,而是需要等待 V1-V2-V5 这条路径也完成之后才能开始。所以对于 V5 来讲,Ve(5) = 7。

    Vl(j):表示在不推迟整个工期的前提下,事件 Vk 允许的最晚发生时间。

    例如,图 1 中,在得知整个工期完成的时间是 18 天的前提下,V7 最晚要在第 16 天的时候开始,因为 a10 活动至少需要 2 天时间才能完成,如果在 V7 事件在推迟,就会拖延整个工期。所以,对于 V7 来说,它的 Vl(7)=16。

    e(i):表示活动 ai 的最早开始时间,如果活动 ai 是由弧 表示的,那么活动 ai 的最早开始的时间就等于时间 Vk 的最早发生时间,也就是说:e[i] = ve[k]。

    e(i)很好理解,拿图 1 中 a4 来说,如果 a4 想要开始活动,那么首先前提就是 V2 事件开始。所以 e[4]=ve[2]。

    l(i):表示活动 ai 的最晚开始时间,如果活动 ai 是由弧 表示,ai 的最晚开始时间的设定要保证 Vj 的最晚发生时间不拖后。所以,l[i]=Vl[j]-len。

    在得知以上四种统计数据后,就可以直接求得 AOE 网中关键路径上的所有的关键活动,方法是:对于所有的边来说,如果它的最早开始时间等于最晚开始时间,称这条边所代表的活动为关键活动。由关键活动构成的路径为关键路径。

    AOE网求关键路径实现过程

    对图 1 中的 AOE 图求关键路径,首先完成 Ve(j)、Vl(j)、e(i)、l(i) 4 种统计信息的准备工作。

    Ve(j),求出从源点到各顶点的最长路径长度为(长度最大的):

    60783f7e6e0b3df5209a1d0f674e8601.png

    Vl(j),求出各顶点的最晚发生时间(从后往前推,多种情况下选择最小的):

    f0e224500e4fe9dc3b0e34ea62241c5d.png

    e(i),求出各边中ai活动的最早开始时间:

    a0136595e71127e09d974e3452569843.png

    l(i),求各边中ai活动的最晚开始时间(多种情况下,选择最小的):

    e4124b3da203dbeeae8dff06033eb4e8.png

    通过对比 l(i) 和 e(i) ,其中 a1 、 a4 、 a7 、 a8 、 a10 、 a11 的值都各自相同,所以,在图 1 中的 AOE 网中有两条关键路径:

    3cb1a6e2165d79d2bf460a65dcd48abf.png

    图 2 关键路径

    AOE 网计算关键路径的 C 语言代码实现为:

    #include

    #include

    #define MAX_VERTEX_NUM 20//最大顶点个数

    #define VertexType int//顶点数据的类型

    typedef enum{false,true} bool;

    //建立全局变量,保存边的最早开始时间

    VertexType ve[MAX_VERTEX_NUM];

    //建立全局变量,保存边的最晚开始时间

    VertexType vl[MAX_VERTEX_NUM];

    typedef struct ArcNode{

    int adjvex;//邻接点在数组中的位置下标

    struct ArcNode * nextarc;//指向下一个邻接点的指针

    VertexType dut;

    }ArcNode;

    typedef struct VNode{

    VertexType data;//顶点的数据域

    ArcNode * firstarc;//指向邻接点的指针

    }VNode,AdjList[MAX_VERTEX_NUM];//存储各链表头结点的数组

    typedef struct {

    AdjList vertices;//图中顶点及各邻接点数组

    int vexnum,arcnum;//记录图中顶点数和边或弧数

    }ALGraph;

    //找到顶点对应在邻接表数组中的位置下标

    int LocateVex(ALGraph G,VertexType u){

    for (int i=0; i

    if (G.vertices[i].data==u) {

    return i;

    }

    }

    return -1;

    }

    //创建AOE网,构建邻接表

    void CreateAOE(ALGraph **G){

    *G=(ALGraph*)malloc(sizeof(ALGraph));

    scanf("%d,%d",&((*G)->vexnum),&((*G)->arcnum));

    for (int i=0; ivexnum; i++) {

    scanf("%d",&((*G)->vertices[i].data));

    (*G)->vertices[i].firstarc=NULL;

    }

    VertexType initial,end,dut;

    for (int i=0; iarcnum; i++) {

    scanf("%d,%d,%d",&initial,&end,&dut);

    ArcNode *p=(ArcNode*)malloc(sizeof(ArcNode));

    p->adjvex=LocateVex(*(*G), end);

    p->nextarc=NULL;

    p->dut=dut;

    int locate=LocateVex(*(*G), initial);

    p->nextarc=(*G)->vertices[locate].firstarc;

    (*G)->vertices[locate].firstarc=p;

    }

    }

    //结构体定义栈结构

    typedef struct stack{

    VertexType data;

    struct stack * next;

    }stack;

    stack *T;

    //初始化栈结构

    void initStack(stack* *S){

    (*S)=(stack*)malloc(sizeof(stack));

    (*S)->next=NULL;

    }

    //判断栈是否为空

    bool StackEmpty(stack S){

    if (S.next==NULL) {

    return true;

    }

    return false;

    }

    //进栈,以头插法将新结点插入到链表中

    void push(stack *S,VertexType u){

    stack *p=(stack*)malloc(sizeof(stack));

    p->data=u;

    p->next=NULL;

    p->next=S->next;

    S->next=p;

    }

    //弹栈函数,删除链表首元结点的同时,释放该空间,并将该结点中的数据域通过地址传值给变量i;

    void pop(stack *S,VertexType *i){

    stack *p=S->next;

    *i=p->data;

    S->next=S->next->next;

    free(p);

    }

    //统计各顶点的入度

    void FindInDegree(ALGraph G,int indegree[]){

    //初始化数组,默认初始值全部为0

    for (int i=0; i

    indegree[i]=0;

    }

    //遍历邻接表,根据各链表中结点的数据域存储的各顶点位置下标,在indegree数组相应位置+1

    for (int i=0; i

    ArcNode *p=G.vertices[i].firstarc;

    while (p) {

    indegree[p->adjvex]++;

    p=p->nextarc;

    }

    }

    }

    bool TopologicalOrder(ALGraph G){

    int indegree[G.vexnum];//创建记录各顶点入度的数组

    FindInDegree(G,indegree);//统计各顶点的入度

    //建立栈结构,程序中使用的是链表

    stack *S;

    //初始化栈

    initStack(&S);

    for (int i=0; i

    ve[i]=0;

    }

    //查找度为0的顶点,作为起始点

    for (int i=0; i

    if (!indegree[i]) {

    push(S, i);

    }

    }

    int count=0;

    //栈为空为结束标志

    while (!StackEmpty(*S)) {

    int index;

    //弹栈,并记录栈中保存的顶点所在邻接表数组中的位置

    pop(S,&index);

    //压栈,为求各边的最晚开始时间做准备

    push(T, index);

    ++count;

    //依次查找跟该顶点相链接的顶点,如果初始入度为1,当删除前一个顶点后,该顶点入度为0

    for (ArcNode *p=G.vertices[index].firstarc; p ; p=p->nextarc) {

    VertexType k=p->adjvex;

    if (!(--indegree[k])) {

    //顶点入度为0,入栈

    push(S, k);

    }

    //如果边的源点的最长路径长度加上边的权值比汇点的最长路径长度还长,就覆盖ve数组中对应位置的值,最终结束时,ve数组中存储的就是各顶点的最长路径长度。

    if (ve[index]+p->dut>ve[k]) {

    ve[k]=ve[index]+p->dut;

    }

    }

    }

    //如果count值小于顶点数量,表明有向图有环

    if (count

    printf("该图有回路");

    return false;

    }

    return true;

    }

    //求各顶点的最晚发生时间并计算出各边的最早和最晚开始时间

    void CriticalPath(ALGraph G){

    if (!TopologicalOrder(G)) {

    return ;

    }

    for (int i=0 ; i

    vl[i]=ve[G.vexnum-1];

    }

    int j,k;

    while (!StackEmpty(*T)) {

    pop(T, &j);

    for (ArcNode* p=G.vertices[j].firstarc ; p ; p=p->nextarc) {

    k=p->adjvex;

    //构建Vl数组,在初始化时,Vl数组中每个单元都是18,如果每个边的汇点-边的权值比源点值小,就保存更小的。

    if (vl[k]-p->dut

    vl[j] = vl[k]-p->dut;

    }

    }

    }

    for (j = 0; j < G.vexnum; j++) {

    for (ArcNode*p = G.vertices[j].firstarc; p ;p = p->nextarc) {

    k = p->adjvex;

    //求各边的最早开始时间e[i],等于ve数组中相应源点存储的值

    int ee = ve[j];

    //求各边的最晚开始时间l[i],等于汇点在vl数组中存储的值减改边的权值

    int el = vl[k]-p->dut;

    //判断e[i]和l[i]是否相等,如果相等,该边就是关键活动,相应的用*标记;反之,边后边没标记

    char tag = (ee==el)?'*':' ';

    printf("%3d%3d%3d%3d%3d%2c\n",j,k,p->dut,ee,el,tag);

    }

    }

    }

    int main(){

    ALGraph *G;

    CreateAOE(&G);//创建AOE网

    initStack(&T);

    TopologicalOrder(*G);

    CriticalPath(*G);

    return 0;

    }

    拿图 1 中的 AOE 网为例,运行的结果为:

    9,11

    1

    2

    3

    4

    5

    6

    7

    8

    9

    1,2,6

    1,3,4

    1,4,5

    2,5,1

    3,5,1

    4,6,2

    5,7,9

    5,8,7

    6,8,4

    7,9,2

    8,9,4

    0  3  5  0  3

    0  2  4  0  2

    0  1  6  0  0 *

    1  4  1  6  6 *

    2  4  1  4  6

    3  5  2  5  8

    4  7  7  7  7 *

    4  6  9  7  7 *

    5  7  4  7 10

    6  8  2 16 16 *

    7  8  4 14 14 *

    通过运行结果,可以看出关键活动有 6 个(后面带有 * 号的),而组成的关键路径就如图 2 中所示。

    展开全文
  • 关于AOE网求关键路径

    千次阅读 2014-02-17 16:58:56
    认识AOE网  有向图中,用顶点表示活动,用有向边表示活动之间开始的先后顺序,则称这种有向图为AOV网络;AOV网络可以反应任务完成的先后顺序(拓扑排序)。  在AOV的边上加上权值表示完成该活动所需的时间,则称...

    认识AOE网

      有向图中,用顶点表示活动,用有向边表示活动之间开始的先后顺序,则称这种有向图为AOV网络;AOV网络可以反应任务完成的先后顺序(拓扑排序)。

      在AOV网的边上加上权值表示完成该活动所需的时间,则称这样的AOV网为AOE网,如下图: 


      


      图中,顶点表示事件(能被触发,两特征属性:最早发生时间Ve(j);最晚发生时间Vl(j)),边表示活动(能被开始,两特征属性:最早开始时间e(i);最晚开始时间l(i)),权表示活动持续时间,通常用AOE网来估算工程完成的时间


    两条原则:

      ?  只有某顶点所代表的事件发生后,从该顶点出发的各活动才能开始

      ?  只有进入某顶点的各活动都结束,该顶点所代表的事件才能发生


    计算关键路径

      首先,在AOE网中,从始点到终点具有最大路径长度(该路径上的各个活动所持续的时间之和)的路径为关键路径。

    计算关键路径,只需求出上面的四个特征属性,然后取e(i)=l(i)的边即为关键路径上的边(关键路径可能不止一条)。

      先来看看四个特征属性的含义:

      ? Ve(j):是指从始点开始到顶点Vk的最大路径长度


       计算技巧:

       (1)从前向后,取大值:直接前驱结点的Ve(j)+到达边(指向顶点的边)的权值,有多个值的取较大者

       (2)首结点Ve(j)已知,为0


      如上图各顶点(事件)的Ve(j): (从V1开始)


      


      ?  Vl(j):在不推迟整个工期的前提下,事件vk允许的最晚发生时间


       计算技巧:

       (1)从后向前,取小值:直接后继结点的Vl(j) –发出边(从顶点发出的边)的权值,有多个值的取较小者;

       (2)终结点Vl(j)已知,等于它的Ve(j)


      如上图各顶点(事件)的Vl(j): (从V7开始,它的最早、最晚发生时间相同,都为10):


      


     

      ?  e(i): 若活动ai由弧<vk,vj>表示,则活动ai的最早开始时间应该等于事件vk的最早发生时间。因而,有:e[i]=ve[k];(即:边(活动)的最早开始时间等于,它的发出顶点的最早发生时间

    如上图各边(活动)的e(i):


      


      ?  l(i): 若活动ai由弧<vk,vj>表示,则ai的最晚开始时间要保证事件vj的最迟发生时间不拖后。 因而有:l[i]=vl[j]-len<vk,vj>1(为边(活动)的到达顶点的最晚发生时间减去边的权值

    如上图各边(活动)的l(i):


      


      至此已介绍完了四个特征属性的求法,也求出了上图中边的e(i)和l(i),取出e(i)=l(i)的边为a1、a2、a4、a8、a9,即为关键路径上的边,所以关键路径有两条:a1 a4 a9和 a2 a8 a9


      


    总结

      求关键路径,只需理解顶点(事件)和边(活动)各自的两个特征属性以及求法即可:

       ?  先根据首结点的Ve(j)=0由前向后计算各顶点的最早发生时间

       ?  再根据终结点的Vl(j)等于它的Ve(j)由后向前依次求解各顶点的最晚发生时间

       ?  根据边的e(i)等于它的发出顶点的Ve(j)计算各边的最早开始时间(最早开始,对应最早发生)

       ?  根据边的l(i)等于它的到达顶点的Vl(j)减去边的权值计算各边的最晚开始时间(最晚开始,对应最晚发生)

     

    转自http://blog.csdn.net/wang379275614/article/details/13990163
    展开全文
  • 出所给的AOE关键路径出所给的AOE-关键路径出所给的AOE关键路径。 输入 若干行整数,第一行有2个数,分别为顶点数v和弧数a,接下来有a行,每一行有3个数,分别是该条弧所关联的两个顶点...
  • 【笔记】AOE网关键路径

    万次阅读 多人点赞 2017-12-02 01:06:32
    AOE网 关键路径 求关键路径的算法实现
  • 求AOE网络关键路径

    2012-07-09 02:54:44
    用C++实现的代码,求AOE网络的关键路径,有详细注释
  • AOE网络-关键路径

    千次阅读 多人点赞 2018-10-15 18:25:32
    拓扑排序的另一个应用就是关键路径的问题,关键路径对应的是另一种网络:AOE网络。先回顾下拓扑排序中讲到的AOV网络,AOV网络即“Activity On Vertex”,即图上每一个顶点表示的是一个事件或者说一个活动,而顶点...
  • AOE-网求关键路径

    2020-08-17 18:43:20
    AOE-网求关键路径 AOE-,即边表示活动的。 活动的最早发生时间和最迟发生时间相同的活动即为关键活动。 代码实现 算法详解见注释 //各顶点事件的最早发生时间ve Status TopologicalOrder(ALGraph G,Stack &...
  • AOE 求关键路径 程序

    2010-12-02 17:49:27
    本程序用c#编写,实现了建图,利用AOE实现求解关键路径问题,并标明那些路径为关键路径
  • 利用AOE网求解关键路径问题

    千次阅读 2017-05-08 19:20:37
    利用AOE网求解关键路径问题,输出一个工程的所有关键活动。
  • AOE网关键路径

    千次阅读 2018-08-20 10:19:51
      AOE网是以边表示活动的有向无环,在AOE网中,具有最大路径长度的路径称为关键路径关键路径表示完成工程的最短工期。 1.AOE网   AOE网是一个带权的有向无环图。其中用顶点表示事件,弧表示活动,权值表示...
  • 图论- AOE 关键路径.rar
  • AOE 求关键路径程序

    2010-12-02 17:55:02
    本程序实现了根据你所输入的数据建图,并利用AOE求出最长路径长度,并标明关键路径
  • AOE网关键路径 在一个表示工程的带权有向图中,用顶点表示事件,用有向边表示活动,边上的权值表示活动持续的时间,称这样的有向图为边表示活动的,简称 AOE网(activity on edge network)。AOE网中没有入边的...
  • 一、关键路径 (一)AOE网 在带权有向图中,以顶点表示事件,以有向边表示活动,以边上的权值表示完成该活动的开销(如完成活动所需的时间),称之为⽤边表示活动的网络,简称AOE网 (Activity On Edge NetWork) 在...
  • AOE求关键路径

    2019-12-19 18:48:04
    Aoe的思路就是,分别活动的最早发生时间,以及活动的最晚发生时间。...3:求关键路径 查看 提交 统计 提问 总时间限制: 10000ms 单个测试点时间限制: 1000ms 内存限制: 65536kB 描述 出所给的AOE-...
  • 算法:求解AOE网关键路径

    万次阅读 多人点赞 2013-05-02 20:35:03
    前面我们简要地介绍了AOE网关键路径的一些概念,本文接着对求解关键路径程序的主要函数进行分析。现有一AOE网图如图7-9-4所示,我们使用邻接表存储结构,注意与拓扑排序时邻接表结构不同的地方在于,这里弧表结点...
  • 选择题快速求解AOE网关键路径

    千次阅读 多人点赞 2020-11-28 12:12:26
    求解AOE网关键路径时,书上的方法为先从源点到汇点求解事件最早发生时间ve,再从汇点到源点求解事件最迟发生时间vl,再利用ve和vl求解每个活动的最早开始时间e(i)和最迟开始时间l(i),e(i)和l(i)相等的活动则为关键...
  • 求AOE网关键路径

    2013-06-26 17:22:06
    AOE-(Activity on Edge),即边表示活动的。若在带权的有向无环图G中,顶点表示事件(Event),弧表示活动...分析关键路径的目的:辨别哪些是关键活动,以便争取提高关键活动的工效,缩短整个工期。 #include
  • 参考书籍:数据结构(C语言版)严蔚敏吴伟民编著清华大学出版社 ... 1.关键路径 对整个工程和系统,人们关心的是两个方面的问题: 1)工程能否顺利进行 对AOV进行拓扑排序 ... 对AOE网求关键路径 ...
  • C语言求AOE网关键路径

    2010-05-24 16:03:07
    这个程序为实现AOE求关键路径的程序,工具为VC,语言为C,内有readme,
  • Problem Description 一个无环的有向图称为无环图(Directed Acyclic Graph),简称DAG图。 AOE(Activity On Edge):顾名思义,用...关键路径:是从开始点到完成点的最长路径的长度。路径的长度是边上活动耗费的时间.
  • 【摘 要】介绍AOE网关键路径的相关概念,通过算法描述和实例,探讨基于拓扑排序求解、P矩阵的求解和广 度优先搜索遍历(BFS)方法三种算法,求解AOE网关键路径的实现过程,并进一步从算法的时间复杂度、数据结 构形式...
  • C语言AOE网关键路径

    千次阅读 2019-05-01 17:21:36
    2.关键路径 2.1关键路径的概念 2.2关键路径的几点说明 2.3关键路径的求解步骤 2.4关键路径求解示例 1.AOE网(Activity On Edge Network) 1.1AOE网的概念 若在带权的有向图中,用有向边表示活动(子工程),...
  • AOE网络的关键路径问题

    千次阅读 2017-06-04 12:01:31
    寻找AOE网络的关键路径目的是:发现该活动网络中能够缩短工程时长的活动,缩短这些活动的时长,就可以缩短整个工程的时长。因此,寻找关键路径就是寻找关键活动。接下来开始寻找一个工程中的关键路径(关键活动)。...
  • 0.概述 本文主要介绍以下两个方面...关键路径概念、特点,四种时间、求解方法 1.AOE网 2.关键路径 (1)概念 (2)四个时间 四个时间 —— 关键路径求解: (3)关键路径求解步骤 (4)特点 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,701
精华内容 1,080
关键字:

aoe网求关键路径