有向無環圖：無環的有向圖，簡稱DAG圖(Directed Acycline Graph)

有向無環圖常用來描述一個工程或系統的進行過程。（通常吧計劃、施工、生產、程序流程等當成是一個工程）
一個工程可以分為若干個 子工程，只要完成了這些子工程（活動），就可以導致整個工程的完成

AOE網：關鍵路徑

• 用一個有向圖表示一個工程的各子工程及其相互制約的關系，以弧表示活動，以頂點表示活動的開始或結束事件，稱這種有向圖為邊表示活動的網，簡稱為AOE網（Activity On Edge）
• 把工程計劃表示為邊表示活動的網絡，即AOE網，用頂點表示事件，弧表示活動，弧的權表示活動持續時間。事件表示在它之前的活動已經完成，在它之后的活動可以開始
• 例：準備一個小型家庭宴會，晚6點開始最遲幾點開始準備？壓縮哪項活動時間可以使總時間減少？
  
  事件v1————表示整個工程開始（源點：入度為0的頂點）
  事件v7————表示整個工程結束（匯點：出度為0的頂點）

對于AOE網，我們關心連個問題：

完成整項工程至少需要多少時間？

哪些活動是影響工程進度的關鍵

關鍵路徑——路徑長度最長的路徑
路徑長度——路徑上各活動持續時間之和

確定關鍵路徑，需要定義4個描述量：

ve(vj)——表示事件vj的最早發生時間
例：ve(v1) = 0 ve(v2) = 30
vl(vj)——表示事件vj的最遲發生時間
例：ve(v4) = 165
e(i)——表示活動ai的最早開始時間
例：e(a3) = 30
l(i)———表示活動ai的最遲開始時間
例：l(a3) = 120
l(i) - e(i)——表示完成活動ai的時間余量。例：l(3) - e(3) = 90
關鍵活動——關鍵路徑上的活動，即l(i)-e(i)==0的活動

如何找l(i)-e(i)==0的關鍵活動？

設活動ai用弧<j, k>表示，其持續時間記為：Wj,k
則有：
(1) e(i) = ve(j)
(2) l(u) = vl(k)-Wj,k
如何求ve(j)和vl(j)?
（1）從ve(1)=0開始向前遞推，ve(j) = Max{ve(i) + Wi,j}, <i,j>∈T， 2 ≤ j ≤ n，其中T是所有以j為頭的弧的集合。
（2）從vl(i)=Min{vl(j) - Wi,j}, <i,j> ∈ S，1 ≤ i ≤ n-1，其中S是所有以i為尾的弧的集合。

總結

以上是生活随笔為你收集整理的有向无环图——AOE网(关键路径)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。