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

    千次阅读 2017-05-13 16:15:31
    AOE网对工程管理问题的表示: 在向图中,如果顶点表示事件,向边表示活动,向边上的权值表示活动持续时间,这样的向图...(2)AOV网的入度为0的顶点可以有多个,而AOE网入度为0的顶点只有一个; (3)AOV网的

    AOE网对工程管理问题的表示:

    在有向图中,如果顶点表示事件,有向边表示活动,有向边上的权值表示活动持续时间,这样的有向图称“边表示活动的网”即AOE网。如下图AOE网中,有10个事件,15个活动。


    AOE网对比AOV网:

    (1)AOV网的有向边不考虑权值,而AOE网的有向边考虑权值;

    (2)AOV网的入度为0的顶点可以有多个,而AOE网入度为0的顶点只有一个;

    (3)AOV网的出度为0的顶点可以有多个,而AOE网出度为0的顶点只有一个;

    (4)AOV与AOE网都不允许出现环路。

    AOE网具有如下性质:

    (1)只有在进入某一顶点的各条有向边代表的活动结束后,该顶点所代表的事件才能发生;

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

    (3)在一个AOE网中,有一个入度为0的事件,称源点,它表示整个工程的开始。同时,有一个出度为0的事件,称汇点,它表示整个工程的结束。

    AOE网的研究目标:

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

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

    基本概念:

    路径长度:AOE网的一条路径上所有活动的总和称为该路径的长度。

    关键路径:在AOE网中,从源点到汇点的所有路径中,具有最大路径长度的路径称为关键路径。

    关键活动:关键路径上的活动称为关键活动。

    显然,完成整个工程的最短时间就是AOE网中关键路径的长度。

    必要说明:为什么最短时间是最大路径长度?

    拿上图说明,以事件v0为起点,0时开始(以秒为单位)。当时间过去5秒活动a1结束,事件v1发生,而此时,活动a2还差两秒才结束;再过3秒活动a3结束,但此时事件v3还不能发生,因为活动a4刚进行1秒还没有结束,必须再等5秒a4结束,事件v3才能发生。

    所以,可以得出某一事件的发生,最早也要等前面的所有活动中最消耗时间(即路径最长)的那个活动完成。

    当一个工程计划用AOE网表示后,所关心的问题就是如何找出关键路径上的关键活动,从而增加关键活动的投入,缩短关键活动持续时间,进而争取整个工程的提前完成。

    参数定义(假设有n个结点),并对上图AOE网进行计算:


    活动持续时间dut(<j,k>):代表有向边(活动)<j,k>的权值。

    事件可能的最早开始时间ve(k):对于顶点vk代表的事件,ve(k)是从源点到该顶点的最大路径长度。递推公式:ve(0)=0;ve(k)=Max{ve(j)+dut(<j,k>)},由公式,我们从源点v0正向计算。

    事件允许的最晚发生时间vl(k):对于顶点vk代表的事件,vl(k)是在保证按时完成整个工程的前提下,该事件最晚必须发生的时间。递推公式:vl(n)=ve(n);vl(k)=Min{vl(j)-dut(<k,j>)},由公式,我们从汇点v9反向计算。

    活动可能的最早开始时间e(i):对于有向边ai代表的活动,e(i)是该活动的狐尾事件可能的最早发生时间。

    活动允许的最晚开始时间l(i):对于有向边ai代表的活动,l(i)是该活动的弧头事件允许的最晚发生时间减去该活动持续的时间。

    每个活动允许的时间余量就是l(i)-e(i),而关键活动l(i)-e(i)=0,即可能的最早开始时间等于允许的最晚开始时间。

    对于上面的AOE网图,把求解的各参数陈述于下表中:

    事件v0v1v2v3v4v5v6v7v8v9
    ve(k)05713171823222631
    vl(k)010713172023222831
    活动a1a2a3a4a5a6a7a8a9a10a11a12a13a14a15
    e(i)0057713131317171823232226
    l(i)501071413151917172026232228
    由表1,整个工程需要的最少时间为ve(v9)=31。

    由表2,根据条件l(i)-e(i)=0,得到关键活动有a2,a4,a6,a9,a10,a13,a14;从源点v0到汇点v9的只要经过关键活动的路径就是关键路径,所以该图的关键路径为(v0,v2,v3,v4,v6,v9)和(v0,v2,v3,v4,v7,v9)。

    寻找关键活动的算法:

    (1)建立包含n+1个顶点(这样是为了方便n直接代表下标)、e条有向边的AOE网。其中,顶点v0为源点,顶点vn为汇点。

    (2)根据有向图的拓扑排序算法,求出AOE网的拓扑序列。如果存在环,拓扑序列不存在,则无法得到关键活动,算法失败退出。

    (3)从源点v0开始,令源点v0的最早开始时间为ve[0]=0,按拓扑序列求其余各顶点k(k=1,2,···,n)的最早开始时间ve[k]。

    (4)从汇点vn开始,令汇点vn的最晚发生时间vl[n]=ve[n],按逆拓扑序列求其余各顶点k(k=n-1,n-2,···,0)的最晚发生时间vl[k]。

    (5)计算每个活动的最早开始时间e[k]。

    (6)计算每个活动的最晚开始时间l[k]。

    (7)找出所有e[k]=l[k]的活动k,这些活动即为AOE网的关键活动。


    展开全文
  • 关键路径的计算

    万次阅读 多人点赞 2014-06-21 09:46:46
    从源点到汇点路径长度最长的路径为该工程的关键路径,即关键路径可以保证所有路径的活动都能够完成。 ok,再次进入我们的作业题: 如下图所示的AOE网(弧上权值代表活动的持续天数) 1)完成此工程最少所需要...

              从源点到汇点路径长度最长的路径为该工程的关键路径,即关键路径可以保证所有路径的活动都能够完成。

          ok,再次进入我们的作业题:

          如下图所示的AOE网(弧上权值代表活动的持续天数)

               1)完成此工程最少所需要多少天?
               2)哪些是关键活动,在图中表示出关键路径

            

         我们先计算最早发生时间ve和最迟发生时间vl:

     

     12345678910
    Ve05612151616192123
    Vl09612152116192123


         首先呢,编号1和编号10分别为该工程的源点和汇点,我们规定最早发生时间ve(源点)=0,最迟发生时间vl(汇点)=ve(汇点)。那么这两个量该如何计算呢,看图:


         对于事件i来说,ve(i) = Max{ve(m) + dut(<m, i>)},vl(i) = Min{vl(j) – dut(<i, j>)};其中ve(m)代表i前一个事件的最早发生时间,dut(<m, i>)表示从m到i的持续时间,大家可以把它看成一个递归算法,一直调用ve(),直到ve(源点)为止,然后取其最大值,因为它要保证所有路径上的活动都能完成;而最迟发生时间和前者一样,一直递归调用vl(),直到vl(汇点)为止,然后取其最小值即可。

        回到原题中对照例图可以很快地得到表格所示内容。

        我们再来看两个概念:e(i)和l(i),前者为活动ai 的最早可能开始时间,后者为活动ai的最迟允许开始时间。区别于前边的ve和vl,e和l为标识的是某活动的时间,而前者是某事件的时间。

        假如从事件m到事件i的活动为af,则有e(f)=ve(m), l(f)=vl(i)–dut(<m,i>) ,即活动af的最早可能开始时间为其弧尾事件最早可能发生时间;最迟允许开始时间为其弧尾事件最迟发生时间与两个事件的持续时间之差。是不是感觉有点别扭,但只要理解了这几个关键词也就很容易看懂了。于是乎 e(k) = l(k)的活动就是关键活动 ,请看图表:

     

     a1a2a3a4a5a6a7a8a9a10a11a12a13
    5636334145242
    e005661212151516191621
    l4096121217151516192121


         由图和前边计算的ve和vl可以得到各活动的e和l,如上表所示,则关键活动为a2,a4,a6,a8,a9,a10,a11和a13,所以完成该工程至少需要的天数d=6+6+3+1(4)+5(2)+2=23,该工程的关键路径有两条,即1->3->4->5->7->9->10和1->3->4->5->8->9->10。

    更新:6号节点的最迟发生时间vl应该是19 而不是21。。。

     

    展开全文
  • 关键路径算法

    千次阅读 2016-04-06 18:09:12
    关键路径的算法是建立在拓扑排序的基础之上的,这个算法中用到了拓扑排序,所以在这里先以拓扑排序开篇。 1. 什么是拓扑排序? 举个例子先:一个软件专业的学生学习一系列的课程,其中一些课程必须再学完它的基础...

    1,(部分转载)

    关键路径的算法是建立在拓扑排序的基础之上的,这个算法中用到了拓扑排序,所以在这里先以拓扑排序开篇。

    1. 什么是拓扑排序?
    举个例子先:一个软件专业的学生学习一系列的课程,其中一些课程必须再学完它的基础的先修课程才能开始。如:在《程序设计基础》和《离散数学》学完之前就不能开始学习《数据结构》。这些先决条件定义了课程之间的领先(优先)关系。这个关系可以用有向图更清楚地表示。图中顶点表示课程,有向边表示先决条件。若课程i是课程j的先决条件,则图中有弧<i,j>。若要对这个图中的顶点所表示的课程进行拓扑排序的话,那么排序后得到的序列,必须是按照先后关系进行排序,具有领先关系的课程必然排在以它为基础的课程之前,若上例中的《程序设计基础》和《离散数学》必须排在《数据结构》之前。进行了拓扑排序之后的序列,称之为拓扑序列。
    2. 如何实现拓扑排序?
    很简单,两个步骤:
    1. 在有向图中选一个没有前驱的顶点且输出。
    2. 从图中删除该顶点和以它为尾的弧。
    重复上述两步,直至全部顶点均已输出,或者当前图中不存在无前驱的顶点为止。后一种情况则说明有向图中存在环。
    3. 什么是关键路径?
    例子开头仍然,图1是一个假想的有11项活动的A0E-网。其中有9个事件v1,v2......,v9,每个事件表示在它之前的活动一完成,在它之后的活动可以开始。如v1表示整个工程的开始,v9表示整个工程结束,v5表示a4和a5已完成,a7和a8可以开始。与每个活动相联系的数是执行该活动所需的时间。比如,活动a1需要6天,a2需要4天。


    由于整个工程只有一个开始点和一个完成点,故在正常情况(无环)下,网中只有一个入度为零的点(称作源点)和一个出度为零的点(叫做汇点)。
    那么该工程待研究的问题是:1.完成整项工程至少需要多少时间?2.哪些活动是影响工程进度的关键?
    由于在AOE-网中有些活动可以并行进行,所以完成工程的最短时间是从开始点到完成点的最长路径的长度(这里所说的路径长度是指路径上各活动持续时间之和,不是路径上弧的数目)。路径长度最长的路径叫做关键路径(Critical path)。
    假设开始点是v1,从v1到vi的最长路径叫做时间vi的最早发生时间。这个时间决定了所有以vi为尾的弧所表示的活动的最早开始时间。我们用e(i)表示活动ai的最早开始时间。还可以定义一个活动开始的最迟时间l(i),这是在不推迟整个工程完成的前提下,活动ai最迟必须开始进行的时间。两者之差l(i)-e(i)意味着完成活动ai的时间余量。当这个时间余量等于0的时候,也即是l(i)=e(i)的活动,我们称其为关键活动。显然,关键路径上的所有活动都是关键活动,因此提前完成非关键活动并不能加快工程的进度。
    因此,分析关键路径的目的是辨别哪些是关键活动,以便争取提高关键活动的功效,缩短整个工期。

    4. 如何实现关键路径?
    由上面的分析可知,辨别关键活动就是要找e(i)=l(i)的活动。为了求得e(i)和l(i),首先应求得事件的最早发生时间ve(j)和最迟发生时间vl(j)。如果活动ai由弧<j,k>表示,其持续时间记为dut(<j,k>),则有如下关系
    e(i) = ve(j)
    l(i) = vl(k) - dut(<j,k>)
    求解ve(j)和vl(j)需分两个步进行:
    1) 从ve(0)=0开始向前推进求得ve(j)
    Ve(j) = Max{ve(i) + dut(<i,j>) };<i,j>属于T,j=1,2...,n-1
    其中T是所有以第j个顶点为头的弧的集合。

    2) 从vl(n-1) = ve(n-1)起向后推进求得vl(j)
    vl(i) = Min{vl(j) - dut(<i,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条弧<j,k>,建立AOE-网的存储结构
    2. 拓扑排序,并求得ve[]。从源点V0出发,令ve[0]=0,按拓扑有序求其余各顶点的最早发生时间ve[i]。如果得到的拓扑有序序列中顶点个数小于网中顶点数n,则说明网中存在环,不能求关键路径,算法终止;否则执行步骤3。
    3. 拓扑逆序,求得vl[]。从汇点Vn出发,令vl[n-1] = ve[n-1],按逆拓扑有序求其余各顶点的最迟发生时间vl[i]。
    4. 求得关键路径。根据各顶点的ve和vl值,求每条弧s的最早开始时间e(s)和最迟开始时间l(s)。若某条弧满足条件e(s) = l(s),则为关键活动。

    为了能按逆序拓扑有序序列的顺序计算各个顶点的vl值,需记下在拓扑排序的过程中求得的拓扑有序序列,这就需要在拓扑排序算法中,增设一个栈,以记录拓扑有序序列,则在计算求得各顶点的ve值之后,从栈顶到栈底便为逆拓扑有序序列。


    代码(自己编写:)

    arcnode.h

    #pragma once
    
    class arcnode
    {
    public:
    	arcnode(void);
    	arcnode(int x, int y):vertex(x), val(y), nextarc(NULL){}
    	~arcnode(void);
    public:
    	int vertex;
    	int val;
    	arcnode* nextarc;
    };
    node.h
    #pragma once
    #include "arcnode.h"
    class node
    {
    public:
    	node(void);
    	node(int x):vertex(x), firstarc(NULL){}
    	~node(void);
    public:
    	int vertex;
    	arcnode* firstarc;
    };
    #pragma once
    #include "node.h"
    class Dgraph
    {
    public:
    	Dgraph(void);
    	~Dgraph(void);
    	void createGraph(Dgraph &g);
    public:
    	int vernum;
    	int arcnum;
    	node* AdjList;
    	int *indegree;
    	int *outdegree;
    };
    Dgraph.cpp

    #include "StdAfx.h"
    #include "Dgraph.h"
    #include <string>
    #include <iostream>
    #include <fstream>
    using namespace std;
    
    
    Dgraph::Dgraph(void)
    {
    }
    
    Dgraph::~Dgraph(void)
    {
    }
    void Dgraph::createGraph(Dgraph &g)
    {
    	ifstream infile("F:\\test100.txt");
    	cout << "读取图的顶点数和边数!" << endl;
    	infile >> g.vernum >> g.arcnum;
    	cout << g.vernum << ' ' << g.arcnum << endl;
    	cout << "开始建立邻接表!" << endl;
    	g.indegree = new int[g.vernum];
    	g.outdegree = new int[g.vernum];
    	g.AdjList = new node[g.vernum];//这里只是调用了node默认的构造函数,所以firstarc还是要重新复制
    	for (int i = 0; i < g.vernum; i++)
    	{
    		g.indegree[i] = 0;
    		g.outdegree[i] = 0;
    		g.AdjList[i].vertex = i;
    		g.AdjList[i].firstarc = NULL;
    	}
    	int tail, head, val;
    	for (int i = 0; i < g.arcnum; i++)
    	{
    		infile >> tail >> head >> val;
    		cout << tail << ' ' << head << ' ' << val << endl;
    		arcnode* temp = new arcnode(head, val);
    		temp->nextarc = g.AdjList[tail].firstarc;
    		g.AdjList[tail].firstarc = temp;
    		g.indegree[head]++;
    		g.outdegree[tail]++;
    	}
    }
    关键路径.cpp

    // 关键路径.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include "Dgraph.h"
    #include <vector>
    #include <stack>
    #include <iostream>
    using namespace std;
    struct A 
    {
    	int tail;
    	int head;
    };
    void topuforearlyfinish(vector<int> &ve, Dgraph g, stack<int> &T)
    {
    	stack<int> s;
    	for (int i = 0; i < g.vernum; i++)
    	{
    		if (g.indegree[i] == 0)
    		{
    			s.push(i);
    			T.push(i);//入度为0的都入栈
    		}
    	}
    	while (!s.empty())
    	{
    		int key = s.top();
    		s.pop();
    		for (arcnode* i = g.AdjList[key].firstarc; i; i = i->nextarc)
    		{
    			g.indegree[i->vertex]--;
    			//下边是求顶点的最早完成时间
    			if (ve[key] + i->val > ve[i->vertex])
    			{
    				ve[i->vertex] = ve[key] + i->val;
    			}
    			if (g.indegree[i->vertex] == 0)
    			{
    				s.push(i->vertex);
    				T.push(i->vertex);
    			}
    		}
    	}
    }
    void topuforlastfinish(Dgraph g, stack<int> T, vector<int> ve, vector<int> &vl)
    {
    	for (unsigned int i = 0; i < vl.size(); i++)
    	{
    		vl[i] = ve[g.vernum - 1];//最晚完成时间都初始化为最后一个顶点的最早发生时间
    	}
    	while (!T.empty())
    	{
    		int key = T.top();
    		T.pop();
    		for (arcnode* i = g.AdjList[key].firstarc; i; i = i->nextarc)
    		{
    			//下边就是求顶点的最晚完成时间
    			if (vl[i->vertex] - i->val < vl[key])
    			{
    				vl[key] = vl[i->vertex] - i->val;
    			}
    		}
    	}
    }
    void CriticalPath(Dgraph g, vector<int> ve, vector<int> vl, vector<A> &path)
    {
    	for (int i = 0; i < g.vernum; i++)
    	{
    		for (arcnode* j = g.AdjList[i].firstarc; j; j = j->nextarc)
    		{
    			if (vl[j->vertex] - j->val == ve[i])
    			{
    				A temp;
    				temp.tail = i;
    				temp.head = j->vertex;
    				path.push_back(temp);
    			}
    		}
    	}
    }
    int _tmain(int argc, _TCHAR* argv[])
    {
    	Dgraph g;
    	g.createGraph(g);
    	vector<int> ve(g.vernum, 0);
    	vector<int> vl(g.vernum);
    	stack<int> t;
    	topuforearlyfinish(ve, g, t);
    	topuforlastfinish(g, t, ve, vl);
    	vector<A> path;
    	CriticalPath(g, ve, vl, path);
    	cout << "各项关键活动为:" << endl;
    	for (unsigned int i = 0; i < path.size(); i++)
    	{
    		cout << path[i].tail << "->" << path[i].head << endl;
    	}
    	system("pause");
    	return 0;
    }
    test100.txt

    9 11
    0 1 6
    0 2 4
    0 3 5
    1 4 1
    2 4 1
    3 5 2
    4 6 9
    4 7 7
    5 7 4
    6 8 2
    7 8 4

    结果:

    0->1

    1->4

    4->6

    4->7

    7->8

    6->8


    展开全文
  • 图——关键路径

    万次阅读 多人点赞 2019-04-02 09:10:27
    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[j] - len<Vk, Vj>。

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

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

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

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

    案例:

    原始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网的关键路径可能有多条。

    展开全文
  • 文章目录一,什么是关键路径二,求解关键路径需要的4个描述量三,如何求得关键路径 视频参考:6.6.4关键路径2–求解关键路径 一,什么是关键路径 【引例 1】某项目的任务是对A公司的办公室重新进行装修 如果10月1日...
  • 项目关键路径

    千次阅读 2016-06-23 17:53:42
    项目关键路径 项目关键路径,在项目管理中,关键路径是指网络终端元素的元素的序列,该序列具有最长的总工期并决定了整个项目的最短完成时间。关键路径的工期决定了整个项目的工期。任何关键路径上的终端元素的延迟...
  • 关键路径计算

    万次阅读 多人点赞 2017-09-03 13:58:48
     向图中,用顶点表示活动,用向边表示活动之间开始的先后顺序,则称这种向图为AOV网络;AOV网络可以反应任务完成的先后顺序(拓扑排序)。  在AOV网的边上加上权值表示完成该活动所需的时间,则称这样的...
  • 【笔记】AOE网与关键路径

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

    千次阅读 多人点赞 2018-10-15 18:25:32
    拓扑排序的另一个应用就是关键路径的问题,关键路径对应的是另一种网络:AOE网络。...在关键路径这个问题中,AOE网络指的是“Activity On Edge”,即图上的每一边表示的是一个活动,顶点作为各个“入度...
  • 关键路径详细原理

    千次阅读 2018-07-18 20:30:21
     关键路径,顾名思义,就是一个程序中最关键的路径,它关系到整个程序的时间进度,而关键二字指临界点。 我们需要引进个概念,AOE和AOV网。 二、AOE和AOV网  AOE和AOV网都是一个大型程序的示意图。而AOV关注...
  • 简单理解关键路径

    千次阅读 多人点赞 2020-03-03 20:40:09
    一,关键路径问题的相关概念 通常,一个项目可以被拆分成多个子项目,多个子项目间会具有并行和串行的特点。 例如造汽车时,造发动机和造车轮是可以并行完成的任务,而组装整车又必须等发动机和车轮等部件完成后...
  • 项目关键路径,指重要功能都已经完成,而且可以投入使用。  最长路径意思很明显,就是耗时最长的。项目后期维护,其实工作量非常大,有时会拖很久。  一般来说,最长路径包含关键路径。有时也不一定,可能会包含...
  • 如何求关键活动以及存在多条关键路径的输出(数据结构C语言版) ** 1.问题描述 关键路径: 通常把计划、施工过程、生产流程、程序流程等都当成一个工程。工程通常分为若干个称为“活动”的子工程。完成了这些...
  • WPF中两条路径渐变的探讨

    千次阅读 2007-09-18 22:39:00
    先看看比较简单的情形:如下图(关键点用红色圆点加以标识):(图1)上面图1中的第1幅图可以说是最简单的路径渐变了,它由两条直线为基础,中间以插值方式作了两条直线间的渐变(插入路径数量为8,加上原始两条直线,...
  • 关键路径的确定

    千次阅读 2013-07-06 14:37:27
    关键路径法的重点是确定项目的关键路径,将项目网络图中的每路径所有活动的历时分别相加,时间最长的路径就是关键路径关键路径上的活动称为关键活动,关键路径的节点称为关键节点,关键活动的总时差为零。因此,...
  • 关键路径

    千次阅读 2014-10-02 20:25:11
     关键路径法(Critical Path Method,CPM),又称为要径法,是计划项目活动中用到的一种算术方法。[1]对于有效的计划管理而言,关键路径是一个十分重要的工具。与计划评核术(Project Evaluation and ...
  • 关键路径

    千次阅读 2015-03-30 10:37:52
    关键路径 1、重要概念  (1)AOE (Activity On Edges)网络 如果在无向环的带权向图中用向边表示一个工程中的各项活动(Activity),用边上的权值表示活动的持续时间(Duration),用顶点表示事件...
  • 目录 0.图——判环 0.1.1无向图判断是否存在环 0.1.2向图判断是否存在环 0.2无向图判环 ...2.1.2关键路径:bool CriticalPath() 求关键路径的完整代码与测试用例: 无向图、向图判环...
  • 经典算法之关键路径

    千次阅读 2018-07-19 16:29:56
    问题提出: 设一个工程11项活动,9个事件,事件V1 ----- 表示整个工程开始,事件V9 ----- 表示整个工程结束。 每个事件的开始必须是它之前的活动已完成。...关键路径:AOE-网中,从起点到终点最长...
  • 关键路径上找时间,非关键路径上找资源
  • 数据结构之关键路径

    千次阅读 2016-09-14 16:55:15
    (首先先说明,作为一个有关键路径的图,图中的每边带权值,这些权值假设为活动持续的时间,顶点表示一个活动的开始或者结束这样一个事件)。 1,作为一个关键路径,需要用到的第一个函数是拓补排序的函数,...
  • C语言关键路径实现

    千次阅读 2017-01-22 11:07:57
    在工程中,要估算工程完成最短时间,就是要找到一从源点到汇点的带权路劲长度最长的路径,成为关键路径。 确定关键路径的四个描述量: 1. 事件vi的最早发生时间ve(i): 进入世界vi的每一活动都结束,vi才可...
  • 图之关键路径

    千次阅读 2017-11-14 15:26:37
    下面的内容摘自程杰的《大话数据结构》,这是一本...关键路径也正是研究这个临界点的问题。 在学习关键路径前,先了解一个AOV网和AOE网的概念: 用顶点表示活动,用弧表示活动间的优先关系的向图: 称
  • AOE网与关键路径

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

    千次阅读 多人点赞 2020-03-19 14:23:45
    文章目录拓扑排序和关键路径摘 要1:引言2:设计步骤:etv和ltv数组的计算方法算法思想2. 实现代码建立(以邻接表为例)邻接表建立栈的建立拓扑排序关键路径的查找完整代码编译环境3.后记 拓扑排序和关键路径 摘 要 ...
  • 关键路径详解

    千次阅读 2017-08-20 17:59:05
    区别于AOV网,AOE网的边是权值的,代表完成事件的时间。 你需要先了解拓扑排序的有关知识。具体详见博文:http://blog.csdn.net/lee18254290736/article/details/77430334 在这里引入几个概念: 起始点...
  • 1.关键路径(Critical Path)从起点到终点的花费时间最长的一关键路径。 注意:在关键路径上的任务的松弛时间为0 ●最早开始时间:在关键路径上,从开始到该任务的最早执行的时间 ●最晚开始时间:关键...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 166,192
精华内容 66,476
关键字:

关键路径可以有两条吗