AOVAOE網絡動態(tài)規(guī)劃算法.ppt

AOV,AOE網絡, 動態(tài)規(guī)劃算法,2010/06/10,2,3,4,5,鄰接矩陣：,6,Prim算法：,7,通訊恢復問題，一些同學的思路：,某一條最小生成樹的邊被摧毀時，其他邊不會改變，此時只有vy沒有變到達，因此只要找到能夠達到vy的邊中，權值最小的一條來代替原來的邊。 將被摧毀線路置為MAX，做Prim，在結果中找出與原線路同起點及終點的線路，且線路中不含權為MAX的邊，則打印線路；否則打印“悲劇”。 用floyd算法，原圖生成shortpath結構體后，將vx,vy的shortpath參數改為無窮和不連接，從而在不改變原圖的條件下生成最短路徑，在打印出vx到vy的最短路徑。設全局變量length計算原最小生成樹的總路徑長度，減去去掉的邊，加上生成最短路徑的距離值，得到目前通訊線路的代價總和,8,Prim應用 00811124 吳小驥,我的思路：摧毀某條邊以后，剩下的邊再進行一次prim排序。 排序結果中唯一出現變動的就是我們所要的替代邊， 其余邊是不會變的（雖然在mst數組中的順序會變）。 為簡化顯示結果，把原先prim的中間步驟省去了，不打印出來 為了不直接改掉原來的矩陣，建一個新矩陣 建一個新的存放生成樹的數組 再次調用prim函數 倘若無法連通，最后得到的最小生成樹中必有MAX， 從這個就可以判斷是否能走通了,9,主要內容,拓撲排序 AOV網概念 AOE網與關鍵路徑,10,拓撲排序概念,對一個有向無環(huán)圖G進行拓撲排序，是指將G中所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若 E(G)，則u在線性序列中出現在v之前。 ABE CFGE ACFGBE CAFBGE,G,F,C,A,B,E,11,拓撲排序思想,（1）從AOV網中選擇一個入度為0的頂點將其輸出。 （2）在AOV網中刪除此頂點及其所有的出邊。 反復執(zhí)行以上兩步，直到所有頂點都已經輸出為止，此時整個拓撲排序完成；或者直到剩下的頂點的入度都不為0為止，此時說明AOV網中存在回路，拓撲排序無法再進行。,12,拓撲排序算法,拓撲排序前，先調用findInDegree得到所有結點的入度，然后將所有入度為0的頂點壓棧。 從棧頂取出一個頂點將其輸出，由它的出邊表可以得到以該頂點為起點的出邊，將這些邊終點的入度減1，即刪除這些邊。 如果某條邊終點的入度為0，則將該頂點入棧。 反復進行上述操作，直到棧為空。 如果這時輸出的頂點個數小于n，則說明該AOV網中存在回路，否則，拓撲排序正常結束。,13,采用鄰接出邊表表示： 增加一個indegree維度，存放各頂點的入度。,14,算法復雜度分析,n個頂點，e條邊 檢查每個頂點的度：O（n+e） 出棧-入棧-刪除邊： O（n+e）,15,AOV網,頂點活動網絡。每一個頂點代表一個活動。頂點之間的有向弧代表活動之間的序關系。,拓撲排序 無有向環(huán) 無死鎖,16,AOE網,如果在帶權的有向圖中，用頂點表示事件，用有向邊表示活動，邊上的權值表示活動的開銷，則此帶權的有向圖稱為邊活動網 (Activity on edge network) ，簡稱AOE網。 頂點表示一個事件。 頂點的入邊所表示該事件發(fā)生所需的的活動。只有所有活動（入邊）都完成了，該事件才能發(fā)生。 頂點的出邊所表示當該事件（頂點）發(fā)生后，后續(xù)的活動（出邊）都可以開展了。,17,AOE網,開工,動工,進材料 3天,打地基 40天,修圍墻 16天,拆遷 2年,蓋房子 120天,動工：進材料； 打地基；完成。蓋房子；可以開始。,18,AOE網,頂點：事件 邊： 活動 事件發(fā)生：之前的所有活動完成。 活動開始：起點事件必發(fā)生。 活動結束：終點事件不一定發(fā)生。,AOE網必須是可拓撲排序的。 一般是一個出發(fā)點頂點，一個終止頂點。,19,關鍵路徑,AOE網中有些活動可以并行進行，所以完成整個工程的最短時間是從開始頂點到完成頂點的最長路徑長度，路徑長度為路徑上各邊的權值之和。把開始頂點到完成頂點的最長路徑稱為關鍵路徑。,關鍵路徑是：1 - 4 - 3 - 2, 關鍵路徑長度為：2+7+6 = 15，,20,幾個相關的概念,ee(j)：事件vj 可能發(fā)生的最早時刻。它是從開始頂點v0到vj 的最長路徑長度。也代表了從vj出發(fā)的所有活動的最早開始時間。 le(i)：在保證不延誤整個工期的前提下，事件vi 允許發(fā)生的最晚時刻。 e(k)：活動ak = 的最早開始時間。 l(k)：活動ak = 的最晚開始時間。 源點：入度為0的頂點。 匯點：出度為零的頂點。,21,關鍵活動,關鍵活動就是e(k) = l(k)的活動。 l(k)e(k)表示完成活動ak的時間余量，是在不延誤工期的前提下，活動ak可以延遲的時間。 關鍵活動是：a2，a4，a5。,22,關鍵路徑算法,(1) 輸入e條弧，建立AOE網的存儲結構。 (2) 從源點v0出發(fā)，令ee(0)=0,求 ee(j) 1 的 最早開始時間e(k) = ee(i) 和 最晚開始時間l(k) = le(j) weight ()， 其中e(k)=l(k)的為關鍵活動。 求關鍵路徑是在拓撲排序的前提下進行的，不能進行拓撲排序，不能求關鍵路徑。,23,關鍵路徑算法,24,聲明四個數組,拓撲排序結果,25,最晚發(fā)生時間,26,例子：,27,算法分析：,設AOE網有n個頂點，e條邊，在求事件可能的最早發(fā)生時間及允許的最遲發(fā)生時間，以及活動的最早開始時間和最晚開始時間時，都要對圖中所有頂點及每個頂點邊表中所有的邊結點進行檢查，時間花費為O(n+e)，因此，求關鍵路徑算法的時間復雜度為O(n+e)。,28,AOE網研究的問題,完成整個工程至少需要多少時間 哪些活動是影響工程的關鍵 1956年，美國杜邦公司提出關鍵路徑法，并于1957年首先用于1000萬美圓化工廠建設，工期比原計劃縮短了4個月。