文章目錄
- 有向無環圖
- 拓撲排序
- AOV-網
- AOE-網
- 關鍵路徑的概念
- 事件的最早/晚開始時間
- 事件和活動的區分
- 活動的最早/晚開始時間
有向無環圖
拓撲排序
AOV-網
由于有向無環圖可以用一種自然的方式對優先關系或依賴關系進行描述，因此在工程計劃與管理方面有廣泛而重要的應用，一個大的工程往往可以分解為若干相對獨立的子工程（活動），子工程之間在進行的時間上有一定的相互制約關系，將這些子工程之間的先后關系用有向圖表示，其中頂點表示活動，有向邊表示活動之間的優先制約關系，稱這種有向圖為頂點表示活動的網，簡稱AOV網，
AOE-網
表示一個實際工程計劃的AOE網應當是無環且存在唯一的源點和匯點的，如果途中存在多個入度為0的頂點，那么可以添加一個虛擬源點，使這個虛擬源點到原來各個入度為0的頂點都有一條權值為0的邊，對多個出度為0的頂點的情況可做類似的處理，
（這里其實不是很懂）
關鍵路徑的概念
在AOE網中有些活動可以并行地進行，因此，完成整個工程的最短時間應該是從源點到匯點的最長路徑的長度（路徑長度等于路徑上各邊權值之和），
需要注意的是：AOE網中可能有不止一條的關鍵路徑，
分析關鍵路徑的目的是找出關鍵活動，即不按期完成就會影響整個工程的完成時間的活動，從而為決策者提供調度依據，應當投入較多的人力和物力在關鍵活動上，以保證整個工程按期完成，并可爭取提前完成，
由于關鍵路徑由關鍵活動組成，因此只要找出AOE網中的關鍵活動，就可以找到關鍵路徑，
（這里看不懂可以看下面）
事件是有向圖中的頂點，活動的最早開始時間和最晚開始時間可以直接由事件的最早開始時間和最晚開始時間求得，因此，演算法的核心在于求事件的最早開始事件和最晚開始時間，
由活動和事件的關系可知：求解程序有正推和反推兩個程序：先正推，才能找到耗時最長的路徑；再反推，就可找出關鍵活動（即l(ai)=e(ai)的活動）；由關鍵活動就找到了關鍵路徑
求解步驟：
- 求拓撲排序
- 從始點v0出發，令ve[0]=0，按拓撲有序求ve[j]（對j來說，取所有進來的邊的最大值：ve(j)=Max{ve(i)+dut(<i,j>)}）
- 從終點vn-1出發，令vl[n-1]=ve[n-1]，按逆拓撲有序求vl[i]（對j來說，取所有出去的邊的最小值：vl(i)=Min{vl(j)-dut(<i,j>)}）
- 根據各頂點的ve和vl值，求每潭訓(活動)aj的最早開始時間e[aj]和最遲開始時間l[aj]，e(aj)=ve(j); l(aj)=vl(k)-dut(<j,k>) j—aj-?k
- 如果e[aj]=l[aj]，則ai為關鍵活動
事件的最早/晚開始時間
好了看到這里你會說這說的什么玩意 ， 下面我用人話解釋一下：
事件（頂點）的最早開始時間：
某個頂點的最早開始時間就是指這個工程最早什么時候能開工？也就是所有的前置工程什么時候完成了，就可以開工了，也就是所有前置工程的最早的開工時間，再加上那個工程所需的時間中，最大的值，（這樣才能保證所有前置工程都開工了，）
選取所有前置工程的最早開始時間加上工程時間的最大值，這就是最早開始時間，
事件（頂點）的最晚開始時間：
比如我不想那么早開干，能拖一天是一天 ，但是要保證不會影響后面的工程，那么此時就是找到后一個工程的最晚開始時間，（也就是后一個懶狗 ），意思就是我再懶再拖，也不能影響我后面的懶狗導致他不能及時開工，
比如同學A交給我一個任務，我做完后要交給他繼續完成，他最晚5號要開始做，那我要做兩天的話，那我最晚3號就要交給他，
多人運動的情況就是：
比如同學AB交給我一個任務，我做完后要交給他們繼續完成，同學A最晚5號要開始做，那我要做兩天的話，那我最晚3號就要交給他，但是同學B最晚4號要開始做，那我只能2號就開始做了，
所以選取所有后置工程的最晚開始時間減去工程時間的最小值就是我的最晚開始時間了，
事實上當一個頂點連了多個邊的時候，當到達了最晚開始時間，事實上這個頂點所指向的所有邊中，可能并不是所有邊都必須得立馬開工的，有些邊也還是可以繼續偷懶的，只要讓最緊迫的那個邊開工就行了，其他的邊是存在冗余時間的，
而最晚開始時間減去最早開始時間等于冗余時間，
但是需要注意一點，初始的頂點和最后一個頂點，由于大家所有人都希望工程盡早完工，所以不會給最開始的點和最后的點偷懶的機會，也就意味著沒有冗余時間，（最前面和最后面的頂點注定做不了懶狗 ）
所以最早的頂點和最晚的頂點他們的最晚開始時間只能等于最早開始時間，
事件和活動的區分
這里要注意區分上面和下面的情況：
一個頂點是一個事件，一條邊是一個活動，或者可以這么說，這樣可能更好理解，在游戲里，一個公會有很多玩家，一個公會達成一個稱號，或者取得某個成就，或者建房子（也就是事件），他需要各個玩家去做事才能完成，當A玩家和B玩家都達成了“取得排名第一”的成就時，公會就達成了“有兩個玩家達成第一”的成就，
所以事件和活動是這樣的一個關系，
一個事件需要一些活動來作為前置，那些活動完成之后，事件（成就）才可以達成，而達成了這個成就后，就可以再安排公會里的其他成員去做其他事情來達成新的成就，
因此一個事件連著多個活動，有前置活動和后置活動，而一個活動只連接了兩個頂點，
由于一個頂點（一個成就）涉及到多個活動（各個玩家的努力），因此需要在多個活動直接選擇最值，
但是活動只涉及到兩個頂點的事，不需要考慮最值，
活動的最早/晚開始時間
活動（邊）的最早開始時間：
一個事件什么時候可以開始，或者說一個成就什么時候達成之后，就可以開始做“因為有了這個成就就可以做新的事”這樣的事情了，
所以活動的最早開始事件等于事件的最早開始時間，意思就是某個成就達成后就可以做新的活動了，
活動（邊）的最晚開始時間：
這里需要注意，一個活動（邊）的最晚開始時間并不是頂點的最晚開始時間，這是因為一個頂點需要考慮多個活動，讓多個活動都不能延誤，因此頂點需要在所有活動的最晚開始時間中選擇最早的那個，而一個活動只需要考慮本身就行了，
因此活動的最晚開始時間等于其所指向的那個點的最晚時間減去工程的長度，
然后我們找到冗余時間為零的點連起來即為關鍵路徑：
其次要注意：
若AOE網中有多條關鍵路徑，那么僅提高一條關鍵路徑上的關鍵活動的速度并不能導致整個工程縮短工期，而必須提高同時在幾條關鍵路徑上的關鍵活動的速度才能有效
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/247725.html
標籤：其他
上一篇：LeetCode刷題——跳躍游戲#55#Medium
下一篇：35歲的程式員：第10章，排行榜