关键路径（关键路径法）

今天我想和大家分享一个关于关键路径(关键路径法)的问题。以下是这个问题的总结。让我们来看看。

如何找到关键路径

首先要知道关键路径是什么。关键路径是项目计划中最长的一组路径。一般来说，因为关键路径最长，项目要完成才能完成，所以最“关键”。

如图所示，路径A耗时最长，因此最“关键”。a需要28小时，所以答案是a和b。

简介

路径是用绘图工具创建的任意曲线，可以勾勒出物体的轮廓，所以也叫轮廓线。为了满足绘图的需要，路径分为开放路径和封闭路径。

GIMP/ Adobe illustrator中所有的矢量图都是由路径组成的。绘制矢量图就是建立和编辑路径。路径由若干线段组成，其中可能包括直线和各种曲线段。

为了更好的绘制和修改路径，每条线段的两端都有锚点来固定。通过移动锚点，您可以修改线段的位置并更改路径的形状。

此外，路径的概念也存在于非矢量绘图工具中。

什么叫做关键路径

关键路径是指设计中从输入到输出延迟最长的逻辑路径。优化关键路径是提高设计速度的有效方法。一般来说，从输入到输出的延迟取决于延迟最大的路径，与其他延迟小的路径无关。关键路径法可以在优化设计过程中反复使用，直到关键路径延迟无法降低。EDA工具中的合成器和设计分析器通常为设计人员提供关键路径信息，以改进设计和加快速度。

关键路径通常(但不总是)是一系列决定项目持续时间的进度活动。它是项目中最长的一条路径，甚至一个小小的波动都可能直接影响整个项目的最早完工时间。关键路径的持续时间决定了整个项目的持续时间，任何关键路径上终端元素的延迟都会直接影响到项目在浮动时间为零或为负时(例如关键路径上没有浮动时间)的预期完成时间。[2]但在特殊情况下，如果总浮动时间大于零，可能不会影响项目的整体进度。

一个项目可以有多个平行的关键路径。总持续时间比关键路径稍短的另一条平行路径称为次要关键路径。最初，关键路径方法只考虑了终端元素之间的逻辑依赖关系。关键链方法中增加了资源限制。关键路径法是杜邦公司发明的。

关键路径怎么求？求详解。

关键路径算法是基于拓扑排序的，并且拓扑排序被用在该算法中。

1.什么是拓扑排序？

比如软件专业学习一系列的课程，有些课程只有在完成基本的先修课程后才能开始。比如你要先学习编程和离散数学的基础知识，然后才能开始学习数据结构。这些先决条件定义了课程之间的主导(优先)关系。这种关系可以用有向图更清楚地表达出来。图中的顶点代表课程，有向边代表先决条件。如果课程I是课程J的先决条件，则图中有弧线I和J。如果要对这个图中顶点所代表的球场进行拓扑排序，排序后得到的序列必须按顺序排序，具有领先关系的球场必须排在基于它的球场之前。如果上面例子中的基本编程和离散数学必须在数据结构之前。拓扑排序后的序列称为拓扑序列。

2.如何实现拓扑排序？

很简单，两步:

1.在有向图中选择一个没有前身的顶点并输出。

2.从图中删除顶点和以它结束的弧。

重复上述两个步骤，直到所有顶点都已输出，或者当前图中不存在没有前辈的顶点。后一种情况表明在有向图中存在一个圈。

3.关键路径是什么？

在这个例子的开始，图1是一个假想的有11个活动的A0E网络。有九个事件v1、v2...而v9，每个事件都表示只要它的前一个活动完成，它的后续活动就可以开始。比如v1表示整个项目的开始，v9表示整个项目的结束，v5表示a4和a5已经完成，a7和a8可以开始。与每个活动相关联的数字是执行该活动所需的时间。例如，活动a1需要6天，活动a2需要4天。

因为整个工程只有一个起点和一个终点，一般情况下(无环)，网络中只有一个零贯穿点(称为源点)和一个零贯穿点(称为汇点)。

那么本课题要研究的问题是:1。完成整个项目需要多长时间？2.哪些活动是影响项目进度的关键？

因为AOE网络的一些活动可以并行进行，所以完成项目的最短时间是从起点到终点的最长路径的长度(这里的路径长度是指路径上每个活动持续时间的总和，而不是路径上的弧数)。路径长度最长的路径称为关键路径。

假设起点为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)。如果arc满足条件e(s) = l(s)，则它是关键活动。

为了根据逆拓扑有序序列的顺序计算每个顶点的vl值，需要记录拓扑排序过程中得到的拓扑有序序列，这就需要在拓扑排序算法中增加一个栈来记录拓扑有序序列，然后计算每个顶点的ve值，逆拓扑有序序列是从栈顶到栈底。

包装图；

导入Java . util . *；

通用类Grph_CriticalPath

{

Graph _ AdjList adjList

栈整数T =新栈整数()；

int ve[]；

int VL[]；

最终int max = 10000

public grph _ critical path(graph _ adj list adj list)//图的存储结构是邻接表。

{

这个。adj list = adj list

整数长度=调整列表。vetexvalue。长度；

ve = new int[length]；

VL = new int[长度]；

for(int I = 0；ilengthi++)

{

ve[I]= 0；

VL[I]= max；

}

}

public void getCriticalPath()

{

topologicalOrder()；

int t = t . pop()；

t。推(t)；

VL[t]= ve[t]；

还有(！T.isEmpty())

{

int j = t . pop()；

for(Graph_AdjList .ArcNode p = adjList.vetex[j].firstArcp！= nullp = p.next)

{

int k = p . adj vex

if(vl[k]-p.weightvl[j])

{

VL[j]= VL[k]-p .重量；

}

}

}

for(int I = 0；五、长度；i++)

{

for(Graph_AdjList .ArcNode p = adjList.vetex[i].firstArcp！= nullp = p.next)

{

int k = p . adj vex

int ee = ve[I]；

int El = VL[k]-p . weight；

if(ee==el)

{

System.out.print(i+\"，\"+k+\" \")；

}

}

}

}

Public 空拓扑规则()

{

stack integer S = new stack integer()；

s。推送(0)；

int count = 0；

还有(！S.isEmpty())

{

int j = s . pop()；

T.push(j)；

count++；

Graph_AdjList .ArcNode p = null

for(p = adjList.vetex[j]).firstArcp！= nullp = p.next)

{

int k = p . adj vex

if( - adjList.degree[k]==0)

{

推(k)；

}

if(ve[j]+p.weightve[k])

{

ve[k]= ve[j]+p . weight；

}

}

}

if(countadjlist。vetexvalue。长度)

{

System.out.println(\"图中有循环！\");

返回；

}

}

公共无效打印()

{

还有(！T.isEmpty())

{

系统。出去。print(t . pop()+\" \")；

}

}

公共void printVel()

{

系统。出去。println()；

for(int I = 0；五、长度；i++)

{

系统。出去。print(ve[I]+\" \")；

}

系统。出去。println()；

for(int I = 0；Ivl。长度；i++)

{

系统。出去。print(VL[I]+\" \")；

}

}

}

转移自:

关键路径是什么

问题1:什么是关键路径？在项目管理中，关键路径是指网络终端元素的顺序，它具有最长的总持续时间，并决定整个项目的最短完成时间。

关键路径的持续时间决定了整个项目的持续时间。任何关键路径上终端要素的延迟都会直接影响项目的预期完成时间(比如关键路径上没有浮动时间)。一个项目可以有多个平行的关键路径。总持续时间比关键路径稍短的另一条平行路径称为次要关键路径。最初，关键路径方法只考虑了终端元素之间的逻辑依赖关系。关键链方法中增加了资源限制。关键路径法是杜邦公司发明的。

问题2:图中的关键路径是什么？1-2-3-5-7-8-9.关键流程耗时最长，没有空空闲时间。

问题3:如何找到关键路径？首先要知道关键路径是什么。关键路径是项目计划中最长的一组路径。一般来说，因为关键路径最长，所以项目完成了才能完成。所以，是最“关键”的。

如图所示，路径A耗时最长，因此最“关键”。a需要28小时，所以答案是a和b。

问题4:如何计算关键路径？关键路径介绍。

关键路径是项目管理中进度控制的一个术语。

在项目的网络图中，项目从开始到完成有很多路径，就像从798艺术区到北京大学(图1)。如果20个人同时离开798艺术区，大家走不同的路(坐地铁、公交、汽车)，但是直到20个人全部到达北大，晚会才算完成。最后到达的人是走最长路线(花最多时间)的人。

图1

同样，直到最长(最耗时)的路径完成，项目才算完成。整个网络图中最长的路径称为关键路径。

让我们先给你一个关键路径的概述。让我们了解一些关键术语:

(1)最早开始时间是指活动可以开始的最早时间。

(2)最早结束时间(EF)是指一项活动能够完成的最早时间。

EF=ES+持续时间估计

根据ES和持续时间估计向前计算EF。

(3)最晚结束时间(LF)是指为了在要求的时间节点上完成一项活动，最晚必须完成的时间。

(4)最晚开始时间(LS)是指为了在要求的时间节点完成一项活动，最晚必须开始的时间。

Ls = lf-持续时间估计

LS是基于LF和时限估计反算得到的。

(5)总时差(TS):项目EF与项目要求完成时间之差，也称float。

总时差= lf-ef或总时差= ls-es，两种计算方法得到的结果相等。

好吧，让我们回到关键路径。确定关键路径的一种方法是找到那些差异最小的活动。用每个活动的LF-EF(或者LS-ES，结果相同)，然后找出最小的活动(要么最小的正时差，要么最大的负时差)，那么这些活动都是关键路径上的活动。

图2

其中，累积时差时红线的时差最小，所以上图中的黄线就是这个项目的关键路径(图2)。同时，任务D和任务E是并行的。任务D的时差是7天，而任务E的时差是8天，所以任务D的浮动时间是1天(如图3)。

图3

值得注意的是，如果项目很大，一个项目网络图从开始到结束会有很多路径。一些路径可能总是具有正时差，而另一些路径可能具有负时差。那些总时差为正的路径也称为非关键路径，而那些总时差始终为零或负的路径称为关键路径。在这种情况下，花费时间最长的路径将被称为最不重要的路径。

最后，让我们总结一下关键路径法的四个要点:

(1)关键路径是项目网络图中最长的路径，它决定了项目的总耗时；

(2)项目经理必须专注于那些优先级较高的任务，以保证按时完成，关键路径上任何活动的延误都会导致整个项目的延误；

(3)关键路径需要时间，非关键路径需要资源；

(4)调整进度，平衡资源。

问题5:操作系统的关键路径是什么？系统环境中的所有可变路径都是关键路径。

我的系统的路径变量值:

c:\\ windows \\ system32；c:\\ windows；c:\\ windows \\ System32 \\ Wbem；c:\\ windows \\ System32 \\ windows powershell \\ v 1.0 \\；c:\\ Program Files(x86)\\ NVIDIA company \\ PhysX \\ mon

问题6:什么是关键路径？为什么项目经理最关心关键路径？从网络图计划中每条路线的起点到终点，找出工期最长的路线，即关键路径。也就是说，整个项目的工期是由最长的一条线，也就是关键线决定的。

关键路径法是项目工期管理中一种非常实用的方法。其工作原理是:为每个最小任务单元计算持续时间，定义最早起止日期和最晚起止日期，根据活动的关系形成顺序网络逻辑图，找出必要的最长路径，即关键路径。确定关键线路，确定整个工期。

因此，项目经理必须最关注关键线路。通过优化关键路线，合理安排项目进度和资金使用计划，实现项目管理的最优化。

(1)关键路径上活动的持续时间决定了项目的持续时间，关键路径上所有活动的总持续时间就是项目的持续时间。

(2)关键路径上的任何活动都是关键活动，任何活动的延误都会导致整个项目完工时间的延误。

(3)花费在关键路径上的时间是能够完成的最短时间。如果花在关键路径上的总时间缩短了，项目工期就会缩短；否则，整个项目的总工期将会延长。但是，如果缩短非关键路径上各种活动所需的时间，项目的完工时间不会受到影响。

(4)关键路径上的活动是总时差最小的活动。改变其中一项活动的时间消耗可能会改变关键路径。

(5)关键路径可以有多条，它们的总时间必须相等，即总完工持续时间。

关键路径是相对的或可变的。采取一定的技术组织措施后，关键路径可能成为非关键路径，非关键路径也可能成为关键路径。

问题7:什么是关键路径法和关键链法？两者有什么区别？关键路径法和关键链法都是制定项目进度计划的工具。从概念定义来看，

关键路径法是指在给定的活动持续时间、逻辑关系、时间推进和时间滞后等约束条件下，不考虑任何资源约束，总时差为0或负值的活动序列。关键路径法是一种具有时间约束的进度网络分析工具，它的应用可以使工作安排尽早开始。

关键链法在考虑了资源约束后，制定了符合资源情况的进度模型，其特点是为影响进度的资源风险预留缓冲时间。活动持续时间通过确定(关键路径法)然后通过概率估算(减少活动持续时间的完成概率)来估算。确定关键路径后，考虑资源的存在和数量，确定资源限制计划。这种资源受限的日程经常会改变项目的关键路径。

关键链法的理论基础是帕金森定律。帕金森定律认为，工作总是被推迟到允许最晚完成的那一天。

问题8:数据结构的关键路径无法理解最早开始时间，也就是一个事件能够开始的最早时间。

例如，如果从A到B的时间是5，那么B的最早开始时间是5。

最晚开始时间意味着一个事件需要最晚开始，以避免落后于下一个事件。

比如从a到b的时间是5，从b到d的时间是2。

从a到c的时间是5，从c到d的时间是4。

此时D事件取决于B和C的完成，此时A、C和D的总时间为9，也就是说D最早的开始时间为9。

此时B的最晚开始时间是7，因为过了这个时间，D事件会因为B而延迟，所以它的开始时间会超过9。

问题9:在microsoft project中，查看关键路径的方式简单地切换为“跟踪甘特图”，右边图形区红色的任务都是关键路径；

在视图选项卡-数据区域，突出显示-键；

在视图选项卡-数据区域，筛选-关键字。

关键路径的介绍到此结束。感谢您花时间阅读本网站的内容。不要忘记搜索这个网站以获得更多关于关键路径方法和关键路径的信息。

以上就是由优质生活领域创作者 嘉文社百科网小编 整理编辑的，如果觉得有帮助欢迎收藏转发~