關鍵路徑

關鍵路徑

關鍵路徑是指設計中從輸入到輸出經過的延時最長的邏輯路徑。最佳化關鍵路徑是一種提高設計工作速度的有效方法。一般地，從輸入到輸出的延時取決於信號所經過的延時最大路徑，而與其他延時小的路徑無關。在最佳化設計過程中關鍵路徑法可以反覆使用，直到不可能減少關鍵路徑延時為止。EDA工具中綜合器及設計分析器通常都提供關鍵路徑的信息以便設計者改進設計，提高速度。

基本介紹

  • 中文名：關鍵路徑
  • 外文名：Critical Path
  • 套用學科：數學 運籌學 計算機
  • 別稱：要徑法
  • 套用：計畫項目活動
  • 發明：杜邦公司
介紹,步驟,相關術語,套用,算法,代碼,參見,

介紹

關鍵路徑通常（但並非總是）是決定項目工期的進度活動序列。它是項目中最長的路徑，即使很小浮動也可能直接影響整個項目的最早完成時間。關鍵路徑的工期決定了整個項目的工期，任何關鍵路徑上的終端元素的延遲在浮動時間為零或負數時將直接影響項目的預期完成時間（例如在關鍵路徑上沒有浮動時間）。但特殊情況下，如果總浮動時間大於零，則有可能不會影響項目整體進度。
一個項目可以有多個、並行的關鍵路徑。另一個總工期比關鍵路徑的總工期略少的一條並行路徑被稱為次關鍵路徑。最初，關鍵路徑方法只考慮終端元素之間的邏輯依賴關係。關鍵鏈方法中增加了資源約束。關鍵路徑方法是由杜邦公司發明的。

步驟

A、從開始頂點 v1 出發，令 ve(1)=0，按拓撲有序序列求其餘各頂點的可能最早發生時間。
Ve(k)=max{ve(j)+dut(<j,k>)} , j ∈ T 。其中T是以頂點vk為尾的所有弧的頭頂點的集合（2 ≤ k ≤ n）。
如果得到的拓樸有序序列中頂點的個數小於網中頂點個數n，則說明網中有環，不能求出關鍵路徑，算法結束。
B、從完成頂點
出發，令
，按逆拓撲有序求其餘各頂點的允許的最晚發生時間：
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網
用頂點表示事件，弧表示活動，弧上的權值表示活動持續的時間的有向圖叫AOE（Activity On Edge Network）網。在建築學中也稱為關鍵路線。AOE網常用於估算工程完成時間。例如：圖1 是一個網。其中有9個事件v1,v2,…,v9；11項活動a1,a2,…,a11。每個事件表示在它之前的活動已經完成，在它之後的活動可以開始。如 v1表示整個工程開始，v9 表示整個工程結束。V5表示活動a2和a3已經完成，活動a7和a8可以開始。與每個活動相聯繫的權表示完成該活動所需的時間。如活動a1需要6個時間單位可以完成。
圖1.有向網路圖1.有向網路
一個AOE網的關鍵路徑可以不止一條。
只有在某頂點所代表的事件發生後，從該頂點出發的各有向邊所代表的活動才能開始。只有在進入某一頂點的各有向邊所代表的活動都已經結束，該頂點所代表的事件才能發生。表示實際工程計畫的AOE網應該是無環的，並且存在唯一的入度為0的開始頂點和唯一的出度為0的完成頂點。
（2） 活動開始的最早時間e(i)；
（3） 活動開始的最晚時間l(i) 定義e(i)=l(i）的活動叫關鍵活動；
（4） 事件開始的最早時間ve(i)；
（5） 事件開始的最晚時間vl(i)。

套用

（1） 完成整個工程至少需要多少時間；
（2） 哪些活動是影響工程的關鍵。
1956年，美國杜邦公司提出關鍵路徑法，並於1957年首先用於1000萬美元化工廠建設，工期比原計畫縮短了4個月。杜邦公司在採用關鍵路徑法的一年中，節省了100萬美元。

算法

（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） 只有在不改變關鍵路徑的前提下，縮短關鍵活動才能縮短整個工期。

代碼

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[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);
}
}
C++完整代碼
#include <iostream>
#include <cstdio>
#include<string.h>
using namespace std;
int n,m,w[1001][1001],prev[1001],queue[1001],Time[1001],l=0,r=0,Pos[1001],path[1001];
void init()
{
int i,a,b,c;
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
w[a][b]=c;
prev[b]++;
}
}
inline void Newq(int v)
{
r++;
queue[r]=v;
}
inline void Del(int v)
{
int i;
for (i=1;i<=n;i++)
if (w[v][i])
{
prev[i]--;
if (!prev[i])
Newq(i);
}
}
void topo()
{
for (int i=1;i<=n;i++)
if (!prev[i])
Newq(i);
while (r<n)
{
l++;
Del(queue[l]);
}
}
void crucialpath()
{
int i,j;
memset(Time,0,sizeof(Time));
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
if ((w[j][queue[i]]) && (Time[j]+w[j][queue[i]]>Time[queue[i]]))
{
Time[queue[i]]=Time[j]+w[j][queue[i]];
Pos[queue[i]]=j;
}
}
void print()
{
printf("%d\n",Time[n]);
int i=n,k=0;
while (i!=1)
{
k++;
path[k]=i;
}
for (i=k;i>1;i--)
printf("%d ",path[i]);
printf("%d\n",path[1]);
}
int main()
{
init();
topo();
crucialpath();
print();
return 0;
}

參見

  • 甘特圖
  • 計畫評審技術（PERT）
  • 項目
  • 項目管理
  • 項目計畫
  • 工作分解結構
  • 關鍵鏈

相關詞條

熱門詞條

聯絡我們