06-樹與流-xxxx-big(編輯修改稿)
2025-02-06 23:34 本頁面
【文章內(nèi)容簡介】 裁剪后呢？ 最優(yōu)解呢？ 仍然不是 最優(yōu)解。 該算法和 SPH都是近似解，誰 的 性能 更好？ 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 26 / 50 應用：負載 平衡的 路由 什么叫負載平衡的路由？ 盡量 讓各 鏈路上的資源 被平均 使用。 為什么需要負載平衡？ 用戶角度：盡量避免擁塞。 網(wǎng)絡(luò)角度：盡量減少投資浪費。 怎樣實現(xiàn)？ 路由時，盡量避免使用負載重的鏈路。 基于最 短路：按照 負載大小來決定邊的權(quán)重； 基于 最小生成樹：給定 s和 d，計算從 s到 d的 最小生成樹 （以負載 為權(quán)重）上的 路徑。 為什么用樹上路徑？ 因為樹上路徑是 最大負載最小 的路徑。 為什么?。? 割最優(yōu)條件。 a?e, 1 c?e, 1 b?e, 5 b a c d e 6 4 2 2 4 5 邊上數(shù)值代表帶寬 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 27 / 50 最小生成樹算法小結(jié) 最小生成樹 ? 兩個最優(yōu)條件和三個算法的關(guān)系。 ? 三個算法的設(shè)計思想。 ? 數(shù)據(jù)結(jié)構(gòu)的選擇技巧。 ? 與最小生成樹問題的關(guān)系。 ? SPH算法的設(shè)計思想。 Steiner樹 思考題 Prim算法和 SPH算法非常相似。 都 采用了貪婪 設(shè)計思想，為什么一 個 可以 得到 最優(yōu)解 ，而另一個卻不行 ？ 請 思考并體會 貪婪思想 的特點。 參考 Prim算法，可以設(shè)計出 SPH算 法 。 那么 參考 Kruskal算法，能否 也 設(shè)計 出一 個 Steiner樹的近似解法？ 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 28 / 50 樹與流 1 最小生成樹算法 關(guān)于流的算法都比較困難，屬于高級論題。這里僅介紹其中最容易理解的部分。 2 最大流算法 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 29 / 50 最大流算法 4 最大流問題 1 2 3 5 剩余網(wǎng)絡(luò) FordFulkerson算法 兩種增廣路徑算法 PreflowPush算法 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 最大流問題 30 / 50 Maximize v = Sj xsj Subject to Sj xij － Sk xki = 0 for each i ? s,t 0 ? xij ? uij for all (i,j) ? E. 最大流問題 符號說明 : 給定圖 G(V, E) xij : 邊 (i, j)上的流 uij : 邊 (i, j)上的容量 s : 源頂點 t : 宿頂點 要求最大化的是什么？ 第一個約束是什么？ 第二個約束是什么？ 流的大小。 流量守恒約束。 鏈路 /邊容量約束。 約束優(yōu)化 /數(shù)學規(guī)劃 目標函數(shù) 優(yōu)化 目標 約束 解變量 解 線性規(guī)劃 線性規(guī)劃 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 例子 31 / 50 s 1 2 t 10 , 8 8, 7 1, 1 10, 6 6, 5 可行解：滿足所有約束的解。 最優(yōu)解：滿足所有約束且使得目標函數(shù)達到最優(yōu)的解。 是最優(yōu)解么？ Maximize v = Sj xsj Subject to Sj xij － Sk xki = 0 for each i ? s,t 0 ? xij ? uij for all (i,j) ? E. 最大流問題 是可行解么？ 該例中最優(yōu)解是什么？ 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 32 / 50 最大流算法 4 最大流問題 1 2 3 5 剩余網(wǎng)絡(luò) FordFulkerson算法 兩種增廣路徑算法 PreflowPush算法 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 直覺 33 / 50 20 s a b t 20 10 30 20 10 0 雖然可用 線性規(guī)劃方法求解，但我們將主要就其物理 意義討論解法。 直覺： 我們找到 s到 t的路徑 p，看它能 運送 多少流到 t；然后一直這樣找下去 ， 直到 沒有 可以運送 流的路徑為止。 這樣能保證容量和流守恒約束么？ 是的。只要按照最小容量來決定 整 個路徑的 運送量就可以保證這兩 個 約束 。 也就是說 ，可以保證每次 得 到 的都是可行解。 0 0 0 0 20 20 找不到路了怎么辦？ 想象：從 b向 a“反向推送” 10個單位， 讓它 經(jīng) a直接到 t； 然后 從 s經(jīng) b到 t再運送 10個 單位 的流。流： 20?30 1010 10 改進的直覺 ： 允許“反向推送”；目的是可以“修正”以前的步驟中尋得的路徑。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 剩余網(wǎng)絡(luò) 34 / 50 找路的過程中，怎樣才能得到這樣的解？ 剩余網(wǎng)絡(luò)（ Residual Network）。 i j xij uij i j rij = uij – xij rji = xij rij: (i,j)的剩余容量 s a b t 20 10 30 20 10 20 0 0 0 0 0 a 20 20 20 20 10 20 10 10 1010 1020改進的直覺 ： 允許“反向推送”；目的是可以“修正”以前的步驟中尋得的路徑。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 35 / 50 最大流算法 4 最大流
教學課件相關(guān)推薦
鄂ICP備17016276號-1