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天 。
由于整個工程只有一個開始點和一個完成點，故在正常情況(無環)下，網中只有一個入度為零的點(稱作源點)和一個出度為零的點(叫做匯點) 。
那么該工程待研究的問題是：1.完成整項工程至少需要多少時間？2.哪些活動是影響工程進度的關鍵？
由于在AOE-網中有些活動可以并行進行，所以完成工程的最短時間是從開始點到完成點的最長路徑的長度(這里所說的路徑長度是指路徑上各活動持續時間之和，不是路徑上弧的數目) 。路徑長度最長的路徑叫做關鍵路徑(Critical path) 。
假設開始點是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) 。若某條弧滿足條件e(s) = l(s)，則為關鍵活動 。

推薦閱讀