Activity Networks AOV網路 AOE網路.

Presentation on theme: "Activity Networks AOV網路 AOE網路."— Presentation transcript:

1 Activity Networks AOV網路 AOE網路

2 AOV網路 (Activity on Vertx Networks)
為了表示一件工作中，各子工程間的先後關係，我們可以利用有向圖中的有向邊代表事情進行的順序，位於一條有向邊終點的事件必須要等待起點的事情完成後，才可以進行。 以頂點表示工作項目、以有向邊表示工作進行順序的圖形被稱為頂點工作網路(Activity on Vertx Networks)，簡稱AOV網路。

3 在AOV網路中，如果不存在迴路，則所有的事件可以排成一個線性序列，使得每個事件的所有先驅事件都排在該事件之前，這種序列稱之為「拓撲序列」。
如果網路中有迴路，則會造成死結(deadlock)現象。 在AOV網路中，如果不存在迴路，則所有的事件可以排成一個線性序列，使得每個事件的所有先驅事件都排在該事件之前，這種序列稱之為「拓撲序列」。

4 AOV網路

5 拓撲排序 (Topology Sort)

6 定義 假設G=(V，E)中， 對任何(Vi ， Vj)為G的有向邊， 也就是存在一條有向路徑從Vi到Vj，
這種走訪順序為拓撲排序。 其中每一個頂點都可視為一個事件， Vi就稱為Vj的先驅事件， Vj則稱為Vi的後繼事件。

7 演算法則 要建立拓撲序列，主要是重複下列兩大步驟，直到找不到入分支度為0的頂點為止： 選擇一個入分支度為０的頂點輸出
從網路中刪除該點的所有出邊

8 由圖中頂點C1、C2的入邊數皆為0，所以這二個頂點都可以輸出，假設選擇頂點C1，則輸出C1，並從網路中刪除邊(C1,C3)；
再由頂點C3、C4中，選擇頂點C3，並刪除邊(C3,C4)、(C3,C6)、(C3,C7)； 再依次輸出點C4、C5、C6、C7。 最後得到拓撲序列： C1→C2→C3→C4→C5→C6→C7

9 演算法 ＝＞圖解演算法 F =1；S = {1}，V=｛0, 1, 2, 3, 4｝ 1 2 3 4 50 20 ∞ 75

10 1 2 3 4 45 20 30 75 由陣列D中可看出D(2) = 20最少，因此將頂點2加入到S集合中： S = {1, 2 }
V – S = {1, 3, 4} 頂點2的相鄰頂點有1和3，則 D [3] = min(D[3], D[2] +A [2,3] ) = min (∞, 20+10)=30 D [1] = min(D[1], D[2] +A [2,1] ) = min (50, 20+25)=45 此時D陣列變成 1 2 3 4 45 20 30 75

11 1 2 3 4 40 20 30 65 從V – S = {1, 3, 4 }找出D陣列的最小值是D[3] =30， 而頂點的相鄰點為1，4
S = {0, 2, 3}，V – S = {1, 4} D [1] = min(D[1], D[3] +A [3,1] ) = min (45, 30+10)=40 D [4] = min(D[4], D[3] +A [3,4] ) = min (75, 30+35)=65 此時D陣列變成 1 2 3 4 40 20 30 65

12 1 2 3 4 40 20 30 50 從V – S = {1, 4 }找出D陣列的最小值是D[1] =40， 而頂點的相鄰點為4
S = {0, 1, 2, 3}，V – S = {4} D [4] = min(D[4], D[1] +A [1,4] ) = min (65, 40+10)=50 繼續將頂點4加入S中，則 S = {0, 1, 2, 3, 4}，V – S = {Φ} 此時已完成城市0至其他城市的最短距離。 而D陣列則變成 1 2 3 4 40 20 30 50

13 ＝＞演算虛擬碼 for ( i = 0; i < n; I ++) {
if every vertex has a predecessor fprintf(stderr, “Network has a cycle, \n”) ; exit (1) ; } else pick a vertex v that has no predecessors; output v ; delete v and all edages leading out of v from the network ;

14 ＝＞演算程式碼 void topological ( int count [ ], int vertex, int link [ ], int n) { int top = 0, i , j , k ; for ( i = 1 ; i <= n ; i ++ ) if ( count [i] = = 0 ) count [i] = top ; top = i ; }

15 for ( i = 1 ; i <= n ; i ++) { if ( top = = 0 ) printf ( “network has a cycle” ); break ; } j = top ; top = count [top] ; printf ( “%d” , j ) ; ptr = link [j] ;

16 while ( ptr != 0) { k = vertex [ptr] ; count [k] = count [k] – 1; if ( count [k] = = 0 ) count [k] = top ; top = k ; } ptr = link [ptr] ;

17 範例 假設AOV網路如圖所示，其拓樸排序過程如下：

18 輸出V1，並刪除(V1，V2)與(V1，V6)兩個邊。
此時V2和V6皆沒有前行者，若輸出V2則刪除(V2，V3)與(V2，V4)兩個邊。

19 選擇輸出V6，並刪除(V6，V4)與(V6，V5)兩個邊。

20 (Activity on Edge Networks)
AOE網路 (Activity on Edge Networks)

21 AOV網路

22 相關的名詞

23 最早開始／最脕開始時間 在AOE網路上所有的活動皆有的時間， 最晚開始時間指一活動在不影響整個計畫完成之下，最晚能夠開始進行的時間。

24 臨界路徑 一個計畫所需完成的最短時間，是從起始點到結束點間最長的路徑來算；而長度最長的路徑為臨界路徑(Critical Path)
AOE網路上的活動是可以並行處理的 臨界路徑(Critical Path)可能不止一條 臨界活動分析的目的 辨別那些路徑是臨界路徑(Critical Path)，以便能夠集中資源在這些臨界活動上，進而縮短計畫完成的時間。 AOE網路的應用 即是在求得其臨界路徑，進而達到控制或評估專案績效的目的。

25 計算最早開始時間ES (j) 每個活動j的最早開始時間，計算公式如下：
ES(j) = max { ES(j) , ES(i) + ( i , j )時間 } 其中i  p ( j )，而p( j )是所有與j相鄰頂點所成的集合。 再利用拓樸排序，每當輸出一個活動時，就修正此活動到各活動之最早開始時間。 如果拓樸排序輸出是活動j，而活動j指向活動k，此時的 ES(k) = max { ES(k) , ES(j) + ( j, k)時間 }

26 現在以下圖的AOE網路為例，假設ES(i) = 0，1≦i≦7，如下所示：
2 3 4 5 6 7 開始

27 由於1沒有前行者，故輸出V1計算V1相鄰頂點V2,V3,V5的ES：
ES(2) = max { ES(2), ES(1) +( 1, 2 ) }=max( 0, 0+3 ) ＝ 3 ES(3) = max { ES(3), ES(1) +( 1, 3 ) }=max( 0, 0+3 ) ＝ 3 ES(5) = max { ES(5), ES(1) +( 1, 5 ) }=max( 0, 0+4 ) ＝ 4 ES 1 2 3 4 5 6 7

28 ES 1 2 3 4 5 6 7 ES 1 2 3 4 5 6 7 V3亦無前行者，故計算其與相鄰的頂點V４, V5的ES：
ES(4) = max { ES(4), ES(3) +( 3, 4 ) }=max( 0, 3+3 ) ＝ 6 ES(5) = max { ES(5), ES(3) +( 3, 5 ) }=max( 0, 3+2 ) ＝ 5 ES 1 2 3 4 5 6 7 V2亦無前行者，故計算其與相鄰的頂點V４的ES： ES(4) = max { ES(4), ES(2) +( 2, 4 ) }=max( 6, 3+1 ) ＝ 6 ES 1 2 3 4 5 6 7

29 V4無前行者，故計算其與相鄰的頂點V5，V6，V7的ES：
ES(5) = max { ES(5), ES(4) +( 4, 5 ) }=max( 5, 6+0 ) ＝ 6 ES(6) = max { ES(6), ES(4) +( 4, 6 ) }=max( 0, 6+3 ) ＝ 9 ES(7) = max { ES(7), ES(4) +( 4, 7 ) }=max( 0, 6+9 ) ＝ 15 ES 1 2 3 4 5 6 7 9 15 V6無前行者，故計算其與相鄰的頂點V7的ES： ES(7) = max { ES(7), ES(6) +( 6, 7 ) }=max( 5, 6+9 ) ＝ 15 ES 1 2 3 4 5 6 7 9 15

30 ES 1 2 3 4 5 6 7 9 15 V5無前行者，故計算其與相鄰的頂點V7的ES： ES(7) = max { ES(7),
9 15

31 最後輸出V7。

32 計算最晚開始時間LS (j) 每個活動j的最晚開始時間，計算公式如下：
LS(j) = min { LS(j) , LS(i) - ( i , j )時間 } 其中i  s( j )，而s( j )是所有與j相鄰頂點所成的集合。 再利用拓樸排序，每當輸出一個活動時，就修正此活動到各活動之最晚開始時間。 如果拓樸排序輸出是活動j，而活動j指向活動k，此時的 LS(k) = min { LS(k) , LS(j) - ( j, k)時間 }

33 同樣以前圖的AOE網路為例，假設LS (i) = 15，1≦i≦7，如下所示：
2 3 4 5 6 7 開始 15

34 求得臨界路徑 當下列三個條件成立時，便可求出二頂點Vi與 Vj 間的路徑是否為臨界路徑： (1) ES( i ) = LS( i ) (2) ES( j ) = LS( j ) (3) ES( j ) – ES(i) = LS( j ) – LS( i ) = a ij