網(wǎng)路的最大流和最小截-全文預(yù)覽
【正文】 最多迭代多少次 (即增廣的次數(shù) )就很難估計(jì)，在最壞情況下，與邊的容量有關(guān)；如上圖：先增廣 s ? u ? v ? t , 然后增廣 s ? v ? u ? t，每次只能增廣 1 個單位，故要增廣 4000次才能結(jié)束 ? 克服這種缺點(diǎn)的經(jīng)驗(yàn)方法： – 盡量先用段數(shù)少的增廣鏈 – 盡量不重復(fù)前面出現(xiàn)過的增廣鏈 9 多端網(wǎng)路問題 1 8764352( 1 5 , 0 )( 1 0 , 0 )( 2 0 , 0 )( 5 , 0 )( 5 , 0 )( 5 , 0 )( 5 , 0 )( 5 , 0 )( 1 0 , 0 )( 1 0 , 0 )( 1 0 , 0 )( 1 0 , 0 )發(fā)點(diǎn) 120發(fā)點(diǎn) 220收點(diǎn) 115收點(diǎn) 220( 5 , 0 )( , 1( 1 0 , 1 0 )555555( 1 0 , 1 0 )5虛發(fā)點(diǎn)虛收點(diǎn)st( 2 0 , 1 5 )( 2 0 , 1 5 )( 2 0 , 1 5 )( 1 5 , 1 5 )( 5 , 0 )10 最小費(fèi)用最大流 ? 雙權(quán)網(wǎng)路 ：每條弧不但有容量，還有單位流量的通過費(fèi)用 ? 兩種解法：一種基于最小費(fèi)用路徑算法；一種基于可行弧集的最大流算法 ? 基于最小費(fèi)用路徑算法 ：總是在當(dāng)前找到的最小費(fèi)用的路徑上增廣流；缺點(diǎn)是每次增廣后要改變弧的費(fèi)用，且出現(xiàn)負(fù)權(quán)值費(fèi)用的弧 ? 基于可行弧集的最大流算法 ：從 0 費(fèi)用弧集開始應(yīng)用最大流算法，然后根據(jù)計(jì)算信息提高費(fèi)用的限界 P，使可行弧集增大，再應(yīng)用最大流算法，直至所有弧都進(jìn)入可行弧集。
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1