AOVAOE網(wǎng)絡(luò)動態(tài)規(guī)劃算法.ppt

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