06-樹(shù)與流-xxxx-big(已改無(wú)錯(cuò)字)
2023-02-07 23:34:58 本頁(yè)面
【正文】 問(wèn)題 1 2 3 5 剩余網(wǎng)絡(luò) FordFulkerson算法 兩種增廣路徑算法 PreflowPush算法 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) FordFulkerson算法 36 / 50 x := 0。 構(gòu)建剩余網(wǎng)絡(luò) G(x)。 WHILE G(x)中存在 s 到 t 的路徑 p DO 確定 p的增廣容量 d*。 沿著路徑 p輸送 d* 單位的流 。 更新圖中各邊上的剩余容量 rij。 ENDWHILE FordFulkerson( G(V,E), s, t ) 增廣路徑 即增廣路徑上各邊上 剩余 容量 rij 的最小值。 算法何時(shí)終止？ 剩余網(wǎng)絡(luò)中不 存在 增廣 路徑了。 s 1 2 t 1 8 1 7 6 9 3 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 最大流最小割 37 / 50 剩余網(wǎng)絡(luò)中沒(méi)有增廣路徑 意味著什么？ s 1 2 t 1 8 1 7 6 9 3 s 1 2 t 10 , 9 8, 8 1, 1 10, 7 6, 6 s 原圖中的某個(gè) st 割的容量被用光了。 哪個(gè)割？ 最大流最小割定理 最大流的值等于最小割的容量。 最大流判定條件 下面三個(gè)陳述等價(jià)： 1）流 x為最大流； 2） G(x)中不存在增廣路徑了。 3）存在一個(gè)割，其容量等于流 x的值。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 增廣路徑的選擇問(wèn)題 38 / 50 FordFulkerson算法的性能怎么樣？ 如果容量的取值是 整數(shù)或有理數(shù) ，該算法 不僅 一定在有限步驟內(nèi)終止 ， 而且 終止時(shí) 得到 的一定是最大流。這種情況下，算法復(fù)雜度為 O(nmU)。 但是：即使是整數(shù) /有理數(shù) 取值 ，如果選擇 增廣路徑 的 方法不得當(dāng)，算法的 性 能 也會(huì)很差。 如果容量的取值不做限制，該算法 既不能保證 在有限步驟內(nèi)終止， 也 不能 保證 終止時(shí) 得到 的是最大流。 s 1 2 t M M M M 1 M – 1 1 M – 1 1 M – 1 1 M – 1 1 2M次增廣之后 如果選擇得好呢？ 只需要兩次增廣。 最大容量增廣路徑 那么，怎樣選擇增廣路徑？ 最短增廣路徑 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 39 / 50 最大流算法 4 最大流問(wèn)題 1 2 3 5 剩余網(wǎng)絡(luò) FordFulkerson算法 兩種增廣路徑算法 PreflowPush算法 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) Δ剩余網(wǎng)絡(luò) 40 / 50 每次都選擇最大容量的路徑進(jìn)行增廣，可以大大減少迭代次數(shù)。 但是：求給定圖中的最大容量路徑并不容易。 那怎么辦？ 選擇容量“足夠大”的路徑來(lái)增廣。 什么意思？ 每次設(shè)一個(gè)門(mén)限 Δ，刪除所有容量小于 Δ的邊 。 稱為 Δ剩余網(wǎng)絡(luò) ， G(x, Δ)。 1 2 3 4 5 10 13 7 12 4 15 6 8 1 2 3 4 5 10 13 12 15 8 G(x) G(x, Δ) Δ = 8 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) Capacity Scaling算法 41 / 50 x := 0。 Δ=2?logU?。 WHILE Δ?1 DO WHILE G(x, Δ)中存在增廣路徑 p DO 確定 p的增廣容量 d*。 沿著路徑 p輸送 d* 單位的流 。 更新圖 G(x, Δ)中各邊上的 rij。 END WHILE Δ = Δ/ 2。 END WHILE Capacity_Scaling( G(V,E), s, t ) O(m2logU) 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 最短增廣路徑算法 42 / 50 什么叫做“最短”？ 跳數(shù)最小。 最短增廣路徑算法 ：每次 都選擇最小跳數(shù)的路徑進(jìn)行增廣。 怎么求 G(x)中的最小跳數(shù)路徑？ 設(shè)每條邊的權(quán)重為 1，然后 調(diào)用 Dijkstra算法。 Better：用廣度優(yōu)先搜索。 Why is BFS better？ 因?yàn)?BFS更快。 為什么 BFS更快？ 因?yàn)?BFS不用 FindMin。 也稱為 EdmondKarp算法 。其 復(fù)雜度為 O(nm2)。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 算法偽碼 43 / 50 d(t) = TRUE。 WHILE d(t) DO FOR 所有頂點(diǎn) j， DO d(j) = FALSE。 p(j) = NULL。 d(s) = TRUE。 LIST = {s}。 WHILE LIST非空 并且 d(t)==FALSE DO 從 LIST中取出第一個(gè)頂點(diǎn) i； FOR 所有 i 的關(guān)聯(lián)邊 e(i,j) DO IF rij 0 且 d(j)==FALSE THEN p(j) = i。 d(j) = TRUE。 LIST = LIST U {j}。 END WHILE IF d(t) THEN 確定 s到 t的增廣路徑 p； 確定 p的增廣容量 d*。 沿著路徑 p輸送 d* 單位的流 。 更新 圖 G(x)中各邊上的
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1