06-樹與流-xxxx-big-資料下載頁
2025-01-19 23:34本頁面
【正文】 rij。 END WHILE Shortest_Augmenting_Path( G(V,E), s, t ) 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 44 / 50 最大流算法 4 最大流問題 1 2 3 5 剩余網(wǎng)絡(luò) FordFulkerson算法 兩種增廣路徑算法 PreflowPush算法 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) PreflowPush算法原理 45 / 50 增廣路徑方法的缺陷：多條增廣路徑可能經(jīng)過同樣的鏈路，但卻必須分別進(jìn)行增廣操作。 10條。 每次增廣多少流量？ 有幾條增廣路徑？ 每次都會在前 8條邊上 重復(fù) 地 增廣 1個(gè)單位的流量。 能不能 一次性地 將流量增廣到節(jié)點(diǎn) 9，然后再從節(jié)點(diǎn) 9 繼續(xù)向后面的邊上增廣？ Preflowpush的思想。 PreflowPush的基本思想： 直至沒有 active節(jié)點(diǎn)為止。 首先將盡可能多的流從源節(jié)點(diǎn) “ push”到鄰接點(diǎn)去。 針對每個(gè) active節(jié)點(diǎn)，將多余的流量“ push”到其鄰接點(diǎn)去。 這樣豈不是會導(dǎo)致鄰接點(diǎn)流量不守恒？ 是的。節(jié)點(diǎn) i的多余量 excess定義為： ? ? ? ?? ? ? ?? ?: , : ,ji ijj j i A j i j Ae i x x??????若 e(i) 0，則節(jié)點(diǎn) i 稱為 active。 哪些“鄰接點(diǎn)”？ 如果 active節(jié)點(diǎn)沒有 admissible邊呢？ 顯然應(yīng)該是“離目的點(diǎn) 更近 的” 怎樣判定？ Distance Label 所有 Label較小的鄰接點(diǎn)么？ 不，為了有效利用剩余容量，只選擇 admissible邊：邊 i?j， d(i) ? d(j) = 1且 rij 0 假如一開始發(fā)出的流量大于實(shí)際的最大流，會發(fā)生什么？ 最終，多余流量會回到源點(diǎn)。 Relabel： d(i) = min{ d(j) + 1。 (i, j) ?A(i)且 rij 0 } 確保得到新的 admissible邊。 a t c d b 2 1 1 5 s 2 1 0 假如 rbt = 0? Relabel a t c d b 2 1?3 1 5 s 2 1 0 想象一個(gè)排水管道組成的網(wǎng)絡(luò)。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) PreflowPush算法實(shí)現(xiàn) 46 / 50 Preprocess。 WHILE 網(wǎng)絡(luò)中還有 active節(jié)點(diǎn) DO 選擇一個(gè) active節(jié)點(diǎn) i。 Pushandrelabel( i )。 END WHILE Preflowpush( G(V,E), s, t ) x : = 0。 計(jì)算距離標(biāo)記 d( i )。 xsj := usj for each arc (s, j) ? A(s)。 d(s) := N。 // N為節(jié)點(diǎn)數(shù)目 Preprocess IF 存在 admissible邊 (i, j) THEN ? := min{ e( i ), rij }； 從 i 向 j push ? 個(gè)單位的流； ELSE d(i) := min{ d(j) + 1: (i, j)? A(i) and rij 0} 。 Pushandrelabel( i ) 1 3 2 4 4 2 3 5 1 e(4)=0 rij e(1)=0 d(3)=1 d(1)=2 d(2)=1 d(4)=0 1 2 1 4 =4e(3)=4 e(2)=2 e(2)=1 =1=5=02)=2=1=0=6當(dāng)存在多個(gè) active節(jié)點(diǎn)時(shí)，應(yīng)該按照什么方式來選擇？ FIFO preflowpush算法 Highestlabel preflowpush算法 按照先入先出順序選擇 按照 Label大小選擇 研究性 Project No. R3 實(shí)現(xiàn)并 比較三種算法 的性能（速度 ） A) 最短增廣路徑； B) FIFO preflowpush； C) Highestlabel preflowpush。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 最大流算法應(yīng)用（一） 47 / 50 什么叫通信網(wǎng)絡(luò)的可靠性？ 我們這里定義為任意兩個(gè)頂點(diǎn) 間鏈路 分離的路徑的數(shù)目。 這跟最大流有啥關(guān)系？ 若邊 的容量都設(shè)為 1，流也 必須是 整數(shù)。求得的最大 流值是什么？ 就是可靠性。 應(yīng)用之一： 通信網(wǎng)絡(luò)的可靠性 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 最大流算法應(yīng)用（二） 48 / 50 什么叫通信網(wǎng)絡(luò)的關(guān)鍵鏈路？ 如何確定兩個(gè)頂點(diǎn)之間的最小割？ 如果 e1同時(shí)包含在 (a,b)之間和 (c,d)之間 的最小 割中；而 e2只 包含 在 (c,d)之間的 最小割 中，那么 e1的關(guān)鍵性大于 e2。 最短增廣路徑算法終止時(shí)，頂點(diǎn)被劃分 為兩 個(gè)部分 S和 T。從 S到 T 的 邊組成最小割。 應(yīng)用之二： 最小干擾路由 什么 叫最小干擾路由？ 減少阻塞的一種路由方法?；舅枷耄阂枣溌逢P(guān)鍵度作為權(quán)重， 求解最小權(quán)重路徑。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 49 / 50 最大流算法小結(jié) FordFulkerson 算法 Capacity Scaling 算法 最短增廣路徑 算法 問題定義 剩余網(wǎng)絡(luò) 最大流最小割定理 PreflowPush 算法 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) And the journey… 演講完畢，謝謝觀看！
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1