精华内容
下载资源
问答
  • 关键路径只有一条
    2021-11-23 21:00:29

    1.AOE网:在一个带权有向图中,用顶点代表事件,用有向边表示活动,边上的权值表示活动的持续时间

    (1)源点:整个工程的开始点,其入度为0

    (2)终点:整个工程的结束点,其出度为0

    (3)性质:

    • 只有进入某顶点的各活动都已经结束,该顶点所代表的事件才能发生
    • 只有在某顶点所代表的事件发生后,从该顶点出发的各活动才能开始

    (4)AOE网能够解决什么问题?

    • 完成整个工程至少需要多少时间
    • 为缩短完成工程所需的时间, 应当加快哪些活动? 

    (5)最短工期:从源点到终点的最大路径长度


    2.关键路径(不唯一):具有最大路径长度的路径,关键路径上的活动称为关键活动

    (1)求最短工期——>求关键路径——>求关键活动

       关键活动为什么关键?

    • 开始时间不能推迟
    • 最早开始时间和最晚开始时间相等

    (2)设带权有向图 G=(V,E)含有 n 个顶点 e 条边,设置 4 个一维数组:

    • 事件的最早发生时间 ve[n]
    • 事件的最迟发生时间 vl[n]
    • 活动的最早开始时间 ae[e]
    • 活动的最晚开始时间 al[e]

    (3)事件的最早发生时间 ve[n]

        ve[0] = 0

        ve[k] = max{ve[j] + len<vj, vk>} (<vj, vk>∈p[k])    

        p[k]:所有到达 vk 的有向边

        按拓扑顺序求,max(起点+权值)

    (4)事件的最迟发生时间 vl[n]

        vl[n-1] = ve[n-1]

        vl[k] = min{vl[j]-len<vk , vj>}(<vk, vj>∈s[k])

        s[k] :所有从 vk 发出的有向边

        逆拓扑序求,min(终点-权值)

    (5)活动的最早开始时间 ae[e]

        起点最早

    (6)活动的最晚开始时间 al[e]

        终点最迟-权值


    3.一些说法

    (1)若任意一个关键活动延期,则工期一定延长

    (2)若任意一个关键活动加快,则工期不一定加快

    (3)若任意一个非关键活动延期,则工期可能延长

    (4)若任意一个非关键活动延期,则工期不加快

    更多相关内容
  • 数据结构-关键路径

    千次阅读 2020-09-02 21:57:33
    (2)关键路径只有一条,关键活动也不是无限制缩短,工期会无限缩短的,因为可能缩到一定程度,这个节点就不是关键活动了。 求解关键路径的主要步骤: (1)求解ve(),求解每个节点(事件)的最早发生时间:规.

    AOV、AOE都是有权无向图,AOV边不带权值,AOE带权值。

    关键路径是AOE中,开始顶点到结束顶点的所有路径中,具有最大路径长度的路径成为关键路径,路径上的点是关键活动。

    (1)关键路径如果有多条,至提高一条关键路径上的关键活动并不能缩短工期,必须要加快所有关键路径上的关键活动才能加快工期。

    (2)关键路径只有一条,关键活动也不是无限制缩短,工期会无限缩短的,因为可能缩到一定程度,这个节点就不是关键活动了。

    求解关键路径的主要步骤:

    (1)求解ve(),求解每个节点(事件)的最早发生时间: 规定ve(0) = 0。 ve(n) = max(ve(n-1)+x1,ve(n-2)+x2) 能够到达n的所有路径中最大值。

    (2)求解vl(),求解每个节点(事件)的最迟发生时间:规定vl(终点)= ve(终点)。vl=min(vl(n-1)-x1,vl(n-2)-x2) 能够返回n的所有路径中的最小值。

    (3)求解e(),求解每个活动的最早开始时间。->活动a连接的两端的顶点的最早发生时间

    (4)求解l(),求解每个活动的最迟开始时间。->活动a连接的两端的终点的最迟发生时间-活动a历经的时间。

    (5)用e()-l(),找出等于0的点,等于0的路径就是关键路径。

    关键路径为:a2,a5,a7. v1->v3->v5->v6

                   

    20题。无需将所有步骤都完成,因为可以直接看出。最终选择C

                         

    21 ,求解ve(),vl() e() l () ,将e() - l () = 0 可以看出所有关键路径。因此有三条,最终选择C

                  

    展开全文
  • 关键路径--经典算法

    万次阅读 2017-11-28 21:36:10
    在建筑学中也称为关键路线。AOE网常用于估算工程完成时间。例如: 图1 图1 是个网。其中有9个事件v1,v2,…,v9;11项活动a1,a2,…,a11。每个事件表示在它之前的活动已经完成,在它之后的活动可以开始。如

    探寻


    AOE网

    用顶点表示事件,弧表示活动,弧上的权值表示活动持续的时间的有向图叫AOE(Activity On Edge Network)网。在建筑学中也称为关键路线。AOE网常用于估算工程完成时间。例如:
    图1 图1
    图1 是一个网。其中有9个事件v1,v2,…,v9;11项活动a1,a2,…,a11。每个事件表示在它之前的活动已经完成,在它之后的活动可以开始。如 v1表示整个工程开始,v9 表示整个工程结束。V5表示,活动a2和a3已经完成,活动a7和a8可以开始。与每个活动相联系的权表示完成该活动所需的时间。如活动a1需要6个时间单位可以完成、



    AOE网性质

    只有在某顶点所代表的事件发生后,从该顶点出发的各有向边所代表的活动才能开始。
    只有在进入某一顶点的各有向边所代表的活动都已经结束,该顶点所代表的事件才能发生。表示实际工程计划的AOE网应该是无环的,并且存在唯一的入度过为0的开始顶点和唯一的出度为0的完成顶点。


    关键路径

    图2 图2
    这时从开始顶点到达完成顶点的所有路径都是关键路径。
    一个AOE网的关键路径可以不止一条,如图7.24的AOE网中有二条关键路径,(v1,v2,v5,v7,v9 ) 和 (v1,v2,v5,v8,v9 )它们的路径长度都是24。
    如图2所示:

    研究的问题

    (1) 完成整个工程至少需要多少时间;
    (2) 哪些活动是影响工程的关键。
    1956年,美国 杜邦公司提出 关键路径法,并于1957年首先用于1000万美元化工厂建设,工期比原计划缩短了4个月。杜邦公司在采用关键路径法的一年中,节省了100万美元。

    关键路径术语

    (1) 关键路径:从源点到汇点的路径长度最长的路径叫关键路径;
    (2) 活动开始的最早时间e(i);
    (3) 活动开始的最晚时间l(i) 定义e(i)=l(i)的活动叫关键活动;
    (4) 事件开始的最早时间ve(i);
    (5) 事件开始的最晚时间vl(i)。
    设活动ai由弧<j,k>(即从顶点j到k)表示,其持续时间记为dut(<j,k>),则
    e(i)=ve(j)
    l(i)=vl(k)-dut(<j,k>)
    求ve(i)和vl(j)分两步:
    1、从ve(1)=0开始向前递推
    ve(j)=Max{ ve(i)+dut(<i,j>) }
    <i,j>T,2<=j<=n
    其中,T是所有以j为弧头的弧的集合。
    2、 从vl(n)=ve(n)开始向后递推
    vl(i)=Min{ vl(j)-dut(<i,j>) }
    <i,j>S,1<=i<=n-1
    其中,S是所有以i为弧尾的弧的集合。
    两个递推公式是在拓扑有序和逆拓扑有序的前提下进行。
    就如上面的图1:可有下表:



    求关键路径的算法
    (1) 输入e条弧<j,k>,建立AOE网的存储结构;
    (2) 从源点v1出发,令ve(1)=0,求 ve(j) 2<=j<=n;
    (3) 从汇点vn出发,令vl(n)=ve(n),求 vl(i) 1<=i<=n-1;
    (4) 根据各顶点的ve和vl值,求每条弧s(活动)的最早开始时间e(s)和最晚开始时间l(s),其中e(s)=l(s)的为关键活动。
    求关键路径是在 拓扑排序的前提下进行的,不能进行拓扑排序,自然也不能求关键路径。

    算法分析

    (1) 求关键路径必须在拓扑排序的前提下进行,有环图不能求关键路径;
    (2) 只有缩短关键活动的工期才有可能缩短工期;
    (3) 若一个关键活动不在所有的关键路径上,减少它并不能减少工期;
    (4) 只有在不改变关键路径的前提下,缩短关键活动才能缩短整个工期。
    测试数据:
    第一行表示顶点数和弧数;后面每一行就是权值,弧尾,弧头;

    6 8

    3 12

    2 13

    2 24

    3 25

    4 34

    3 36

    2 46

    1 56



    代码:可能在过程中需要知道拓扑排序,如果不知道的可以在我的另一篇文章中有介绍,此处的数据之间有点绕,可以好好的自己推一下,懂了之后就是很简单的算法;这里我使用的是C++的STL辅助,如果,有不懂的读者可以提前了解,其实,一起可以自己用C语言写一下啦,只是有点麻烦啦,什么队列栈呀的,都可以自己用数组模拟,知识在C++的STL中都有了,那还模拟啥呢,
    #include <iostream>
    #include <stack>
    #include <list>
    #include <vector>
    #include <algorithm>
    #define NUM 20
    using namespace std;
    
    struct Info{
        int num;
        int value;
        Info(){}
        Info(int x,int y):num(x),value(y){}//构造函数
    };
    int indree[NUM]={0};
    int N,M;//表示顶点数和边数;
    
    
    vector<list<Info> > Graph(NUM);
    stack<int> T;//用来储存拓扑排序的顶点,用来逆序输出;
    
    int Ve[NUM];
    int Vl[NUM];
    
    
        //拓扑排序求出事件 的最早发生时间Ve(j)和最迟发生时间Vl(j);
    
    bool tuopsort()
    {
        int count = 0;
        stack<int> q;
        memset(Ve, 0, sizeof(Ve));
        for(int i = 1;i<=N;i++)
            if(!indree[i])
                q.push(i);
    
        while(!q.empty()){
            int t = q.top();
            q.pop();
            count++;
            T.push(t);
            for(list<Info>::iterator it =  Graph[t].begin(); it!=Graph[t].end();it++){
                int k = it->num;
                if(!(--indree[k]))
                    q.push(k);
                Ve[k] = max(Ve[k],Ve[t]+it->value);//不断更新里面的最大值;
            }
        }
        if(count<N)
            return false;
        else
            return true;
    }
    
    
    
    bool CritPath()
    {
        if(!tuopsort()) return false;
        memset(Vl, 125, sizeof(Vl));
        Vl[N] = Ve[N];
    
    
        while(!T.empty()){
            int t = T.top();
            T.pop();
            for(list<Info>::iterator it =  Graph[t].begin(); it!=Graph[t].end();it++){
                int k = it->num;
                Vl[t] = min(Vl[t],Vl[k]-it->value);//也是不断的更新;
            }
        }
    //    for(int i = 1;i<=N;i++){
    //        cout <<Ve[i]<<"   "<<Vl[i]<<endl;
    //    }
    
    
    
        int ee,el;
        for(int i = 1;i<=N;i++){
            for(list<Info>::iterator it =  Graph[i].begin(); it!=Graph[i].end();it++){
                int k = it->num;
                ee= Ve[i];
                el = Vl[k]-it->value;
                int flag = (ee==el)?1:0;
                cout <<i<<"v->v"<<k<<" "<<it->value<<" "<<ee<<" "<<el<<" "<<flag<<endl;
            }
        }
        return true;
    }
    
    
    
    
    
    
    
    
    
    void print(Info f)
    {
        cout <<f.num<<"V-"<<f.value<<" ";
    
    }
    
    
    int main()
    {
    
        cin>>N>>M;
        for(int i=1;i<=M;i++){
            int v,f,e;
            cin>>v>>f>>e;
            if(f!=e)
                {Graph[f].push_front(Info(e,v));indree[e]++;}
        }
    
    //    cout <<"图的邻接表储存:"<<endl;
    //    for(int i= 1;i<=N;i++){
    //        cout <<i<<"   ";
    //        for_each(Graph[i].begin(),Graph[i].end() , print);
    //        cout <<endl;
    //    }
    
    //    cout <<"每一个顶点的入度:";
    //    for(int i = 1;i<=N;i++)
    //        cout <<indree[i]<<" ";
    //    cout <<endl;
        CritPath();
    
    
        return 0;
    }
    



    展开全文
  • 关键路径

    2020-03-31 10:33:55
    AOE网:在个表示工程的带权有向图中,用顶点表示事件(如V0),用有向边表示活动(如<v0,v1> = a1),边上的权值表示活动的持续时间,称这样的有向图为边表示的活动的网,简称AOE网(activity on edge ...

    AOE网示例图:

    AOE网:在一个表示工程的带权有向图中,用顶点表示事件(如V0),用有向边表示活动(如<v0,v1> = a1),边上的权值表示活动的持续时间,称这样的有向图为边表示的活动的网,简称AOE网(activity on edge network)

    源点:
    在AOE网中,没有入边的顶点称为源点;如顶点V0

    终点:
    在AOE网中,没有出边的顶点称为终点;如顶点V3

    AOE网的性质:
    【1】只有在进入某顶点的活动都已经结束,该顶点所代表的事件才发生;

             例如:a1和a2活动都结束了,顶点V2所代表的事件才会发生。

    【2】只有在某顶点所代表的事件发生后,从该顶点出发的各活动才开始;

             例如:只有顶点V1所代表的事件结束之后,活动a2和a4才会开始。

     
    在AOE网中,所有活动都完成才能到达终点,因此完成整个工程所必须花费的时间(即最短工期)应该为源点到终点的最大路径长度。具有最大路径长度的路径称为关键路径。关键路径上的活动称为关键活动:

     
    事件的最早发生时间:ve[k]
    根据AOE网的性质,只有进入Vk的所有活动<Vj, Vk>都结束,Vk代表的事件才能发生,而活动<Vj, Vk>的最早结束时间为ve[j]+len<Vj, Vk>。所以,计算Vk的最早发生时间的方法为:

    ve[0] = 0

    ve[k] = max(ve[j] + len<Vj, Vk>)

    事件的最迟发生时间:vl[k]
    vl[k]是指在不推迟整个工期的前提下,事件Vk允许的最迟发生时间。根据AOE网的性质,只有顶点Vk代表的事件发生,从Vk出发的活动<Vk, Vj>才能开始,而活动<Vk, Vj>的最晚开始时间为 vl[k]=vl[j] - len<Vk, Vj>。

    活动的最早发生时间:ee[i]
    ai由有向边<Vk, Vj>,根据AOE网的性质,只有顶点Vk代表的事件发生,活动ai才能开始,即活动ai的最早开始时间等于事件Vk的最早开始时间, ee[i] = ve[k]

    活动的最迟发生时间:el[i]
    el[i]是指在不推迟整个工期的前提下,活动ai必须开始的最晚时间。若活动ai由有向边<Vk, Vj>表示,则ai的最晚开始时间要保证事件vj的最迟发生时间不拖后,即 el[i]=vj最迟发生时间-ai

    案例:

    原始AOE网:

    事件的最早发生时间:ve[k]

    从源点向终点方向计算

    ve[0] = 0

    ve[1] = ve[0] + a0 = 0 + 4 = 4

    ve[2] = max( ve[0] + a1, ve[1] + a2 ) = max(0 + 3, 4 + 2 = 6

    ve[3] = max(ve[1] + a4, ve[2] + a3) = max(4 + 6, 3 + 4) = 10

    事件的最迟发生时间:vl[k]

    从终点向源点方向计算

    vl[3] = ve[3] = 10

    vl[2] = vl[3] - a3 = 10 - 4 = 6

    vl[1] = min(vl[3] - a4, vl[2] - a2) = min(10-6, 6-2) = 4

    vl[0] = min(vl[2] - a1, vl[1] - a0) = min(4-4, 4-2) = 0 

    活动的最早发生时间:ee[i]

    共有五个活动:

    ee[0] = ve[0] = 0

    ee[1] = ve[0] = 0

    ee[2] = ve[1] = 4

    ee[3] = ve[2] = 6

    ee[4] = ve[1] = 4

    活动的最迟发生时间:el[i]

    el[0] = v[1] - a0 = 4 - 4 = 0

    el[1] = vl[2] - a1 = 6 - 3 = 3

    el[2] = vl[2] - a2 = 6 - 2 = 4

    el[3] = vl[3] - a3 = 10 - 4 = 6

    el[4] = vl[3] - a4 = 10 - 6 = 4

     

    活动的最早开始时间和最晚开始时间相等,则说明该活动时属于关键路径上的活动,即关键活动。

    经过比较,得出关键活动有:a0, a2, a3, a4,画出示意图如下:

    该AOE网有两条关键路径。

    所以,通过此案例也可以发现,一个AOE网的关键路径可能有多条。
     

    展开全文
  • 关键路径问题讲解,解决最早开始时间,最晚开始时间的问题。
  • 关键路径)AOE网 在带权有向图中,以顶点表示事件,以有向边表示活动,以边上的权值表示完成该活动的开销(如完成活动所需的时间),称之为⽤边表示活动的网络,简称AOE网 (Activity On Edge NetWork) 在...
  • 【算法专题】关键路径及代码实现

    千次阅读 2021-09-07 11:16:30
    关键路径 . 问题描述 概念 项工程计划可以被看成个有向图,图中的顶点表示事件,边代表活动,边上的权值代表完成这项活动需要的...我们只有减少关键路径上活动用时才能加快工程的进度。 我们的问题就是输
  • 关键路径详解

    千次阅读 2019-11-22 15:46:36
    关键路径算法是种典型的动态规划法,设图 G=(V, E) 是个 AOE 网,结点编号为 1,2,...,n ,其中结点 1 与 n 分别为始点和终点, ak=, j> ∈ E 是 G 的个活动。算法关键是确定活动的 最早发生时间v e[k] 和 最晚...
  • 关键路径的权值和,并且从源点输出关键路径上的路径(如果有多,请输出字典序最小的) 输入样例 9 11 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 8 9 4 7 9 2 输出样例 18 1 2 2 5 5 7 7 9
  • 图——关键路径

    万次阅读 多人点赞 2019-04-02 09:10:27
    AOE网:在个表示工程的带权有向图中,用顶点表示事件(如V0),用有向边表示活动(如<v0,v1> = a1),边上的权值表示活动的持续时间,称这样的有向图为边表示的活动的网,简称AOE网(activity on edge ...
  • 关键路径计算

    万次阅读 多人点赞 2017-09-03 13:58:48
    计算关键路径,只需求出上面的四个特征属性,然后取e(i)=l(i)的边即为关键路径上的边(关键路径可能不止一条)。  先来看看四个特征属性的含义:  Ø  Ve(j):是指从始点开始到顶点Vk的最大路径长度 ...
  • 如何求关键活动以及存在多条关键路径的输出(数据结构C语言版) ** 1.问题描述 关键路径: 通常把计划、施工过程、生产流程、程序流程等都当成个工程。工程通常分为若干个称为“活动”的子工程。完成了这些...
  • 关键路径实践报告

    2014-01-03 22:54:56
    在AOE网络中,从源点到汇点的有向路径可能不止一条,但只有各条路径上所有活动都完成了,这个工程才算完成。因此,完成整个工程所需的时间取决于从源点到汇点的最长路径长度,即在这条路径上所有活动的持续时间之和...
  • 关键路径习题.ppt

    2020-12-21 09:49:58
    山东绿邦网络技术集成有限公司 地址:山东省济南市文化西路13号 邮编:250014 电话:0531传真:0531网址: 山东绿邦 关键路径法(Critical Path ethod,CPM) 关键路线法是种网络图方法,由雷明顿-兰德公司(Remington...
  • 拓扑排序以及求解关键路径

    千次阅读 2019-10-29 17:14:33
    拓扑排序以及求解关键路径都是属于有向无环网的应用 拓扑排序:解决工程能否顺序进行的问题 介绍2个概念 AOV网:在个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示...
  • 图的关键路径

    2020-05-17 09:52:44
    图的关键路径思想 AOE网是指在有向网中,如果用顶点表示事件,用有向边表示活动,边上的权值表示活动持续的时间,则称这样的有向网为弧表示活动的网(Acticity On Edge,AOE-网)。对仅有个开始点和个完成点的...
  • 图解:什么是关键路径

    万次阅读 多人点赞 2020-05-06 20:31:39
    小禹禹,五一假期马上结束了,你们过得怎么样呢?有没有玩得很开心,收获满满呢?好想听你们在评论区说说。哈哈,不过我们还是先来说说今日景禹要给你们分享的内容,关键路径。何为关键路径?如果...
  • 文章目录数据结构C++——关键路径一、前言二、关键路径的概念三、关键路径的实现①关键路径的实现原理②关键路径的代码实现③测试的全部代码四、总结 、前言 理解关键路径需要掌握拓扑排序和邻接表的相关知识,...
  • 给出个图,首先判断是否为有向无环图,如果是,则输出要求的边的最早发生时间和最晚发生时间,然后输出所有关键路径。 判断是否为有向无环图,可以用拓扑排序来判断。 二、分析 首先分析拓扑排序。使用邻接矩阵...
  • 超详细讲解实现拓扑排序、关键路径

    千次阅读 多人点赞 2022-03-26 11:07:49
    今天,小编带着大家来学习图中非常重要的环,拓扑排序和关键路径! 首先,我们需要知道的是,拓扑排序是关键路径的基础,正因如此,当我们知道了关键路径在生活中的应用,相信大家也就明白这两个算法的重要性了!...
  • 数据结构之——关键路径

    千次阅读 2020-06-06 23:07:57
    1.AOE网 边活动(Activity On Edge, AOE)网是指用带权的边集表示活动,用顶点表示事件的有向图,而用边权表示活动完成需要的时间。 如下图所示,边a1 -a6表示需要学习的课程...(2)只有在进入某顶点的各有向边所代
  • 7这红色的路径就是关键路径关键路径的特征是:从起点 (起点是唯一的,入度为0) 到终点 (终点是唯一的,出度为0) 的个有向图中,该路径上的弧 (有向图的边称之为“弧”) 的权重的和最大。关键路径可能不是唯一...
  • 图的应用——关键路径

    千次阅读 2020-01-14 18:41:58
    AOE网、关键路径
  • 简单理解关键路径

    千次阅读 多人点赞 2020-03-03 20:40:09
    关键路径问题的相关概念 通常,个项目可以被拆分成多个子项目,多个子项目间会具有并行和串行的特点。 例如造汽车时,造发动机和造车轮是两个可以并行完成的任务,而组装整车又必须等发动机和车轮等部件完成后...
  • 关键路径法详解【CPM】

    万次阅读 2018-09-01 22:26:33
    CPM(CriticalPathMethod 关键路径法)是项目管理中最基本也是非常关键的个概念,它上连着WBS(工作分解结构),下连着执行进度控制与监督。关键路径是项目计划中最长的路线。 它决定了项目的总实耗时间。项目经理...
  • 【数据结构】AOE网——关键路径

    千次阅读 2021-05-16 10:01:48
    在AOE网中,从源点到汇点最长的路径称为关键路径,在关键路径上的活动称为关键活动。 因为AOE网中的活动是可以并行进行的,所以整个工程的时间开销,其实是最长路径的时间开销。即关键路径制约整个工程的工期。 &...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 168,949
精华内容 67,579
关键字:

关键路径只有一条

友情链接: aspgongqiufabu.zip