吉林大學(xué)數(shù)據(jù)結(jié)構(gòu)_關(guān)鍵路徑

1、關(guān)鍵路徑關(guān)鍵路徑 在上節(jié)介紹的AOV網(wǎng)中，頂點(diǎn)表示任務(wù)，有向邊表示任務(wù)之間的先后關(guān)系。在實(shí)際應(yīng)用中，除了執(zhí)行次序的先后關(guān)系外，通常還具有更為嚴(yán)格的時(shí)間約束，我們用AOE網(wǎng)網(wǎng)(Activity On Edge network) 表示多個(gè)活動(dòng)之間的時(shí)間約束關(guān)系。其中，有向邊表示活動(dòng)活動(dòng)，邊上的權(quán)值表示該活動(dòng)所需要的時(shí)間。頂點(diǎn)表示它的入邊的活動(dòng)已經(jīng)完成、它的出邊的活動(dòng)可以開始的一種狀態(tài)，也稱之為一個(gè)事件事件。由于整個(gè)工程通常只有一個(gè)開始點(diǎn)和一個(gè)完成點(diǎn)，所以在正常情況（無環(huán)）下，網(wǎng)中只有一個(gè)入度為零的點(diǎn)稱為源點(diǎn)源點(diǎn)，一個(gè)出度為零的點(diǎn)稱為匯點(diǎn)匯點(diǎn)。AOE網(wǎng)可以使人們了解：完成整個(gè)工程至少需要多少時(shí)間；為

2、縮短完成工程所需要的時(shí)間，應(yīng)當(dāng)加快哪些活動(dòng)；為了不延誤整個(gè)工程，哪些活動(dòng)不得延期，哪些活動(dòng)可以適當(dāng)延期。 在AOE網(wǎng)中，有些活動(dòng)可以并行進(jìn)行，因此，完成整個(gè)工程的最短時(shí)間是從源點(diǎn)到匯點(diǎn)完成整個(gè)工程的最短時(shí)間是從源點(diǎn)到匯點(diǎn)的最長路徑長度的最長路徑長度（路徑長度等于路徑上各邊的權(quán)之和，而不是路徑上弧的數(shù)目）。這條具有最大長度的路徑稱為關(guān)鍵路徑關(guān)鍵路徑。 要找出關(guān)鍵路徑，必須找出關(guān)鍵活動(dòng)關(guān)鍵活動(dòng)，即即不按期完成就會(huì)影響整個(gè)工程完成的活動(dòng)不按期完成就會(huì)影響整個(gè)工程完成的活動(dòng)。 關(guān)鍵路徑關(guān)鍵路徑上的所有活動(dòng)都是關(guān)鍵活動(dòng)上的所有活動(dòng)都是關(guān)鍵活動(dòng)。 因此因此，只要找到了關(guān)鍵活動(dòng)，就可以找到，只要找到了關(guān)鍵活

3、動(dòng)，就可以找到關(guān)鍵路徑。關(guān)鍵路徑。如何找關(guān)鍵如何找關(guān)鍵活動(dòng)？活動(dòng)？關(guān)鍵活動(dòng)有什么特點(diǎn)關(guān)鍵活動(dòng)有什么特點(diǎn)？與活動(dòng)相關(guān)的量與活動(dòng)相關(guān)的量 活動(dòng)的最早開始時(shí)間e(i) 活動(dòng)的最遲開始時(shí)間l(i) 完成活動(dòng)ai的時(shí)間余量l(i)-e(i)關(guān)鍵活動(dòng)的特點(diǎn)關(guān)鍵活動(dòng)的特點(diǎn)活動(dòng)的最遲開始時(shí)間等于活動(dòng)的最早開始時(shí)間，即l(i)=e(i) 分析關(guān)鍵路徑的目的是辨別在整個(gè)工程中哪些是關(guān)鍵活動(dòng)，以便爭(zhēng)取提高關(guān)鍵活動(dòng)的功效，縮短整個(gè)工程的工期。因此，問題的關(guān)鍵是要找l(i)=e(i)的活動(dòng)。(2)計(jì)算vl(j)需從匯點(diǎn)Tn開始，自右向左逐個(gè)事件逆推計(jì)算，直到源點(diǎn)T1為止。其計(jì)算順序是某個(gè)拓?fù)湫蛄械哪嫘?。我們知道，?duì)匯點(diǎn)

4、Tn而言，其最早發(fā)生時(shí)間與最遲發(fā)生時(shí)間是一致的，因此vl(n) = ve(n)計(jì)算vl(j)的遞推公式是： 1 ,., 1, )(, | ) , ()( min)()()(njGETTkjweightkvljvlnvenvlkjk 1 ,., 1, )(, | ) , ()( min)()()(njGETTkjweightkvljvlnvenvlkjk 1 ,., 1, )(, | ) , ()( min)()()(njGETTkjweightkvljvlnvenvlkjk求關(guān)鍵活動(dòng)的基本步驟求關(guān)鍵活動(dòng)的基本步驟aia1a2a3a4a5a6a7a8a9a10a11a12e(i)00064457

5、771615l(i)0246610987111715l(i)-e(i)024026410410可見，a1, a4, a9, a12為該工程的關(guān)鍵活動(dòng)，路徑T1T2T5T8T9就是從源點(diǎn)到匯點(diǎn)路徑長度為19的關(guān)鍵路徑。表 5.1 圖5.14中各個(gè)活動(dòng)的最早開始時(shí)間和最晚開始時(shí)間算法算法CriticalPath ()FOR i = 1 TO n DO ve i 0.FOR i = 1 TO n1 DO/*（1）按頂點(diǎn)的拓?fù)湫蛄杏?jì)算各事件的最早發(fā)生時(shí)間*/(padjacent(Head i) . WHILE p null DO(k VerAdj (p) .IF (ve i + cost (p) ve

6、k ) THENvek vei + cost (p) .plink(p) )CPath2計(jì)算事件的最遲發(fā)生時(shí)間FOR i = 1 TO n DO vli ven .FOR i = n1 TO 1 STEP 1 DO /*（2）按拓?fù)淠嫘蛴?jì)算事件的最遲發(fā)生時(shí)間*/(padjacent (Headi) .WHILE p null DO(kVerAdj(p) .IF (vlk cost (p) vli ) THENvli vlk cost(p) .plink(p) )CPath3求諸活動(dòng)的最早開始時(shí)間和最遲開始時(shí)間FOR i = 1 TO n DO (padjacent (Head i) .WHILE p null DO(kVerAdj (p) .evei .lvlk cost(p) .IF l = e THENPRINT is Critical Activity! plink(p) 設(shè)AOE網(wǎng)中頂點(diǎn)的個(gè)數(shù)為n ，邊的個(gè)數(shù)為e . 對(duì)頂點(diǎn)進(jìn)行拓?fù)渑判虻臅r(shí)間復(fù)雜性為O(n+e) ，以拓?fù)湫蛄星笾T事件的最早發(fā)生時(shí)間ve(i)的時(shí)間復(fù)雜性為O(e) ，以拓?fù)淠嫘蚯笾T事件的最遲發(fā)生時(shí)間vl(i)