數(shù)據(jù)結(jié)構(gòu),拓?fù)渑判蚝完P(guān)鍵路徑課件

1、第五章 拓?fù)渑判蚝完P(guān)鍵路徑吉林大學(xué)計(jì)算機(jī)學(xué)院谷方明fmgu2002問題背景計(jì)劃、施工過程、生產(chǎn)流程、程序流程等都可以看作一個(gè)任務(wù)或“工程”。除了很小的工程外，一般都把工程分為若干個(gè)叫做“活動(dòng)”的子任務(wù)。活動(dòng)之間一般會(huì)有先后關(guān)系。如果不違反限制完成這些活動(dòng)，那么整個(gè)工程順利完成。例：選課計(jì)算機(jī)專業(yè)學(xué)生的學(xué)習(xí)就是一個(gè)工程，每一門課程的學(xué)習(xí)就是整個(gè)工程的一項(xiàng)活動(dòng)。其中有些課程要求先修課程，有些則不要求。這樣在有的課程之間有先后關(guān)系，有的課程可以并行地學(xué)習(xí)。任務(wù)：安排一種學(xué)習(xí)次序，使得所有課程都學(xué)習(xí)完成，并滿足課程的限制關(guān)系。計(jì)算機(jī)專業(yè)必修課程課程代號(hào) 課程名稱 先修課程 C0 高等數(shù)學(xué) 無 C1 程

2、序設(shè)計(jì)基礎(chǔ) 無 C2 離散數(shù)學(xué) C0,C1 C3 數(shù)據(jù)結(jié)構(gòu) C2,C4 C4 程序設(shè)計(jì)語(yǔ)言 C1 C5 編譯技術(shù) C3,C4 C6 操作系統(tǒng) C3,C8 C7 普通物理 C0 C8 計(jì)算機(jī)原理 C7 C0C2C3C5C4C1C7C6C8在有向圖中，用頂點(diǎn)表示活動(dòng)，用有向邊表示活動(dòng)之間的先后關(guān)系，稱這樣的有向圖為AOV網(wǎng)(Activity On Vertex Network)。拓?fù)湫蛄校喊袮OV網(wǎng)中的所有頂點(diǎn)排成一個(gè)線性序列，該序列滿足如下條件：如果存在有向邊，則在該序列中，Vi 必位于Vj 之前。拓?fù)渑判颍簶?gòu)造AOV網(wǎng)的拓?fù)湫蛄械倪^程被稱為拓?fù)渑判颉Ｒ环N可能的拓?fù)湫蛄惺牵篊0 , C1 , C

3、2 , C4 , C3 , C5 , C7 , C8 , C6C0C2C3C5C4C1C7C6C8拓?fù)湫蛄械拇嬖谛匀我釧OV網(wǎng)中拓?fù)湫蛄胁灰欢ù嬖?。例如，存在回路的AOV網(wǎng)就無法找到拓?fù)湫蛄?。因?yàn)槌霈F(xiàn)了有向環(huán)，則意味著某項(xiàng)活動(dòng)應(yīng)以自己作為先決條件。有向無環(huán)圖一定存在拓?fù)湫蛄?。?gòu)造方法引理5.1： 設(shè)圖G = (V, E)是有向無環(huán)圖, V(G), 則G中一定存在入度為零的頂點(diǎn)。構(gòu)造方法： 從網(wǎng)中選擇一個(gè)入度為0的頂點(diǎn)且輸出之。 從網(wǎng)中刪除該頂點(diǎn)及其所有出邊。執(zhí)行 ，直至所有頂點(diǎn)已輸出，或網(wǎng)中剩余頂點(diǎn)入度均不為0 （說明網(wǎng)中存在回路）。C0 , C1 , C2 , C4 , C3 , C5 ,

4、C7 , C8 , C6C0 , C1 , C4 , C2 , C3 , C5 , C7 , C8 , C6C0 , C1 , C7 , C2 , C4 , C3 , C5 , C8 , C6C0C2C3C5C4C1C7C6C8算法設(shè)計(jì)AOV網(wǎng)用鄰接表的形式存儲(chǔ)；數(shù)組count ，counti的值是頂點(diǎn)i的入度；使用一個(gè)數(shù)據(jù)結(jié)構(gòu)，存放入度為0的點(diǎn)。線性表存放時(shí)發(fā)生在一端；取用順序無所謂，在同一端（棧）或另一端（隊(duì)列）。棧的模擬利用變量top和count數(shù)組元素的值來模擬堆棧的壓入和彈出。原理：利用入度為0的counti空間記錄棧元素的下標(biāo)；top始終記錄棧頂元素的下標(biāo)。拓?fù)渑判蛩惴ㄋ惴═opo

5、Order( ) /* 圖的拓?fù)渑判蛩惴ǎ琻表示頂點(diǎn)數(shù) */T1初始化 for( i = 1 ; i= n ; i + ) counti = 0; for( i = 1 ; ilink ) count p-VerAdj +; for( i = 1 ; i= n ; i + ) if( counti = 0 ) counti = top , top = i ;002123124536count436251toptop-102123124536count-112123124536countT2拓?fù)渑判?for( i = 1 ; i = n ; i+ ) if ( top = - 1 ) cout“

6、有回路! ”; RETURN; j = top , top = counttop . /* 彈出棧頂j */ cout link) k = p - VerAdj ; countk - ;/ 頂點(diǎn)k的入度減1 if (countk = 0 ) countk=top, top = k; 436251-111013124536counttop-112123124536counttop模擬棧的狀態(tài)初始化： top = -1;棧 空： top = -1入棧：counti = top; top = i;出棧：j = top; top = counttop;算法分析定理5.2 設(shè)G=(V, E)是有向無環(huán)圖

7、，V(G)=1, 2 , n, e=|E(G)|. 則算法TopoOrder是正確的且算法的時(shí)間復(fù)雜性為 O(n+e).正確性證明：初始化T1時(shí)，棧不為空T2時(shí)，如果G不空，棧也不空。輸出n個(gè)頂點(diǎn)結(jié)束設(shè)是邊，則 v 一定 排在 w 之前。拓展拓?fù)渑判蚺c有向環(huán)無回路的AOV網(wǎng)，其頂點(diǎn)可排成拓?fù)湫蛄校挥谢芈返腁OV網(wǎng)，找不到所有頂點(diǎn)的拓?fù)湫蛄?；如果能將AOV網(wǎng)的所有頂點(diǎn)排成拓?fù)湫蛄?，則該AOV網(wǎng)中必定無有向環(huán)；如果得不到所有頂點(diǎn)的拓?fù)湫蛄校瑒t說明AOV網(wǎng)中存在有向環(huán)(AOV網(wǎng)所代表的工程是不可行的)。拓?fù)湫蛄械膫€(gè)數(shù)關(guān)鍵路徑時(shí)間約束邊表示活動(dòng)(Activity) 邊的權(quán)值表示活動(dòng)的持續(xù)時(shí)間(Dura

8、tion) 頂點(diǎn)表示入邊的活動(dòng)已完成，出邊的活動(dòng)可以開始的狀態(tài)，也稱為事件(Event)這樣的有向無環(huán)帶權(quán)圖叫做AOE (Activity On Edges)網(wǎng)。例 某工程源點(diǎn)：表示整個(gè)工程的開始（入度為零）。匯點(diǎn)：表示整個(gè)工程的結(jié)束（出度為零）。完成整個(gè)工程至少需要多少時(shí)間？為縮短工程的時(shí)間，應(yīng)當(dāng)加快哪些活動(dòng)？為了不延誤整個(gè)工期，哪些活動(dòng)不得延期，哪些可適當(dāng)延期436251978a1=6a9=8a8=9a7=2a4=1a5=1a3=5a2=4a10=4a12=4a11=2匯點(diǎn)源點(diǎn)a6=1關(guān)鍵路徑和關(guān)鍵活動(dòng)AOE網(wǎng)中，有些活動(dòng)可并行進(jìn)行。只有各條路徑上所有活動(dòng)都完成了，整個(gè)工程才算完成。因此，

9、完成整個(gè)工程所需的時(shí)間取決于從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑長(zhǎng)度。路徑長(zhǎng)度等于路徑上各邊的權(quán)之和。這條具有最大長(zhǎng)度的路徑就叫做關(guān)鍵路徑。關(guān)鍵活動(dòng)：不按期完成就會(huì)影響整個(gè)工期的活動(dòng)。 關(guān)鍵路徑上的活動(dòng)為關(guān)鍵活動(dòng)；從源點(diǎn)到匯點(diǎn)由關(guān)鍵活動(dòng)構(gòu)成的路徑為關(guān)鍵路徑。436251978a1=6a9=8a8=9a7=2a4=1a5=1a3=5a2=4a10=4a12=4a11=2匯點(diǎn)源點(diǎn)a6=1關(guān)鍵活動(dòng)有關(guān)的量 事件vj的最早發(fā)生時(shí)間 ve( j ): 從源點(diǎn)v0到vj的最長(zhǎng)路徑長(zhǎng)度。436251978a1=6a9=8a8=9a7=2a4=1a5=1a3=5a2=4a10=4a12=4a11=2匯點(diǎn)源點(diǎn)a6=1ve(1

10、)=0ve(2)= 6ve(3)= 4ve(4)= 5ve(5)= 7ve(6)= 7ve(7)= 16ve(8)= 15ve(9)= 19 事件vj的最遲發(fā)生時(shí)間 vl ( j ): 保證匯點(diǎn)的最早發(fā)生時(shí)間不推遲的前提下，事件vj允許的最遲開始時(shí)間，等于ve(n)減去從vj到vn最長(zhǎng)路徑長(zhǎng)度。436251978a1=6a9=8a8=9a7=2a4=1a5=1a3=5a2=4a10=4a12=4a11=2匯點(diǎn)源點(diǎn)a6=1vl(9)= 19vl(8)= 15vl(7)= 17vl(6)= 11vl(5)= 7vl(4)= 9vl(3)= 6vl(2)= 6vl(1)= 0關(guān)鍵活動(dòng)有關(guān)的量 活動(dòng)a

11、i的最早開始時(shí)間e(i): 設(shè)活動(dòng)ai為有向邊，則 e(i) = ve(j)。 ve(j)是從源點(diǎn)v0到vj的最長(zhǎng)路徑長(zhǎng)度，決定了所有從vj開始的活動(dòng)的最早開始時(shí)間。 活動(dòng)ai的最遲開始時(shí)間 l(i): l(i) 是在不會(huì)引起工期延誤的前提下，該活動(dòng)允許的最遲開始時(shí)間。設(shè)活動(dòng)ai為有向邊, 則 l(i) = vl(k)-weight()。vl(9)= 19vl(8)= 15vl(7)= 17vl(6)= 11vl(5)= 7vl(4)= 9vl(3)= 6vl(2)= 6vl(1)= 0ve(1)=0ve(2)= 6ve(3)= 4ve(4)= 5ve(5)= 7ve(6)= 7ve(7)=

12、16ve(8)= 15ve(9)= 19436251978a1=6a9=8a8=9a7=2a4=1a5=1a3=5a2=4a10=4a12=4a11=2a6=1aie(i)l(i)li-ei 0 0 0 6 4 4 5 7 7 7 16 15 0 2 4 6 6 10 9 8 7 11 17 15 0 2 2 0 2 5 3 1 0 4 0 0 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 關(guān)鍵活動(dòng)： l(i) e(i) 表示活動(dòng)ak 是沒有時(shí)間余量的關(guān)鍵活動(dòng)。為找出關(guān)鍵活動(dòng), 需要求各個(gè)活動(dòng)的 e(i) 與 l(i)，以判別是否 l(i) e(i) 為求得e(

13、i) 與 l(i)，需要先求得從源點(diǎn)V0到各個(gè)頂點(diǎn)Vj 的 ve(j) 和 vl(j)。436251978a1=6a9=8a8=9a7=2a4=1a5=1a3=5a2=4a10=4a12=4a11=2匯點(diǎn)源點(diǎn)a6=1求關(guān)鍵活動(dòng)算法 對(duì)AOE網(wǎng)拓?fù)渑判?（若網(wǎng)中有回路，則終止算法） 按拓?fù)浯涡蚯蟪龈黜旤c(diǎn)事件的最早發(fā)生時(shí)間ve; 按拓?fù)湫蛄械哪嫘蚯蟾黜旤c(diǎn)事件的最遲發(fā)生時(shí)間vl; 根據(jù)ve和vl的值，求各活動(dòng)的最早開始時(shí)間e(i)與最遲開始時(shí)間l(i)，若e(i)=l(i)，則i是關(guān)鍵活動(dòng)。 例 求關(guān)鍵活動(dòng) 第1步ve(k) ve(k)ve(1)0 k=1maxve(j)+ weight() E(G

14、), k=2, 3, , n按拓?fù)湔蜻f推:436251978a1=6a9=8a8=9a7=2a4=1a5=1a3=5a2=4a10=4a12=4a11=2匯點(diǎn)源點(diǎn)a6=1ve(1)=0ve(2)= ve(1)+weight()=6ve(3)= ve(1)+weight()=4ve(4)= ve(1)+weight()=5ve(5)= maxve(2)+ weight()， ve(3)+ weight()=max6+1,4+1=7ve(6)= maxve(3)+ weight()， ve(4)+ weight()=max4+1,5+3=7ve(7)= ve(4)+weight()=7+9=16

15、ve(8)= maxve(4)+ weight()， ve(5)+ weight()=max7+8,7+4=15ve(9)= maxve(6)+ weight()， ve(7)+ weight()=max16+2,15+4=19436251978a1=6a9=8a8=9a7=2a4=1a5=1a3=5a2=4a10=4a12=4a11=2a6=1例 求關(guān)鍵活動(dòng) 第2步vl(k) vl(j)ve(n) j=nminvl(k)- weight() E(G), j= n-1, n-2,1按拓?fù)淠嫘蜻f推:436251978a1=6a9=8a8=9a7=2a4=1a5=1a3=5a2=4a10=4a12

16、=4a11=2匯點(diǎn)源點(diǎn)a6=1vl(9)= ve(9)=19vl(8)= vl(9)-weight()=15vl(7)= vl(9)-weight()=17vl(6)= vl(8)-weight()=11vl(5)= minvl(8)- weight()， vl(7)- weight() =min15-8,16-9=7vl(4)= vl(6)-weight()=11-2=9vl(3)= minvl(6)- weight()， vl(5)- weight() =min11-1,7-1=6vl(2)= vl(5)-weight()=7-1=6vl(1)= minvl(2)- weight()， v

17、l(3)- weight(), vl(4)- weight() = min6-6,6-4,9-5=0436251978a1=6a9=8a8=9a7=2a4=1a5=1a3=5a2=4a10=4a12=4a11=2a6=1例 求關(guān)鍵活動(dòng) 第3步e(i)=ve(j), l(i)=vl(k)-weight()aie(i)l(i)li-ei 0 0 0 6 4 4 5 7 7 7 16 15 0 2 4 6 6 10 9 8 7 11 17 15 0 2 2 0 2 5 3 1 0 4 0 0 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12436251978a1=6a9=

18、8a8=9a7=2a4=1a5=1a3=5a2=4a10=4a12=4a11=2匯點(diǎn)源點(diǎn)a6=1圖的關(guān)鍵路徑算法 算法CriticalPath ( )/* 圖的關(guān)鍵路徑算法 */CPath1計(jì)算事件的最早發(fā)生時(shí)間 for ( i = 1 ; i = n ; i + ) ve i = 0; for ( i = 2 ; i link) k =p - VerAdj ； if (vei + p - cost vek ) vek =vei + p - cost ; CPath2計(jì)算事件的最遲發(fā)生時(shí)間 for ( i = 1 ; i = 1 ; i - ) /*按拓?fù)淠嫘?/ for ( p = Head i . adjacent ; p ; p = p- link) k =p - VerAdj ； if (vlk p- cost cost ;CPath3求諸活動(dòng)的最早開始時(shí)間和最遲開始時(shí)間 fo