關鍵路徑等于最長路徑嗎關鍵路徑怎么找 _經驗分享

什么是關鍵路徑關鍵路徑是指設計中從輸入到輸出經過的延時最長的邏輯路徑。優化關鍵路徑是一種提高設計工作速度的有效方法。一般地，從輸入到輸出的延時取決于信號所經過的延時最大路徑，而與其他延時小的路徑無關。在優化設計過程中關鍵路徑法可以反復使用，直到不可能減少關鍵路徑延時為止。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網絡中執行時間最長的路徑路徑，自然長度最長的。從這點上來說關鍵路徑就是最長路徑。
（望樓主采納哦）
關于關鍵路徑和關鍵路徑怎么找的內容就分享到這兒！更多實用知識經驗，盡在 m.apearl.cn

關鍵路徑等于最長路徑嗎 關鍵路徑怎么找

關鍵路徑等于最長路徑嗎關鍵路徑怎么找