关键路径等于最长路径吗关键路径怎么找 _经验分享

什么是关键路径关键路径是指设计中从输入到输出经过的延时最长的逻辑路径。优化关键路径是一种提高设计工作速度的有效方法。一般地，从输入到输出的延时取决于信号所经过的延时最大路径，而与其他延时小的路径无关。在优化设计过程中关键路径法可以反复使用，直到不可能减少关键路径延时为止。EDA工具中综合器及设计分析器通常都提供关键路径的信息以便设计者改进设计，提高速度。
关键路径怎么算输入e条弧<j，k>，建立AOE网的存储结构；从源点v1出发，令ve(1)=0，求 ve(j)，2<=j<=n；从汇点vn出发，令vl(n)=ve(n)，求 vl(i)，1<=i<=n-1 。
根据各顶点的ve和vl值，求每条弧s（活动）的最早开始时间e(s)和最晚开始时间l(s)，其中e(s)=l(s)的为关键活动。
求关键路径必须在拓扑排序的前提下进行，有环图不能求关键路径；只有缩短关键活动的工期才有可能缩短工期；若一个关键活动不在所有的关键路径上，减少它并不能减少工期；只有在不改变关键路径的前提下，缩短关键活动才能缩短整个工期。
扩展资料
在项目管理中，编制网络计划的基本思想就是在一个庞大的网络图中找出关键路径，并对各关键活动，优先安排资源，挖掘潜力，采取相应措施，尽量压缩需要的时间。
而对非关键路径的各个活动，只要在不影响工程完工时间的条件下，抽出适当的人力、物力和财力等资源，用在关键路径上，以达到缩短工程工期，合理利用资源等目的。在执行计划过程中，可以明确工作重点，对各个关键活动加以有效控制和调度。
关键路径法主要为一种基于单点时间估计、有严格次序的一种网络图。它的出现为项目提供了重要的帮助，特别是为项目及其主要活动提供了图形化的显示，这些量化信息为识别潜在的项目延迟风险提供极其重要的依据。
参考资料来源：百度百科-关键路径法
参考资料来源：百度百科-关键路径
关键路径怎么算关键路径的计算方法如下：
（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)的为关键活动。
求关键路径是在拓扑排序的前提下进行的，不能进行拓扑排序，自然也不能求关键路径。
关键路径是指设计中从输入到输出经过的延时最长的逻辑路径。优化关键路径是一种提高设计工作速度的有效方法。一般地，从输入到输出的延时取决于信号所经过的延时最大路径，而与其他延时小的路径无关。
扩展资料：
一、拓扑排序的执行
【关键路径等于最长路径吗关键路径怎么找】由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。
（1）选择一个入度为0的顶点并输出之；
（2）从网中删除此顶点及所有出边。
循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。
二、关键路径相关术语
（1）AOE网
用顶点表示事件，弧表示活动，弧上的权值表示活动持续的时间的有向图叫AOE网。在建筑学中也称为关键路线。AOE网常用于估算工程完成时间。一个AOE网的关键路径可以不止一条。
只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。只有在进入某一顶点的各有向边所代表的活动都已经结束，该顶点所代表的事件才能发生。
表示实际工程计划的AOE网应该是无环的，并且存在唯一的入度为0的开始顶点和唯一的出度为0的完成顶点。
（2）活动开始的最早时间e(i)；
（3）活动开始的最晚时间l(i)；
（4）事件开始的最早时间ve(i)；
（5）事件开始的最晚时间vl(i) 。
参考资料：百度百科-拓扑排序
参考资料：百度百科-关键路径
5.7 关键路径在拓扑排序的AOV图基础上，给每条边加上权重AOV图就成了AOE图了。同样是描述工程或者一个过程的关于活动的图。
AOE的特点，存在源点和汇点，顶点代表事件，边代表活动。
就如工程中某些事件必须等待，所有在它前面的活动完成才会出现。
事件出现了，它后面的活动才能发生。
简单来说就是，要开始从顶点出发，要所有指向它的边都完成了才可以。
关键路径，就是从源点到汇点的最长路径，可以理解成工程的最短时间。
关键路径就是路径上所有的边的集合，关键活动就是路径上的顶点的集合。
最早发生时间：从源点到该顶点的最长路径
（只有耗时最长的那些活动完成，事件才能发生）
最晚发生时间：从顶点到该汇点的最长路径
（在最晚发生时间发生，耗时最长的活动才能完成，这样工程才不会延误）
注意：此处的最长，最短时间是基于，工程并发合理的理想条件下。
当事件的最早最晚发生时间一致的时候，表明该事件在关键路径上。只有不是耗时最长的活动最早最晚时间不一致，可以延误但不会导致整体工程延误。
因此，计算所有事件的最早最晚发生时间即可找到所有关键事件，事件之间连起来就是关键路径了。
什么是关键路径？在项目管理中，关键路径是指网络终端元素的元素的序列，该序列具有最长的总工期并决定了整个项目的最短完成时间。
求关键路径的算法分析
（1）求关键路径必须在拓扑排序的前提下进行，有环图不能求关键路径；（2）只有缩短关键活动的工期才有可能缩短工期；（3）若一个关键活动不在所有的关键路径上，减少它并不能减少工期；（4）只有在不改变关键路径的前提下，缩短关键活动才能缩短整个工期。
探寻关键路径
AOE网
用顶点表示事件，弧表示活动，弧上的权值表示活动持续的时间的有向图叫AOE（Activity On Edge Network）网。AOE网常用于估算工程完成时间。例如：图1
图1 是一个网。其中有9个事件v1，v2，…，v9；11项活动a1，a2，…，a11 。每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。如 v1表示整个工程开始，v9 表示整个工程结束。V5表示活动，a4和a5已经完成，活动a7和a8可以开始。与每个活动相联系的权表示完成该活动所需的时间。如活动a1需要6天时间可以完成。
AOE 网具有的性质
只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。只有在进入某一顶点的各有向边所代表的活动都已经结束，该顶点所代表的事件才能发生。表示实际工程计划的AOE网应该是无环的，并且存在唯一的入度过为0的开始顶点和唯一的出度为0的完成顶点。2)
最早发生时间和最晚发生时间的定义
可以采取如下步骤求得关键活动： A、从开始顶点 v 1 出发 , 令 ve(1)=0, 按拓朴有序序列求其余各顶点的可能最早发生时间。Ve(k)=max{ve(j) dut(<j,k>)} （ 1.1 ） j ∈ T 其中T是以顶点vk为尾的所有弧的头顶点的集合(2 ≤ k ≤ n)。如果得到的拓朴有序序列中顶点的个数小于网中顶点个数n，则说明网中有环，不能求出关键路径，算法结束。表1
B、从完成顶点 v n 出发，令vl(n)=ve(n)，按逆拓朴有序求其余各顶点的允许的最晚发生时间: vl(j)=min{vl(k)-dut(<j,k>)} k ∈ S 其中 S 是以顶点vj是头的所有弧的尾顶点集合(1 ≤ j ≤ n-1)。C、求每一项活动ai(1 ≤ i ≤ m)的最早开始时间e(i)=ve(j)；最晚开始时间： l(i)=vl(k)-dut(<j,k>) 若某条弧满足 e(i)=l(i)，则它是关键活动。对于图1所示的 AOE 网，按以上步骤的计算结果见表1，可得到a1 , a4 , a7 , a8 , a10 , a11 是关键活动。
AOE 网的关键路径
图2
这时从开始顶点到达完成顶点的所有路径都是关键路径。一个AOE网的关键路径可以不止一条，如图7.21的AOE网中有二条关键路径，(v1, v2, v5, v7 , v9 ) 和 (v1 , v2 , v5 , v8 , v9 )它们的路径长度都是16。如图2所示：
AOE网研究的问题
（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>) (6_6_1) 求ve(i)和vl(j)分两步： · 从ve(1)=0开始向前递推 ve(j)=Max{ ve(i)+dut(<i,j>) } (6_6_2) <i,j>T, 2<=j<=n 其中，T是所有以j为弧头的弧的集合。· 从vl(n)=ve(n)开始向后递推 vl(i)=Min{ vl(j)-dut(<i,j>) } (6_6_3) <i,j>S, 1<=i<=n-1 其中，S是所有以i为弧尾的弧的集合。两个递推公式是在拓扑有序和逆拓扑有序的前提下进行。4、求关键路径的算法 (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)的为关键活动。求关键路径是在拓扑排序的前提下进行的，不能进行拓扑排序，自然也不能求关键路径。Status ToplogicalSort(ALGraph G,stack &T){ FindInDegree(G,indegree); InitStack(S);count=0; ve[0..G.vexnum-1]=0; while(!StackEmpty(S)) { Pop(S,j);Push(T,j); ++count; for(p=G.vertices[j].firstarc;p;p=p->nextarc) {k=p>adjvex; if(--indegree[k]==0) Push(S,k); if(ve[j]+*(p->info)>ve[k]) ve[k]=ve[j]+*(p->info); } } if(count<G.vexnum) return ERROR; else return OK; } status CriticalPath(ALGraph G){ if(!ToplogicalOrder(G,T)) return ERROR; vl[0..G.vexnum-1]=ve[0..G.vexnum-1]; while(!StackEmpty(T)) for(Pop(T,j),p=G.vertices[j].firstarc;p;p=p->nextarc) {k=p>adjvex; dut=*(p->info); if(vl[k]-dut<vl[j]) vl[j]=vl[k]-dut; } for(j=0;j<G.vexnum;++j) for(p=G.vertices[j].firstarc;p;p=p->nextarc) {k=p>adjvex; dut=*(p->info); ee=ve[j]; el=vl[k]; tag=(ee==el)?’*’:’’; printf(j,kdut,ee,el,tag); } }
关键路径等于最长路径吗是的。
AOE (Activity On Edges)网络：如果在无有向环的带权有向图中用有向边表示一个工程中的各项活动(Activity)，用边上的权值表示活动的持续时间(Duration)，用顶点表示事件(Event)，则这样的有向图叫做用边表示活动的网络，简称AOE (Activity On Edges)网络。AOE网是一个带权的有向无环图。
关键路径(Critical Path )：在AOE网络中, 有些活动顺序进行，有些活动并行进行。从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，整个工程才算完成。因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(Critical Path) 。
道理很简单，就是几个人同时到一个地方集合，离得近的到得早，离得远的到得晚，但只有最晚到的人到了，大家才算凑到一块了，不知道这样说你明白不？可见关键路径是从源点到汇点的最长路径长度，也可以说关键路径是AOE网络中执行时间最长的路径路径，自然长度最长的。从这点上来说关键路径就是最长路径。
（望楼主采纳哦）
关于关键路径和关键路径怎么找的内容就分享到这儿！更多实用知识经验，尽在 www.hubeilong.com

关键路径等于最长路径吗 关键路径怎么找

关键路径等于最长路径吗关键路径怎么找