AOV網的定義
以頂點表示活動,以有向邊表示活動之間的優先關系的有向圖稱為頂點表示活動的網(Activity On Vertex Network),簡稱AOV網,如下:
在AOV網中,若頂點i到頂點j之間有路徑,則稱頂點i為頂點j的前驅,頂點j為頂點i的後繼;
若頂點i到頂點j之間為一條有向邊,則稱頂點i為頂點j的直接前驅,頂點j為頂點i的直接後繼
在AOV網中,最重要的兩個知識點就是拓撲排序和關鍵路徑,其中拓撲排序用于判斷AOV網中是否存在回路,有回路則活動永遠也結束不了,關鍵路徑可以得出關鍵活動以及完成整個活動的最短時間,下面分别介紹這兩個知識點。
拓撲排序
檢測工程能否正常進行,首先要判斷對應的AOV網中是否存在回路,達到該目的最有效的方法之一是對AOV網構造其頂點的拓撲序列,即對AOV網進行拓撲排序
什麼是拓撲排序?
拓撲排序在離散數學中的定義如下:
由某個集合上的一個偏序得到該集合上的一個全序的操作稱為拓撲排序;
是不是有些難以了解?忽略上述定義,看如下更易懂的定義:
構造AOV網的一個頂點序列,使得該頂點序列滿足下列條件:
1、若在AOV網中,頂點i 優先于頂點j,則在該序列中頂點i 仍然優先于頂點j;
2、若在AOV網中,頂點i 與頂點j之間不存在優先關系,則在該序列中建立它們的優先關系,即頂點i優先于頂點j,或者頂點j 優先于頂點i;
3、若能構造出這樣的拓撲序列,則拓撲序列包含AOV網的全部頂點,說明AOV網中沒有回路;若構造不出這樣的序列,說明AOV網中存在回路
拓撲排序的核心思想
拓撲排序的核心思想如下:
1、 從AOV網中任意選擇一個沒有前驅的頂點;
2、 從AOV網中去掉該頂點以及以該頂點為出發點的所有邊;
3、 重複上述過程,直到AOV網中的所有頂點都被去掉(AOV網中無回路),或者AOV網中還有頂點,但不存在入度為0 的頂點(AOV網中存在回路)。
上述方法的圖示如下:
注:拓撲序列不一定唯一;
用堆棧實作拓撲排序算法
AOV圖采用鄰接表存儲方式,使用堆棧實作拓撲排序的算法步驟如下:
1、首先建立一個入度為0的頂點堆棧,将網中所有入度為0的頂點分别進棧;
2、當堆棧不空時,反複執行以下動作:
2.1、從頂點棧中退出一個頂點,并輸出它;
2.2、從AOV網中删去該頂點以及以它發出的所有邊,并分别将這些邊的終點的入度減1;
2.3、若此時邊的終點的入度為0,則将該終點進棧;
3、若輸出的頂點個數少于AOV網中的頂點個數,則報告網中存在回路,否則,說明該網中不存在回路;
Q:除了進行拓撲排序,還可以采用什麼方法判斷一個有向圖是否存在回路?
A:還可以對AOV網圖進行深度優先周遊。若從某個頂點v出發,周遊結束前出現了從頂點u到頂點v的回邊,則可以斷定圖中包含頂點v到頂點u的回路。(廣度優先不可以)
AOE網的定義
AOE(Activity On Edge)網為一個帶權的有向無環圖,其中,以頂點表示 事件,有向邊表示 活動 ,邊上的權值表示活動持續的時間 ,如下圖:
1、正常情況下,AOE網中隻有一個入度為0的頂點,稱之為 源點;有一個出度為0 的頂點,稱之為 終點;
2、隻有在某個頂點所代表的事件發生以後,該頂點引發的活動才能開始;
3、進入某事件的所有邊代表的活動都已完成,該頂點代表的事件才能發生;
關鍵路徑
關鍵路徑的定義和特點
從源點到終點的路徑中具有最大長度的路徑為關鍵路徑;關鍵路徑上的活動稱為關鍵活動。
關鍵路徑的特點:
1、關鍵路徑的長度(路徑上的邊的權值之和)為完成整個工程所需要的最短時間;
2、關鍵路徑的長度變化(即任意關鍵活動的權值變化)将影響整個工程的進度,而其他非關鍵活動在一定範圍内的變化不會影響工期;
關鍵路徑算法
核心思想:
1、e[i] — 活動ai的最早開始時間;
2、l[i] — 活動ai的最晚開始時間;
若l[i]–e[i]=0,則說明活動ai為一個關鍵活動;所有的關鍵活動連接配接起來即為關鍵路徑;
注:活動指的是AOE網絡中的邊;事件指的是AOE網絡中的結點;
對于事件和活動,有如下結論:
事件k的最早發生時間ee[k] = 活動的ai最早開始時間e[i];
事件k的最晚發生時間le[k] = 活動的ai最晚開始時間l[i];
求關鍵路徑的步驟
AOE圖使用鄰接矩陣的存儲方式
求關鍵路徑的步驟如下:
1、計算事件k的最早發生時間ee[k]
事件k的最早發生時間決定了由事件k出發的所有活動的最早開始時間;該時間是指從源點到頂點(事件)k的最大路徑長度,計算方法如下圖:
樣例如下:
2、計算事件k的最晚發生時間le[k]
所謂事件k的最晚發生時間是指不影響整個工期的前提下事件k必須發生的最晚時間,它必須保證從事件k發出的所有活動的終點事件的最遲發生時間,該過程是一個從終點到源點的反推計算過程,計算方法如下:
樣例如下:
3、計算活動 i 的最早開始時間e[i]
所謂活動i的最早開始時間實際上是事件k發生的最早時間,即隻有事件k發生,活動i才能開始,計算方法如下:
樣例如下:
4、計算活動 i 的最晚開始時間l[i]
所謂活動i的最晚開始時間是指不推遲整個工期的前提下活動i開始的最晚時間,計算方法如下:
樣例如下:
5、求出關鍵活動與關鍵路徑