什麼時候用關鍵路徑演算法

㈠ 關鍵路徑怎麼求求詳解。

關鍵路徑的演算法是建立在拓撲排序的基礎之上的，這個演算法中用到了拓撲排序。

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天。

packagegraph;
importjava.util.*;
publicclassGrph_CriticalPath
{
Graph_AdjListadjList;
Stack<Integer>T=newStack<Integer>();
intve[];
intvl[];
finalintmax=10000;

publicGrph_CriticalPath(Graph_AdjListadjList)//圖的存儲結構是用的鄰接表
{
this.adjList=adjList;
intlength=adjList.vetexValue.length;
ve=newint[length];
vl=newint[length];
for(inti=0;i<length;i++)
{
ve[i]=0;
vl[i]=max;
}
}

publicvoidgetCriticalPath()
{
topologicalOrder();

intt=T.pop();
T.push(t);
vl[t]=ve[t];
while(!T.isEmpty())
{
intj=T.pop();
for(Graph_AdjList.ArcNodep=adjList.vetex[j].firstArc;p!=null;p=p.next)
{
intk=p.adjvex;
if(vl[k]-p.weight<vl[j])
{
vl[j]=vl[k]-p.weight;
}
}
}
for(inti=0;i<ve.length;i++)
{
for(Graph_AdjList.ArcNodep=adjList.vetex[i].firstArc;p!=null;p=p.next)
{
intk=p.adjvex;
intee=ve[i];
intel=vl[k]-p.weight;
if(ee==el)
{
System.out.print(i+","+k+"");
}

}
}
}

publicvoidtopologicalOrder()
{
Stack<Integer>S=newStack<Integer>();
S.push(0);
intcount=0;
while(!S.isEmpty())
{
intj=S.pop();
T.push(j);
count++;
Graph_AdjList.ArcNodep=null;
for(p=adjList.vetex[j].firstArc;p!=null;p=p.next)
{
intk=p.adjvex;
if(--adjList.degree[k]==0)
{
S.push(k);
}
if(ve[j]+p.weight>ve[k])
{
ve[k]=ve[j]+p.weight;
}
}
}
if(count<adjList.vetexValue.length)
{
System.out.println("圖中存在環路！");
return;
}
}

publicvoidprint()
{
while(!T.isEmpty())
{
System.out.print(T.pop()+"");
}
}

publicvoidprintVel()
{
System.out.println();
for(inti=0;i<ve.length;i++)
{
System.out.print(ve[i]+"");
}
System.out.println();
for(inti=0;i<vl.length;i++)
{
System.out.print(vl[i]+"");
}
}


}

轉自：http://blog.csdn.net/pigli/article/details/5777048

㈡ pmp如何計算關鍵路徑

pmp計算關鍵路徑的方法如下：

關鍵路徑法（Critical Path Method）是一種用來預測總體項目歷時的項目源網路分析技術。所謂「關鍵路徑」，是指當我們完成了項目進計劃後，在項目的網路圖上，存在著若干條從項目啟動到項目結束之間的路徑，但是對其中一條（嚴格的來說，可能存在一條以上）路徑上來說。

所謂正推法就是從項目的第一個活動到最後一個活動跟蹤全部活動的先後關系，計知算出每個活動的最早開始時間（ES）和最早結束時間（EF）。

所謂倒道推法則是從最後一個活動開始向前追溯到第一個活動，計算出每個活動的最晚開始時間（LS）和最晚結束時間（LF）。

PMP作為項目管理資格認證考試，已在國際上樹立了其權威性：

1、PMP為美國培養了一大批項目管理專業人才，項目管理職業已成為美國的「黃金職業」。在中國許多媒體已把PMP稱為繼MBA，MPA之後的三大金字招牌之一；

2、PMP認證已成為了一個國際性的認證標准，用英語、德語、法語、日語、韓語、西班牙語、葡萄牙語和中文等九種語言進行認證考試；

3、到目前為止，全球有80多萬名PMP，中國大陸地區獲得「PMP」頭銜的已有18萬多人，並逐年增長；

4、各國紛紛效仿美國的項目管理認證制度，推動了世界項目管理的發展。

㈢ cpm是什麼意思

CPM在項目計劃管理方法中代表的是什麼意思?你們可曾接觸過?下面是我給大家整理的cpm是什麼意思，供大家參閱!

cpm是什麼意思

關鍵路徑法(Critical Path Method, CPM)是一種基於數學計算的項目計劃管理方法，是網路圖計劃方法的一種，屬於肯定型的網路圖。關鍵路徑法將項目分解成為多個獨立的活動並確定每個活動的工期，然後用邏輯關系(結束-開始、結束-結束、開始-開始和開始結束)將活動連接，從而能夠計算項目的工期、各個活動時間特點(最早最晚時間、時差)等。在關鍵路徑法的活動上載入資源後，還能夠對項目的資源需求和分配進行分析。關鍵路徑法是現代項目管理中最重要的一種分析工具。

CPM關鍵路徑法應用

在60年代初期，PERT的發展比較迅速，據統計，到1964年，關於PERT的參考書目和論文達到了1000多種。到1961年，各種基於PERT的類似的方法出現，如PERT/Cost,PERT-RAMPS(Resource Allocation & Multi-Project Schele)，MAPS，SCANS，TOPS，PEP，TRACE，LESS和PAR等。其中PEP法是將甘特圖的活動賦以邏輯關系，這是計劃軟體一般採用的一種圖形輸出方法。1962年的時候，時任美國國防部長MacNamara在起草一項法令時，指出計劃評審法和關鍵路徑法同時並存的局面容易引起混淆，以後國防部的所有部門一律使用計劃評審法(PERT)，這在當時對於關鍵路徑法的提倡者是一個重大打擊，不過在隨後的發展中，關鍵路徑法(CPM)逐漸佔了優勢，真正使用計劃評審法的其實已經很少。而且即使是在當時，很多所謂的計劃評審法(PERT)，其實質其實是關鍵路徑法(CPM)。如美國航空局(NASA)當時使用的NASA-PERT，實際就是關鍵路徑法(CPM)。

無論是關鍵路徑法(CPM)還是計劃評審法(PERT)，最初使用的表示方法都是箭線法(ADM)，在之後很長的一段時間箭線法(ADM)都是人們主要使用的方法，直到70年代以後，前導圖(PDM)才開始逐漸流行起來，但是箭線法(ADM)仍然使用極為廣泛。在90年代以後，美國Primavera公司開發出其Windows版本的計劃管理軟體時，只採用前導圖(PDM)作為其計算平台，從根本上改變了這一局面，從此以後，前導圖(PDM)成了人們主要使用的方法，而箭線圖(ADM)則很少使用。

CPM關鍵路徑法時間計算

在進行計算時，箭線圖和前導圖的計算過程有所不同。

正推法

箭線圖(ADM)的計算一般有正推法(Forward Pass)和逆推法(Backward Pass)兩種，正推法用於計算活動和節點的最早時間，其演算法如下：

⒈設置箭線圖(ADM)中的第一個節點的時間，如設置為1。

⒊令活動最早開始時間等於其開始節點的最早時間。

⒋在選擇的活動的最早開始時間上加上其工期，就是其最早結束時間。

⒌比較此活動的最早結束時間和此活動結束節點的最早時間。如果結束節點還沒有設置時間，則此活動的最早結束時間就是該結束節點的最早時間;如果活動的結束時間比結束節點的最早時間大，則取此活動的最早結束時間作為節點的最早時間;如果此活動的最早結束時間小於其結束節點的最早時間，則保留此節點時間作為其最早時間。

⒍檢查是否還有其它活動開始於此節點，如果有，則回到步驟3進行計算;如果沒有，則進入下一個節點的計算，並回到步驟3開始，直到最後一個節點。

逆推法

活動和節點的最遲時間採用逆推法(Backward Pass)計算，逆推法(Backward Pass)一般從項目的最後一個活動開始計算，直到計算到第一個節點的時間為止，在逆推法的計算中，首先令最後一個節點的最遲時間等於其最早時間，然後開始計算，具體的計算步驟如下所示：

⒈設置最後一個節點的最遲時間，令其等於正推法計算出的最早時間。

⒉選擇一個以此節點為結束節點的活動進行計算。

⒊令此活動的最遲結束時間等於此節點的最遲時間。

⒋從此活動的最遲結束時間中減去其工期，得到其最遲開始時間。

⒌比較此活動的最遲開始時間和其開始節點的最遲時間，如果開始節點還沒有設置最遲時間，則將活動的最遲開始時間設置為此節點的最遲時間，如果活動的最遲開始時間早於節點的最遲時間，則將此活動的最遲開始時間設置為節點的最遲時間，如果活動的最遲開始時間遲於節點的最遲時間，則保留原節點的時間作為最遲時間

⒍檢查是否還有其它活動以此節點為結束節點，如果有則進入第二步計算，如果沒有則進入下一個節點，然後進入第二步計算，直至最後一個節點。

⒎第一個節點的最遲時間是本項目必須要開始的時間，假設取最後一個節點的最遲時間和最早時間相等，則其值應該等於1。

㈣ 關鍵路徑怎麼算

關鍵路徑的計算方法如下：

（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)的為關鍵活動。

求關鍵路徑是在拓撲排序的前提下進行的，不能進行拓撲排序，自然也不能求關鍵路徑。

關鍵路徑是指設計中從輸入到輸出經過的延時最長的邏輯路徑。優化關鍵路徑是一種提高設計工作速度的有效方法。一般地，從輸入到輸出的延時取決於信號所經過的延時最大路徑，而與其他延時小的路徑無關。

(4)什麼時候用關鍵路徑演算法擴展閱讀：

一、拓撲排序的執行

由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)。