精华内容
下载资源
问答
  • AOE网络

    2017-12-25 09:55:09
    AOE网络(Activity On Edges)

    AOE网络(Activity On Edges)

    定义:在无有向环的带权有向图中,满足以下条件:

    1.用有向边表示一个工程的各项活动

    2.用边上的权值代表活动的持续时间

    3.用顶点代表事件

    这样的有向图叫做用边表示活动的网络,简称AOE网络


    相关概念:

    源点:入度为零的点

    汇点:出度为零的点

    关键路径:从源点到汇点长度最长的路径

    关键活动:关键路径上的所有活动都是关键活动


    相关的量:

    事件vi的最早可能开始时间ve[i]:从源点v0到顶点vi的最长路径长度

    事件vi的最迟允许开始时间vl[i]:在保证汇点在最早可能时间完成的情况下,事件vi的允许的最迟开始时间

    活动ak的最早可能开始时间e[k]:

    活动ak的最迟允许开始时间l[k]:

    时间余量:




    展开全文
  • AOE 网络

    2019-09-28 03:46:43
    则这样的有向图叫做用边表示活动的网络,简称AOE网络 AOE在工程方面非常有用: 例如: (1)完成整个工程至少需要多少时间(假设没有环); (2)为缩短完成工程所需时间,应当加快那些活动? 从源点到各个...

    1、定义

    如果在无向环的带权有向图中

       - 用有向边表示一个工程中的活动

       - 用边上的权值表示活动的持续时间

       - 用顶点表示事件

    则这样的有向图叫做用边表示活动的网络,简称AOE网络

    AOE在工程方面非常有用:

    例如:

    (1)完成整个工程至少需要多少时间(假设没有环);

    (2)为缩短完成工程所需时间,应当加快那些活动?

    从源点到各个顶点,以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同,完成不同路径的活动所需时间不同,但只有各条路径上所有活动都完成了,整个工程才完成。

    Hence, 完成整个工程所需时间取决于从源点到汇点的最长路径长度,即在该路径上所有活动的持续时间之和,给路径称为关键路径

     

    为了找出关键路径,必须找出关键活动,即不按期完成就会影响整个工程完成的活动。

    关键路径上的所有活动都是关键活动。

     

     

     

    修改后的拓扑排序:

    void TopologicalSort(AdjGraph G)
    {
    	Stack S;
    	StackEmpty(S);
    	int j;
    
    	for(int i=0;i<n;i++) //入度为0的顶点进栈
    		if(count[i]==0)
    			Push(S,i);
    
    	while(!StackEmpty(S))
    	{
    		Pop(S,j); //退栈
    		cout << j << endl;  //输出栈顶元素
    		Push(T,j); //j号顶点入栈
    		EdgeNode * p=data[j].firstarc;
    		while(p!=NULL)     //扫描出边表
    		{
               int k=p->adjvex;  //另一顶点
               if(--count[k]==0) //顶点入度减一
               	  Psuh(S,k);  //顶点入度减至0,进栈
                if(ve[j]+p->info>ve[k])ve[k]=ve[j]+p->info;
                p=p->nextarc;
    		}
    	}
    }
    
    CristicalPath(G)
    {
    	vl[0..vexnum-1]=ve[vexnum-1];
    	while(!StackEmpty(T))
    	{
    		Pop(T,j);
    		p=G.data[j].firstarc;
    		while(p!=NULL)
    		{
    			k=p->adjvex;
    			dut=p->info;
    			if(vl[k]-dut<vl[j]) vl[j]=vl[k]-dut;
    		}
    		for(j=0;j<vexnum;j++)
    			for(p=G.data[j].firstarc;p;p=p->next)
    			{
    				k=p->adjvex;
    				dut=p->info;
    				ee=ve[j];
    				el=vl[k]-dut;
    				if(ee=el)printf("j,k");
    			}
    	}
    }
    

      

     算法分析:

    在拓扑排序求Ve[i],与逆拓扑排序求Vl[i]时需要的时间复杂度为O(n+e),求各个活动e(k)与l(k)需要的时间复杂度为O(e),

    则总的时间复杂度为O(n+e)

     

    注意到并不是改变任何一个关键活动的时间都可以改变总时间

    转载于:https://www.cnblogs.com/KennyRom/p/6135849.html

    展开全文
  • 活动网络——AOE网络

    2017-02-16 17:42:45
    AOE网络 关键路径

    AOE网络:如果在有向无环图中用有向边表示一个工程中的各项活动,用有向边上的权值表示活动的持续时间,用顶点表示事件,则这种有向图叫做用边表示活动的网络,简称AOE网络。

    AOE网络的用途

    (1)完成整个工程至少需要多长时间

     (2)为缩短工程所需的时间,应加快哪些活动


    关键路径:完成整个工程所需的时间取决于从源点到汇点的最长路径长度,这条路径最长的路径就称为关键路径。(Critical Path);

    常用的量:(1)事件Ei的最早可能开始时间,记为Ee[i].是从源点到顶点Ei的最长路径长度

                       (2)事件Ei的最迟可能开始时间,记为El[i].El[i]是在保证汇点En-1在Ee[n-1]时刻完成的前提下,事件Ei允许开始的最迟时间,它等于Ee[n-1]减去从Ei到En-1的最长路径长度。

                        (3)活动ak的最早可能开始时间,记为e[k]。设活动在有向边<Ei,Ej>上,e[k]=Ee[i].

                         (4)活动ak最迟允许开始的时间,记为l[l].   l[k]=El[j]-dur<Ei,Ej>的值。

    松弛时间:l[k]-e[k]

    求Ee[i]的递推公式,从Ee[0]=0开始,向前递推:

    Ee[i]=max{Ee[j]+dur(<Ej,Ei>)}.

    求El[i]的递推公式。从El[n-1]=Ee[n-1]开始,反向递推

    El[i]=min{  El[j]-dur(<Ei,Ej>)  }.

    这两个递推公式必须在拓扑有序及逆拓扑有序的前提下进行。所谓逆拓扑有序,就是首先输出出度为0的顶点,以相反的次序输出拓扑排序序列,这种排序称为逆拓扑排序。

    也就是说,在计算Ee[i]时,Ei的所有前驱顶点Ej的Ee[j]都已经求出。反之,在计算El[i]时,Ei的所有后继顶点El[j]都已经求出

    例题:求如图所示的AOE网络的关键路径并输出。首先输入顶点个数n和边个数m,然后依次输入每条边



    #include<cstdio>
    #include<iostream>
    #include<cstring>
    using namespace std;
    #define MAXN 100///顶点数目的最大值
    #define MAXM 200///边的数目的最大值
    struct ArcNode
    {
        int to,dur,no;///no为活动序号
        ArcNode *next;
    };
    int n,m;
    ArcNode *list1[MAXN];///出边表的表头指针
    ArcNode *list2[MAXN];///入边表的表头指针
    int count1[MAXN];///各顶点的入度
    int count2[MAXN];///各顶点的出度
    int Ee[MAXN];///各事件最早可能开始的时间
    int El[MAXN];///各事件允许开始的最迟时间
    int e[MAXM];///各活动最早可能开始的时间
    int l[MAXM];///各活动允许最晚可以开始的时间
    void CriticalPath();
    int main()
    {
        int i,j;
        int u,v,w;
         while(scanf("%d%d",&n,&m)!=EOF)///顶点数和边数
        {
            if(n==0&&m==0) break;
           memset(list1,0,sizeof(list1));
           memset(list2,0,sizeof(list2));
           memset(count1,0,sizeof(count1));
           memset(count2,0,sizeof(count2));
           ArcNode *temp1,*temp2;
           for(i=0;i<m;i++)
           {
               scanf("%d%d%d",&u,&v,&w);
               count1[v]++;
               temp1=new ArcNode;///构造邻接表
               temp1->to=v;
               temp1->dur=w;
               temp1->no=i+1;
               temp1->next=NULL;
               if(list1[u]==NULL)
                list1[u]=temp1;
               else
               {
                   temp1->next=list1[u];
                   list1[u]=temp1;
               }
               count2[u]++;
               temp2=new ArcNode;///构造逆邻接表
               temp2->to=u;
               temp2->dur=w;
               temp2->no=i+1;
               temp2->next=NULL;
               if(list2[v]==NULL)
                list2[v]=temp2;
               else
               {
                   temp2->next=list2[v];
                   list2[v]=temp2;
               }
           }
           CriticalPath();
           ///释放边链表上各边结点所占用的空间
           for(i=0;i<n;i++)
           {
               temp1=list1[i];
               temp2=list2[i];
               while(temp1!=NULL)
               {
                   list1[i]=temp1->next;
                   delete temp1;
                   temp1=list1[i];
               }
               while(temp2!=NULL)
               {
                   list2[i]=temp2->next;
                   delete temp2;
                   temp2=list2[i];
               }
           }
    
        }
        return 0;
    }
    void CriticalPath()
    {
        ///拓扑排序求Ee;
         int i,j,k;
         int top1=-1;
         ArcNode *temp1;
         memset(Ee,0,sizeof(Ee));
         for(i=0;i<n;i++)///找出入度为0的点
         {
             if(count1[i]==0)
             {
                 count1[i]=top1;
                 top1=i;
             }
         }
         for(i=0;i<n;i++)
         {
             if(top1==-1)
             {
                 printf("Network has a cycle\n");
                 return ;
             }
             else
                {
                   j=top1;
                  top1=count1[top1];
                  temp1=list1[j];
               while(temp1!=NULL)
               {
                   k=temp1->to;
                   count1[k]--;
                   if(count1[k]==0)
                   {
                       count1[k]=top1;
                       top1=k;
                   }
                   if(Ee[j]+temp1->dur>Ee[k])
                    Ee[k]=Ee[j]+temp1->dur;
                   temp1=temp1->next;
               }
            }
         }
         ///逆拓扑排序求El;
         int top2=-1;
         ArcNode *temp2;
         for(i=0;i<n;i++)///找出出度为0的顶点
         {
             El[i]=Ee[n-1];///初始化为已知的最大值
             if(count2[i]==0)
             {
                 count2[i]=top2;
                 top2=i;
             }
         }
         for(i=0;i<n;i++)
         {
             j=top2;
             top2=count2[top2];
             temp2=list2[j];
             while(temp2!=NULL)
             {
                 k=temp2->to;
                 count2[k]--;
                 if(count2[k]==0)
                 {
                     count2[k]=top2;
                     top2=k;
                 }
                 if(El[j]-temp2->dur<El[k])
                    El[k]=El[j]-temp2->dur;
                 temp2=temp2->next;
             }
         }
          ///输出Ee[i]和El[i]
         for(i=0;i<n;i++)
            cout<<Ee[i]<<" ";
         cout<<endl;
         for(i=0;i<n;i++)
            cout<<El[i]<<" ";
            cout<<endl;
         ///求各种活动的e[k]和l[k];
         memset(e,0,sizeof(e));
         memset(l,0,sizeof(l));
         printf("the critical activities:\n");
         for(i=0;i<n;i++)
         {
             temp1=list1[i];
             while(temp1!=NULL)
             {
                 j=temp1->to;///有向边<i,j>;
                 k=temp1->no;
                 e[k]=Ee[i];
                 l[k]=El[j]-temp1->dur;
                  if(e[k]==l[k])
                    {
                         printf("a%d : %d->%d\n",k,i,j);
                    }
                 temp1=temp1->next;
             }
         }
         ///输出e[i]和l[i]的值
          for(i=0;i<m;i++)
            cout<<e[i]<<" ";///为啥前四个都为0??因为是最早可能开始的时间
         cout<<endl;
         for(i=0;i<m;i++)
            cout<<l[i]<<" ";
         cout<<endl;
    }
    
    测试数据:


    TMD书上的测试数据竟然给错,还好有超哥相助,多谢超哥


    展开全文
  • AOV网络和AOE网络

    千次阅读 2018-12-02 22:41:29
    AOV和AOE网络是什么 活动网络可以用来描述生产计划、施工过程、生产流程、程序流程等工程中各子工程的安排问题。活动网络可分为两种:AOV网络和AOE网络 AOV网络(Activity On Vertices):在有向图中,用顶点表示...

    AOV和AOE网络是什么

    活动网络可以用来描述生产计划、施工过程、生产流程、程序流程等工程中各子工程的安排问题。活动网络可分为两种:AOV网络和AOE网络

    AOV网络(Activity On Vertices):在有向图中,用顶点表示活动,用有向边u->v来表示活动u必须先于活动v进行

    AOE网络(Activity on edge network):若在带权的有向图中,以顶点表示阶段,以有向边u->v表示活动活动u必须先于活动v进行,边上的权值表示活动的开销(如该活动持续的时间)

     针对AOV网络的拓扑排序算法

    为AOV网络进行管理:决定每个结点的先后顺序(不一定是唯一的),也就决定了活动的先后顺序

    拓扑排序(Topological Sort)见:算法导论第22章:基本的图算法

    针对AOE网络的关键路径算法 

    关键路径(Critical Path):从源点到汇点具有最大长度的路径。这条路径决定了整个项目的最早完成时间,要想优化整个项目的时间,则必须在关键路径上下手。

    最早完成时间:项目到达某个阶段至少需要的时间,即源点到相应顶点的最长路径。

    最迟完成时间:项目最迟完成的时间,超过此时间表示项目产生了停滞。

    **算法思想:拓扑序DP**

    算法描述

    从源点开始,更新其所有邻接结点的最早完成时间,直到汇点(项目的终止点)

    按拓扑逆序DP,获得所有结点的最迟完成时间

    若最早完成时间 == 最迟完成时间,则证明其为关键路径上的结点

    参考资料

    算法学习记录-图——应用之关键路径(Critical Path)

    AOV网络与拓扑(一)

    展开全文
  • AOE网络-关键路径

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

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

    2011-02-17 09:29:46
    数据结构课程设计,aoe网络计算,带图形界面
  • 本资源为同济大学数据结构课程设计题之AOE网络的图形化实现,内含VS2012工程、可执行程序及设计说明文档。
  • 由于低频浮动车数据时间间隔较长,现有地图匹配方法难以满足低频浮动车数据地图匹配的...第三,设计了一种改进AOE网络,提出了基于改进AOE网络的最短可达路径算法,以获取最终的地图匹配点;最后,对改进AOE网络的地图匹配
  • //求AOE网络中的关键路径算法 #include <cstdio> #include <cstring> #define MAXN 100 //顶点个数的最大值 #define MAXM 200 //边数的最大值 struct ArcNode { int to, dur, no; //边的另一个顶点持续时间活动序号 ...
  • AOV网络与AOE网络

    千次阅读 多人点赞 2018-06-05 20:43:07
    一、AOV网络与拓扑排序   AOV网(Activity On Vertex NetWork)用顶点表示活动,边表示活动(顶点)发生的先后关系。   若网中所有活动均可以排出先后顺序(任两个活动之间均确定先后顺序),则称网是拓扑...
  • AOE网络的关键路径问题

    千次阅读 2017-06-04 12:01:31
    关于AOE网络的基本概念可以参考《数据结构》或者search一下就能找到,这里不做赘述。寻找AOE网络的关键路径目的是:发现该活动网络中能够缩短工程时长的活动,缩短这些活动的时长,就可以缩短整个工程的时长。因此,...
  • 有良好界面的JAVA编写的AOE网络求取关键路径,比较完善
  • 数据结构 图-关键路径:AOE网络

    千次阅读 2020-07-25 22:10:08
    在带权有向图中,以顶点表示事件,有向边表示活动,边上的权值表示完成该活动的开销(如完成活动所需的时间),即用边表示活动的网络称为AOE网络。 注: AOE网络一定是有向无环图。 关键活动 假设:a+d+f > b+e ...
  • AOE网络与关键路径(一)

    千次阅读 多人点赞 2014-04-07 00:24:12
    1、与AOV网络密切相关的是AOE网络。如果在DAG中用有向边表示一个工程的各项活动,用有向边上的权值表示活动的持续时间,用顶点表示事件,则这种有向图叫做用边表示活动的网络(Activity On Edge),简称AOE网络; ...
  • C++ AOE网络

    2019-04-03 22:19:52
    一、思路(你可以用拓扑排序来做,但我这里没用拓扑排序) (1)求事件Vi的最早可能开始时间是从源点V0到顶点Vi的最长路径长度。 如V0=0, V1=6,V2=4,V3=5;V4事件要等V1和V2事件完成后才可以进行,所以要取事件用的...
  • 说明: AOE 网络是有向无环加权图,其中顶点表示事件,弧表示活动,权表示活动持续的时间,通常可以用来估算工程完成的时间,即图中从开始点到结束点之间最长的路径对应的时间。请完成一个程序,完成下列任务: 1 ...
  • 关于aoe网络的课程设计,java做的 能用,希望对大家有帮助
  • 找代码废了很大的时间,有些代码存在问题,...#裘宗燕数据结构中的aoe网络代码"""topological sort of direct graph """class Graph: #basic graph class, using adjacent matrix ...
  • AOE网络与关键路径(二)——实现

    千次阅读 2014-04-07 11:43:50
    这一篇来实现下AOE网络和关键路径~
  • AOV与AOE网络

    2019-12-01 21:56:03
    二、关键排序(AOE) 一、拓扑排序(AOV) 1. AOV的概念: 在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,称这样的有向图为顶点表示活动的网,简称AOV网 2.拓扑排序:按照有向图给出...
  • Python递归解决AOE网络最长路关键路径的问题 一鼓作气,再来一发 这是某同学在某公式宣讲会中笔试部分的一题,如下图: 如图:每一个项目都有完成时间和若干个前置条件,求总项目(或每一个项目)的最短完成时间。...

空空如也

空空如也

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

aoe网络