圖與網(wǎng)路分析報(bào)告探討(編輯修改稿)
2025-02-03 08:00 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 的 容量 為其最大通過(guò)能力，記為 cij ，支路上的實(shí)際 流量 記為 fij ? 圖中規(guī)定一個(gè)發(fā)點(diǎn) s，一個(gè)收點(diǎn) t ? 節(jié)點(diǎn)沒(méi)有容量限制，流在節(jié)點(diǎn)不會(huì)存儲(chǔ) ? 容量限制條件 ： 0? fij ? cij ? 平衡條件 ： ??????????? ????tifvtsisifvffijij vBvjivAvij)(,0)()()(? 滿足上述條件的網(wǎng)路流稱為 可行流 ，總存在 最大可行流 ? 當(dāng)支路上 fij = cij ，稱為 飽和弧 ? 最大流問(wèn)題也是一個(gè)線性規(guī)劃問(wèn)題 vi A(vi) B(vi) 20 截集與截集容量 定義 ：把網(wǎng)路分割為兩個(gè)成分的弧的最小集合，其中一 個(gè)成分包含 s 點(diǎn)，另一個(gè)包含 t 點(diǎn) 。 ? 一般包含 s 點(diǎn)的成分中的節(jié)點(diǎn)集合用 V表示，包含 t 點(diǎn)的成分中的節(jié)點(diǎn)集合用 V表示 ? 截集容量 是指截集中正向弧的容量之和 ????VjVi ijcVVC ),(? 福特 富克森定理 ：網(wǎng)路的最大流等于最小截集容量 s t5342(4 ,0 )(3 ,0 )(2 ,0 )(1 ,0 )(1 ,0 )(5 ,0 )(3 ,0 )(2 ,0 )(5 ,0 )21 確定網(wǎng)路最大流的標(biāo)號(hào)法 ? 從任一個(gè)初始可行流出發(fā)，如 0 流 ? 基本算法：找一條從 s 到 t 點(diǎn)的 增廣鏈 (augmenting path) ? 若在當(dāng)前可行流下找不到增廣鏈，則已得到最大流 ? 增廣鏈中與 s 到 t 方向一致的弧稱為 前向弧 ，反之 后向弧 ? 增廣過(guò)程：前向弧 f?ij=fij +q , 后向弧 f?ij=fij ?q ? 增廣后仍是可行流 s t5432(3,0) (5,3)(1,1)(5,1) (1,1)qs2= 4 q5t= 2q45= 3q43= 1q32= 1增廣量 q = m in qij= m in (4,1,1,3 ,2 ) = 1s t5432(3,1) (5,4)(1,0)(5,2) (1,0)??? ??后向弧前向弧ijijijijffcq22 最大流最小截的標(biāo)號(hào)法步驟 第一步：標(biāo)號(hào)過(guò)程，找一條增廣鏈 給源點(diǎn) s 標(biāo)號(hào) [s+,q(s)=?]，表示從 s 點(diǎn)有無(wú)限流出潛力 找出與已標(biāo)號(hào)節(jié)點(diǎn) i 相鄰的所有未標(biāo)號(hào)節(jié)點(diǎn) j，若 (1) (i, j)是前向弧且飽和，則節(jié)點(diǎn) j 不標(biāo)號(hào)； (2) (i, j)是前向弧且未飽和，則節(jié)點(diǎn) j 標(biāo)號(hào)為 [i+,q(j)]，表示從節(jié)點(diǎn) i 正向 流出，可增廣 q(j)=min[q(i), cij?fij] ； (3) (j, i)是后向弧，若 fji=0，則節(jié)點(diǎn) j 不標(biāo)號(hào)； (4) (j, i)是后向弧，若 fji0，則節(jié)點(diǎn) j 標(biāo)號(hào)為 [i?,q(j)]，表示從節(jié)點(diǎn) j 流向 i， 可增廣 q(j)=min[q(i), fji] ； 重復(fù)步驟 2，可能出現(xiàn)兩種情況： (1) 節(jié)點(diǎn) t 尚未標(biāo)號(hào)，但無(wú)法繼續(xù)標(biāo)記，說(shuō)明網(wǎng)路中已不存在增廣鏈，當(dāng)前流 v(f) 就是最大流；所有獲標(biāo)號(hào)的節(jié)點(diǎn)在 V 中，未獲標(biāo)號(hào)節(jié)點(diǎn)在 V 中， V 與 V 間的弧即為最小截集；算法結(jié)束 (2)節(jié)點(diǎn) t 獲得標(biāo)號(hào)，找到一條增廣鏈，由節(jié)點(diǎn) t 標(biāo)號(hào)回溯可找出該增廣鏈；到第二步 23 最大流最小截的標(biāo)號(hào)法步驟 第二步：增廣過(guò)程 對(duì) 增廣鏈中的前向弧，令 f?=f+q(t)， q(t) 為節(jié)點(diǎn) t 的標(biāo)記值 對(duì) 增廣鏈中的后向弧，令 f?=f?q(t) 非增廣鏈上的所有支路流量保持不變 第三步：抹除圖上所有標(biāo)號(hào)，回到第一步 ? 以上算法是按廣探法描述的，但在實(shí)際圖上作業(yè)時(shí)，按深探法進(jìn)行更快捷 ? 一次只找一條增廣鏈，增廣一次換一張圖 ? 最后一次用廣探法，以便找出最小截集 24 最大流最小截集的標(biāo)號(hào)法舉例 s t13 42 56(14,14)(9,9)(15 ,9)(16 ,15 )(3,1)(12 ,10 )(6,6)(4,3 )(5,5)(22,22)(13,12)(7,5)(6,3)(19,10)s t13 42 56(14,14)(9,9)(15 ,10 )(16 ,15 )(3,1)(12 ,10 )(6,5)(4,4 )(5,5)(22,22)(13,12)(7,5)(6,3)(19,11)(s+,?) (s+,6) (2?,6) (3+,1) (4+,1) (s+,?) (s+,5) (2+,2) (5?,2) (4+,2) 25 最大流最小截集的標(biāo)號(hào)法舉例 s t13 42 56(14,14)(9,9)(15 ,10 )(16 ,15 )(3,1)(12 ,10 )(6,5)(4,4 )(5,5)(22,22)(13,12)(7,5)(6,3)(19,11)s t13 42 56(14,14)(9,9)(15 ,12 )(16 ,15 )(3,1)(12 ,12 )(6,5)(4,4 )(5,5)(22,22)(13,12)(7,5)(6,1)(19,13)(s+,?) (s+,3) (2?,3) 最小截集 26 最大流標(biāo)號(hào)法的復(fù)雜度討論 s tvu20 0020 0020 0020 001? 找一條增廣鏈的計(jì)算量是容易估計(jì)的，不會(huì)超過(guò) O(n2) ? 但是最多迭代多少次 (即增廣的次數(shù) )就很難估計(jì)，在最壞情況下，與邊的容量有關(guān)；如上圖：先增廣 s ? u ? v ? t , 然后增廣 s ? v ? u ? t，每次只能增廣 1 個(gè)單位，故要增廣 4000次才能結(jié)束 ? 克服這種缺點(diǎn)的經(jīng)驗(yàn)方法： – 盡量先用段數(shù)少的增廣鏈 – 盡量不重復(fù)前面出現(xiàn)過(guò)的增廣鏈 27 多端網(wǎng)路問(wèn)題 1 8764352(15, 0)(10, 0)(20, 0)(5,0 )(5,0 )(5,0 )(5,0 )(5,0 )(10, 0)(10, 0)(10, 0)(10, 0)發(fā)點(diǎn) 120發(fā)點(diǎn) 2
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1