網(wǎng)絡(luò)最大流問(wèn)題算法研究【畢業(yè)論文】

1、<p><b>　　本科畢業(yè)論文</b></p><p><b>　?。?0 屆）</b></p><p>　　網(wǎng)絡(luò)最大流問(wèn)題算法研究</p><p>　　所在學(xué)院 </p><p>　　專業(yè)班級(jí) 數(shù)學(xué)與應(yīng)用數(shù)學(xué)

2、 </p><p>　　學(xué)生姓名 學(xué)號(hào) </p><p>　　指導(dǎo)教師 職稱 </p><p>　　完成日期 年 月 </p><p><b>　　摘要</b></p>

3、<p>　　網(wǎng)絡(luò)最大流問(wèn)題是一個(gè)應(yīng)用極為廣泛的問(wèn)題, 在交通運(yùn)輸系統(tǒng)和金融系統(tǒng)中都有廣泛應(yīng)用, 網(wǎng)絡(luò)最大流是計(jì)算機(jī)科學(xué)和運(yùn)籌學(xué)的重要內(nèi)容. 20世紀(jì)50年代, 由福特(Ford)、富克遜（Fulkerson）建立的“網(wǎng)絡(luò)流理論”成為網(wǎng)絡(luò)應(yīng)用的重要組成部分. 最近幾十年來(lái)關(guān)于網(wǎng)絡(luò)最大流方面的研究有很大進(jìn)展, 研究成果也是層出不窮, 本文基于以往學(xué)者的研究成果上對(duì)網(wǎng)絡(luò)最大流問(wèn)題進(jìn)行了分析與總結(jié), 并給出了網(wǎng)絡(luò)最大流算法中標(biāo)號(hào)算

4、法的求解過(guò)程, 也涉及在實(shí)際生活中的應(yīng)用. 最后介紹了現(xiàn)在流行的一些最大流主要算法和實(shí)例.</p><p>　　關(guān)鍵詞: 網(wǎng)絡(luò)最大流; 標(biāo)號(hào); 增廣鏈; 算法</p><p>　　Network maximal-flow problem research</p><p><b>　　Abstract</b></p><p&g

5、t;　　Network maximum flow problem is a wide range of applications problem. It is widely used in transportation systems and financial systems, the network maximum flow is an important computer science and operations resear

6、ch content. The "Network Flow Theory", established by Ford and Fulkerson in 1950 has become an important part of network applications. In recent decades the maximum flow on the network of research has made grea

7、t progress, the achievements are fruitful, this dissertation is based on t</p><p>　　Keywords: Maximum network flow; Labeling algorithm; Augmented chain Algorithm</p><p><b>　　目錄</b>&

8、lt;/p><p><b>　　摘要I</b></p><p>　　AbstractII</p><p>　　1 前言……………1</p><p>　　2 理論基礎(chǔ)……………………………………………………………………………...………..3</p><p>　　2.1 相關(guān)定義3</p

9、><p>　　2.2 最大流最小割定理5</p><p><b>　　3標(biāo)號(hào)算法7</b></p><p>　　3.1 標(biāo)號(hào)過(guò)程7</p><p>　　3.2 調(diào)整過(guò)程7</p><p>　　3.3 標(biāo)號(hào)算法的matlab實(shí)現(xiàn)……………………………………………………………...8<

10、;/p><p>　　3.4 標(biāo)號(hào)法應(yīng)用舉例…………………………………………………………………….....9</p><p>　　4 網(wǎng)絡(luò)最大流其他算法簡(jiǎn)要介紹…………………………………………………….........15</p><p>　　5 小結(jié)…………………………………………………………………………………………...19</p><p>

11、<b>　　參考文獻(xiàn)20</b></p><p><b>　　致謝21</b></p><p><b>　　1 前言</b></p><p>　　網(wǎng)絡(luò)最大流應(yīng)用非常廣泛, 在交通運(yùn)輸網(wǎng)絡(luò)中有人流、車流、貨物流, 供水網(wǎng)絡(luò)中有水流, 金融系統(tǒng)中有現(xiàn)金流, 通訊網(wǎng)絡(luò)中有信息流等. 還用于求電力傳輸問(wèn)題

12、、供銷通路問(wèn)題中的最大流.</p><p>　　最大流問(wèn)題已經(jīng)有幾十年的研究歷史, 在這幾十年中, 人們建立了最大流問(wèn)題比較完善的理論, 從Ford和Fulkerson提出第一個(gè)最大流算法到現(xiàn)在, 很多學(xué)者都對(duì)其進(jìn)行了改進(jìn)并提出了很多新的算法, 同時(shí)開(kāi)發(fā)出了大量?jī)?yōu)秀的算法, 如Ford和Fulkerson增截軌算法、 Dinic阻塞流算法、Goldberg推進(jìn)和重標(biāo)號(hào)算法以及Goldberg和Rao的二分長(zhǎng)度阻塞

13、流算法等等, 這些經(jīng)典算法及其中用到的相關(guān)技術(shù)對(duì)網(wǎng)絡(luò)最大流問(wèn)題的研究和發(fā)展起到了非常重要的推動(dòng)作用. 近年來(lái), 隨著網(wǎng)絡(luò)和計(jì)算機(jī)科學(xué)的飛速發(fā)展, 最大流問(wèn)題得到了更深的研究. 多年來(lái), 盡管在眾多學(xué)者的共同努力下最大流問(wèn)題的研究取得了極大的進(jìn)展, 但是關(guān)于最大流問(wèn)題的研究還遠(yuǎn)遠(yuǎn)沒(méi)有結(jié)束. 首先, 在理論算法研究方面, 還沒(méi)有發(fā)現(xiàn)最大流問(wèn)題算法時(shí)間復(fù)雜度的精確下界, 更沒(méi)有任何一種通用算法達(dá)到或接近問(wèn)題的下界; 其次, 在算法的實(shí)際性能方

14、面, 目前算法的實(shí)際性能也不能滿足很多應(yīng)用問(wèn)題的需求. </p><p>　　最大流算法的研究過(guò)程中最早是Dantzig提出的網(wǎng)絡(luò)單純形法和Ford和Fulkerson的增載軌算法, 他們都是偽多項(xiàng)式算法. 20世紀(jì)70年代出現(xiàn)了多項(xiàng)式時(shí)間算法, 分別由Dinic、Edmonds和Karp等提出. 從最大流問(wèn)題的提出到現(xiàn)在的發(fā)展, 其中出現(xiàn)了很多優(yōu)秀的算法, 其中增載軌算法、預(yù)流推進(jìn)算法的貢獻(xiàn)比較突出, 基本上很

15、多算法都是基于這兩種算法的基礎(chǔ)上得到的, 其他的算法還包括線性規(guī)劃算法、隨機(jī)算法等. 算法的發(fā)展過(guò)程中, 先后引入了剩余網(wǎng)絡(luò)、增載軌、層次網(wǎng)絡(luò)等概念, 對(duì)最大流問(wèn)題的發(fā)展起了很大的推動(dòng)作用.</p><p>　　對(duì)于一個(gè)網(wǎng)絡(luò)最大流問(wèn)題, 現(xiàn)在有很多求解方法, 如重標(biāo)號(hào)算法、預(yù)流推進(jìn)算法等. 對(duì)一個(gè)最大流問(wèn)題也可以用線性規(guī)劃方法求解, 也就是說(shuō), 將一個(gè)最大流問(wèn)題轉(zhuǎn)化為一個(gè)線性規(guī)劃模型, 再用單純形法求解. 有些情

16、況下運(yùn)用線性規(guī)劃模型求解很方便, 而且易于理解.</p><p>　　這幾十年來(lái), 很多著名學(xué)者開(kāi)發(fā)出了很多優(yōu)秀的算法, 由R. K. Ahuja和B. Orlin提出的快速算法是基于Goldberg和Tarjan的算法而得到的一個(gè)平行算法, 即預(yù)流推進(jìn)算法. 其對(duì)后面學(xué)者的研究起了很大的指導(dǎo)作用. 在具有適宜整數(shù)邊容量的稀疏圖中, Gabow的縮進(jìn)算法是最好的. 而基于Dinic算法結(jié)構(gòu)的那些算法中, 唯一的一

17、個(gè)平行算法是由Shiloach和Vishkin給出. Goldberg給出了基于Karzanov預(yù)流思想的新算法, 即在剩余網(wǎng)絡(luò)中尋找最短路徑. Gallo和Tarjan等提出通過(guò)重優(yōu)化技術(shù)能解決參數(shù)最大流中的很多問(wèn)題, 其是對(duì)Goldberg和Tarjan的推重標(biāo)號(hào)法進(jìn)行的拓展, 進(jìn)一步優(yōu)化了最大流問(wèn)題算法.</p><p>　　由Ford和Fulkerson提出的增廣鏈算法是基礎(chǔ), Edmonds和Karp

18、提出的另外一個(gè)方法是始終沿著最短路徑增廣, 它利用的是廣度優(yōu)先搜索思想, 這種算法存在一個(gè)最壞運(yùn)行時(shí)間. 還有Dinic獨(dú)自提出的最短路徑增廣等算法, 這些都對(duì)最大流問(wèn)題的算法研究產(chǎn)生了巨大的影響.</p><p>　　最近也有很多關(guān)于無(wú)向網(wǎng)絡(luò)最大流問(wèn)題的研究, 而且發(fā)展迅速, 但是本文主要講述的是有向網(wǎng)絡(luò)圖中最大流問(wèn)題的算法及其應(yīng)用, 并不涉及無(wú)向網(wǎng)絡(luò)流算法問(wèn)題. 下面簡(jiǎn)要介紹一下本文的大概內(nèi)容: 本文第一部分

19、介紹與網(wǎng)絡(luò)最大流問(wèn)題有關(guān)的定義及定理, 第二部分介紹最常見(jiàn)的網(wǎng)絡(luò)最大流算法—標(biāo)號(hào)算法, 第三部分簡(jiǎn)要介紹網(wǎng)絡(luò)最大流問(wèn)題算法中比較流行的幾種其他算法, 后面一部分對(duì)本文講述的算法及舉例進(jìn)行總結(jié). 最后一部分是致謝.</p><p><b>　　2 理論基礎(chǔ)</b></p><p><b>　　2.1 相關(guān)定義</b></p><

20、;p>　　最大流問(wèn)題是一類應(yīng)用極為廣泛的問(wèn)題. 在實(shí)際應(yīng)用中, 從公司配送網(wǎng)絡(luò)中求工廠到客戶的流量到求交通網(wǎng)絡(luò)中的最大車流量都是最大流問(wèn)題. 盡管最大流問(wèn)題中僅有一個(gè)發(fā)點(diǎn)和一個(gè)收點(diǎn), 但是, 在實(shí)際應(yīng)用中, 流可能來(lái)自多點(diǎn), 并終于多點(diǎn). 例如一個(gè)公司的配送網(wǎng)絡(luò)通常有多個(gè)工廠和多個(gè)客戶. 生活中這類問(wèn)題很多, 但是要研究最大流問(wèn)題, 就需要了解有關(guān)的概念.（定義2.7和定義2.8是與第4節(jié)中新算法有關(guān)定義）</p>

21、<p>　　定義2.1 所有流經(jīng)網(wǎng)絡(luò)（有向且連通）的流都起源于同一點(diǎn), 叫發(fā)點(diǎn)（源）, 終止于另一點(diǎn)叫收點(diǎn)（匯）. 剩余的其他點(diǎn)叫中間點(diǎn). </p><p>　　定義2.2 設(shè)為一個(gè)賦權(quán)連通的有向圖, 如果對(duì)于每一條弧均有一個(gè)非負(fù)實(shí)數(shù)與之對(duì)應(yīng), 稱為弧的容量. 表示該弧的最大容量, 簡(jiǎn)稱弧容量. 在中指定一個(gè)發(fā)點(diǎn)和一個(gè)收點(diǎn), 中其他點(diǎn)是中間點(diǎn), 這樣的圖叫做容量網(wǎng)絡(luò), 記作.</p>

22、<p>　　定義2.3 設(shè)給定容量網(wǎng)絡(luò)圖, 將滿足下列兩個(gè)條件的流稱為可行流.</p><p><b>　?。ㄈ萘考s束）.</b></p><p>　　對(duì)任意（為中間點(diǎn)集）, 有</p><p><b>　　,</b></p><p>　　即中間點(diǎn)的物資輸入量與輸出量相等.<

23、;/p><p>　　對(duì)于發(fā)點(diǎn)與收點(diǎn), 有</p><p><b>　?。ㄆ胶饧s束）,</b></p><p>　　則稱為發(fā)點(diǎn)的總流量, 即容量網(wǎng)絡(luò)的總流量.</p><p>　　定義2.4 設(shè)有容量網(wǎng)絡(luò), 為發(fā)點(diǎn), 為收點(diǎn), 如果把分成兩個(gè)非空集合,(), 使, 則所有始點(diǎn)屬于, 而終點(diǎn)屬于的弧的集合, 稱為由決定的割集（截

24、集）, 記作. 割集中所有弧的容量之和, 稱為這個(gè)割集的容量, 記為. </p><p>　　定義2.5 設(shè)為可行流, 對(duì)任意, 分別稱</p><p>　　為的流出量與流入量, 若記</p><p><b>　　,</b></p><p>　　稱為的凈流出量, 簡(jiǎn)稱為的流量. </p><p>

25、;　　定義2.6 增廣鏈</p><p>　　對(duì)容量網(wǎng)絡(luò),若為網(wǎng)絡(luò)中從到的一條鏈（即不考慮每條弧的方向）, 定義的方向?yàn)閺牡? 上的凡是與方向相同的弧稱為前向弧, 凡與方向相反的弧稱為后向弧, 其集合分別用和表示, 若為網(wǎng)絡(luò)中從到的一條鏈, 是一個(gè)可行流, 如果滿足</p><p>　　則稱為從到的（關(guān)于的）一條增廣鏈.</p><p>　　定義2.7 一致鏈&

26、lt;/p><p>　　若是網(wǎng)絡(luò)中連接發(fā)點(diǎn)和收點(diǎn)的一條鏈, 對(duì)于（其中為網(wǎng)絡(luò)中的?。? , 則稱是從到的一條一致鏈.</p><p>　　定義2.8 極大一致鏈</p><p>　　設(shè)是網(wǎng)絡(luò)中連接發(fā)點(diǎn)和收點(diǎn)的一條一致鏈, 也是網(wǎng)絡(luò)中連接發(fā)點(diǎn)和收點(diǎn)的一條鏈, 是兩條鏈的公共點(diǎn)的集合, 若對(duì)于 且 都有表示從到的容量）, 則稱是網(wǎng)絡(luò)中從發(fā)點(diǎn)到收點(diǎn)的一條極大一致鏈.<

27、/p><p>　　2.2 最大流最小割定理</p><p>　　最大流最小割定理由Ford和Fulkerson提出, 所以也叫Ford-Fulkerson定理, 它是網(wǎng)絡(luò)最大流問(wèn)題中一個(gè)非常重要的定理, 下面是對(duì)最大流最小割定理的介紹:</p><p>　　定理 1 設(shè)為網(wǎng)絡(luò)的任一可行流, 流量為, 為分離, 的任一割集, 則有.</p><p&g

28、t;　　上面的定理說(shuō)明網(wǎng)絡(luò)中可行流的流量以的割集的最小容量為上界, 而割集的容量又以可行流的最大流為下界. 如果網(wǎng)絡(luò)上的一個(gè)可行流和網(wǎng)絡(luò)中的一個(gè)割集, 滿足條件, 那么一定是上的最大流, 而一定是的最小割集.</p><p>　　定理 2(Ford-Fulkerson定理) 在任何網(wǎng)絡(luò)中, 從到得最大流的流量等于分離, 的最小割集的容量. （也稱最大流-最小割定理）</p><p>　　證

29、明: 設(shè)為的一個(gè)最大流, 流量為, 首先定義點(diǎn)集, 滿足如下條件:</p><p><b>　　;</b></p><p>　　, 且, 令, 則弧為非飽和弧;</p><p>　　若, 且, 令, 則弧為非零弧.</p><p>　　因而, 否則若, 則有從到的鏈, 對(duì)中的前向弧, 必有, 后向弧必有. 把修改為, 即

30、令</p><p><b>　　而, 其中</b></p><p>　　顯然. 可驗(yàn)證仍為的一個(gè)可行流, 但的總流量等于的流量加上, 這與為最大流矛盾. 故, 從而得到的一個(gè)割集, , 且對(duì), 顯然有</p><p><b>　　其次有</b></p><p><b>　　,</b&

31、gt;</p><p><b>　　即. 定理得證.</b></p><p>　　在得到最大流時(shí), 同時(shí)也得到了一個(gè)最小割集, 這一最小割集對(duì)分析網(wǎng)絡(luò)有重要意義.</p><p><b>　　3 標(biāo)號(hào)算法</b></p><p>　　標(biāo)號(hào)法是從網(wǎng)絡(luò)中的一個(gè)可行流出發(fā)（如果中沒(méi)有可行流, 可以令是零流

32、）, 運(yùn)用標(biāo)號(hào)法, 經(jīng)過(guò)標(biāo)號(hào)過(guò)程和調(diào)整過(guò)程, 可以得到網(wǎng)絡(luò)中的一個(gè)最大流. 下面具體看看標(biāo)號(hào)法的標(biāo)號(hào)過(guò)程.</p><p><b>　　3.1 標(biāo)號(hào)過(guò)程</b></p><p>　　第一步 給發(fā)點(diǎn)標(biāo)號(hào)</p><p>　　第二步 取一個(gè)已標(biāo)號(hào)的點(diǎn), 對(duì)于的一切未標(biāo)號(hào)的鄰接點(diǎn)按下列規(guī)則處理：</p><p>　　如果弧

33、（即為始點(diǎn), 為終點(diǎn)）, 且 那么給標(biāo)號(hào)其中</p><p>　　如果?。礊槭键c(diǎn), 為終點(diǎn)）, 且 那么給標(biāo)號(hào)其中</p><p>　　第三部 轉(zhuǎn)第二步, 直到被標(biāo)號(hào)或標(biāo)號(hào)過(guò)程無(wú)法進(jìn)行下去, 則標(biāo)號(hào)過(guò)程結(jié)束.</p><p>　　若被標(biāo)號(hào), 則存在一條可增廣鏈, 轉(zhuǎn)調(diào)整過(guò)程（第二步）; 若未被標(biāo)號(hào),則標(biāo)號(hào)過(guò)程無(wú)法進(jìn)行下去, 說(shuō)明可行流就是最大流.</p&g

34、t;<p><b>　　3.2 調(diào)整過(guò)程</b></p><p>　　設(shè)是一條從到得增廣鏈, 的前向弧集合和后向弧集合分別用和表示, 設(shè)</p><p>　　如果上沒(méi)有后向弧, 則令取</p><p><b>　　第一步 令</b></p><p>　　第二步 去掉所有標(biāo)號(hào), 回到標(biāo)

35、號(hào)過(guò)程, 對(duì)可行流重新標(biāo)號(hào).</p><p>　　上面所述的就是標(biāo)號(hào)的全過(guò)程, 在計(jì)算時(shí)我們只用按照上面的步驟一步一步來(lái), 就能得到一個(gè)網(wǎng)絡(luò)的最大流量.</p><p>　　3.3 標(biāo)號(hào)算法的matlab實(shí)現(xiàn)</p><p>　　現(xiàn)有的最大流算法很多, 而對(duì)于最大流算法在實(shí)際中的應(yīng)用問(wèn)題, 大部分都是借助于計(jì)算機(jī)技術(shù)來(lái)評(píng)測(cè)算法的優(yōu)劣, 運(yùn)行的時(shí)間越長(zhǎng), 說(shuō)明算法的時(shí)

36、間復(fù)雜度越不好, 運(yùn)行時(shí)間越短, 越精確, 說(shuō)明算法越好. 下面就是標(biāo)號(hào)算法在matlab上的實(shí)現(xiàn).</p><p>　　int n; C; % n為頂點(diǎn)數(shù), C為弧容量矩陣, 對(duì)于實(shí)際問(wèn)題輸入數(shù)據(jù)</p><p>　　for(i=1:n)</p><p>　　for(j=1:n)</p><p><

37、b>　　f(i,j)=0;</b></p><p><b>　　end;</b></p><p>　　end %取初始可行流f為零流</p><p>　　for(i=1:n)</p><p>　　No(i)=0;d(i)=0;</p><p

38、>　　end %No, d記錄標(biāo)號(hào)</p><p><b>　　while(1)</b></p><p>　　No(1)=n+1;d(1)=Inf; %給發(fā)點(diǎn)vs標(biāo)號(hào)</p><p>　　while(1) pd=1; %標(biāo)號(hào)過(guò)程</p>&

39、lt;p>　　for(i=1:n)</p><p>　　if(No(i)) %選擇一個(gè)已標(biāo)號(hào)的點(diǎn)vi</p><p>　　for(j=1:n)</p><p>　　if(No(j)==0&f(i,j)<C(i,j)) %對(duì)于未給標(biāo)號(hào)的點(diǎn)vj, 當(dāng)vivj為非飽和弧時(shí)</p><p&g

40、t;　　No(j)=i; d(j)=C(i,j)-f(i,j); pd=0; </p><p>　　if(d(j)>d(i))</p><p>　　d(j)=d(i);</p><p><b>　　end</b></p><p>　　elseif(No(j)==0& f(j,i)>0) %對(duì)于

41、未給標(biāo)號(hào)的點(diǎn)vj, 當(dāng)vjvi為非零流弧時(shí)</p><p>　　No(j)=-i; d(j)=f(j,i); pd=0;</p><p>　　if(d(j)>d(i))</p><p>　　d(j)=d(i);end ;end; end; end; end</p><p>　　if(No(n)|pd)</p><p&

42、gt;　　break ; end; end %若收點(diǎn)vt得到標(biāo)號(hào)或者無(wú)法標(biāo)號(hào), 終止標(biāo)號(hào)過(guò)程</p><p><b>　　if(pd)</b></p><p>　　break;end %vt未得到標(biāo)號(hào), f已是最大流, 算法終止</p><p>　　dvt=d(n);t=n;

43、 %進(jìn)入調(diào)整過(guò)程, dvt表示調(diào)整量</p><p><b>　　while(1)</b></p><p>　　if(No(t)>0)</p><p>　　f(No(t),t)=f(No(t),t)+dvt; %前向弧調(diào)整</p><p>　　elseif(No(t)<0)</

44、p><p>　　f(No(t),t)= f(No(t),t)-dvt;</p><p>　　end %后向弧調(diào)整</p><p>　　if(No(t)==1)</p><p>　　for(i=1:n)</p><p>　　No(i)=0; d(i)=0;</p>&

45、lt;p>　　end; break;end %當(dāng)t的標(biāo)號(hào)為vs時(shí), 終止調(diào)整過(guò)程</p><p>　　t=No(t); end;end; %繼續(xù)調(diào)整前一段弧上的流f</p><p><b>　　wf=0;</b></p><p>　　for(j=1:n)</p><p&g

46、t;　　wf= wf+f(1,j); end %計(jì)算最大流量</p><p>　　f; %顯示最大流</p><p>　　wf %顯示最大流量</p><p>　　No %顯示標(biāo)號(hào), 由此可得最小割, 程序結(jié)

47、束</p><p>　　上面的算法標(biāo)明了標(biāo)號(hào)算法在matlab上的具體實(shí)現(xiàn), 對(duì)于一個(gè)實(shí)際問(wèn)題, 則可以在第一步輸入數(shù)據(jù), 通過(guò)算法得到最大流和最小割等, 既簡(jiǎn)潔, 又方便.</p><p>　　3.4標(biāo)號(hào)法應(yīng)用舉例</p><p>　　在現(xiàn)實(shí)生活中, 很多最優(yōu)化問(wèn)題, 如通過(guò)求交通網(wǎng)絡(luò)上的最大流來(lái)安排貨物的運(yùn)輸情況, 以達(dá)到合理利用道路流量等都需要對(duì)原有系統(tǒng)進(jìn)行簡(jiǎn)

48、化. 下面的兩個(gè)例子就是實(shí)際問(wèn)題的簡(jiǎn)化:</p><p>　　解: 先給發(fā)點(diǎn)標(biāo)號(hào). 檢查的鄰接點(diǎn)1, 2 , 發(fā)現(xiàn)1點(diǎn)滿足, 且那么給1點(diǎn)標(biāo)號(hào), 2點(diǎn)不滿足標(biāo)號(hào)條件. 再檢查1的鄰接點(diǎn)2和3, 發(fā)現(xiàn)2滿足, 那么給2標(biāo)號(hào) 3點(diǎn)不滿足標(biāo)號(hào)條件. 再檢查2的鄰接點(diǎn)3和4, 4點(diǎn)滿足 且 那么給4點(diǎn)標(biāo)號(hào), 再看3點(diǎn), 3點(diǎn)滿足 那么給3點(diǎn)標(biāo)號(hào), 再檢查3的鄰接點(diǎn), 發(fā)現(xiàn)點(diǎn)滿足 那么給點(diǎn)標(biāo)號(hào), 點(diǎn)已經(jīng)得到了標(biāo)號(hào), 說(shuō)明

49、存在增廣鏈, 標(biāo)號(hào)過(guò)程結(jié)束. 如圖所示:</p><p><b>　　下面進(jìn)入調(diào)整過(guò)程:</b></p><p>　　顯然: 是一條增廣鏈.</p><p><b>　　取 令</b></p><p>　　按照逆增廣鏈方向（即由）, 則有: 調(diào)整過(guò)程結(jié)束, 見(jiàn)下圖, 圖中粗線為調(diào)整后的增廣鏈.

50、</p><p>　　重新進(jìn)入標(biāo)號(hào)過(guò)程, 當(dāng)對(duì)1點(diǎn)進(jìn)行標(biāo)號(hào)后, 標(biāo)號(hào)工程無(wú)法進(jìn)行下去, 點(diǎn)并未得到標(biāo)號(hào), 說(shuō)明此時(shí)是最大流. 最大流的流量 同時(shí)得到一個(gè)最小割集, 得到下圖, 虛線為最小割集.</p><p>　　上述結(jié)果也可以直接用給定的程序運(yùn)行一下, 進(jìn)行對(duì)比, 只需給定:</p><p>　　; =[ ; ; 4 ; ;

51、 ; ]; 運(yùn)行程序可以得到結(jié)果:</p><p>　　wf=; No= ; 將此結(jié)果和用標(biāo)號(hào)過(guò)程的進(jìn)行對(duì)比, 驗(yàn)證結(jié)果的正確性.</p><p>　　只有一個(gè)發(fā)點(diǎn)和一個(gè)收點(diǎn)的網(wǎng)絡(luò)為簡(jiǎn)單網(wǎng)絡(luò). 但是實(shí)際上, 在實(shí)際應(yīng)用問(wèn)題上有多個(gè)發(fā)點(diǎn)和多個(gè)收點(diǎn)的網(wǎng)絡(luò), 為了簡(jiǎn)化計(jì)算, 我們可將它們轉(zhuǎn)化為簡(jiǎn)單網(wǎng)絡(luò), 這樣能使得計(jì)算效率大大提高. 轉(zhuǎn)化方法為虛擬一個(gè)發(fā)點(diǎn)（用表示發(fā)點(diǎn)集,

52、 表示收點(diǎn)集）, 對(duì)于每一個(gè)增加一條從到的弧, 適當(dāng)定義該弧的容量, 從而將原網(wǎng)絡(luò)擴(kuò)充為一個(gè)簡(jiǎn)單的網(wǎng)絡(luò). 下面的例題就是對(duì)一個(gè)實(shí)際問(wèn)題的擴(kuò)充的情況下求其最大流量.</p><p>　　例題: 某大型物流公司想要沿著如下圖的交通網(wǎng)絡(luò)從1和2點(diǎn)經(jīng)過(guò)中間運(yùn)輸點(diǎn)3、4、5運(yùn)往6和7兩點(diǎn), 每條路段對(duì)該公司每天通過(guò)的物流量都有限制, 其值為圖中每條弧上的權(quán)數(shù), 現(xiàn)1和2點(diǎn)各有物資100和200噸, 而6和7點(diǎn)需求量各為15

53、0和180噸, 試問(wèn)物流公司最多能通過(guò)這個(gè)交通網(wǎng)絡(luò)運(yùn)送多少物資, 并給出運(yùn)輸方案.</p><p>　　解: 通過(guò)問(wèn)題的分析, 我們能發(fā)現(xiàn)上面所述問(wèn)題就是求最大流量問(wèn)題, 但是我們發(fā)現(xiàn)始點(diǎn)和收點(diǎn)都超過(guò)一個(gè), 無(wú)法按照原來(lái)的方法計(jì)算, 所以我們要對(duì)原來(lái)網(wǎng)絡(luò)進(jìn)行擴(kuò)充.</p><p>　　我們按照上面的方法把原圖擴(kuò)充為一個(gè)簡(jiǎn)單網(wǎng)路, 如下圖:</p><p>　　設(shè) 其

54、為可行流, 給個(gè)點(diǎn)標(biāo)號(hào)后如下圖: </p><p>　　在圖12中尋求一條增廣鏈 將修改成, 重新標(biāo)號(hào)后得到圖3-4-8:</p><p>　　在圖13中尋求一條增廣鏈 將修改為, 并重新標(biāo)號(hào)后得到圖3-4-9:</p><p>　　在圖14中尋求一條增廣鏈 將修改成, 并重新標(biāo)號(hào)得到圖3-4-10:</p><p>　　在圖15中尋求一條增

55、廣鏈 將修改為, 并重新標(biāo)號(hào)得到圖3-4-11:</p><p>　　在圖16中尋求一條增廣鏈 將修改為, 并重新標(biāo)號(hào)得到圖3-4-12:</p><p>　　在圖17中尋求一條增廣鏈 將修改為, 并重新標(biāo)號(hào)得到圖3-4-13:</p><p>　　此時(shí), 我們可以發(fā)現(xiàn)不再存在增廣鏈, 點(diǎn)也得不到標(biāo)號(hào), 算法結(jié)束.</p><p>　　因此,

56、 為最大流, 最大流流量為 運(yùn)輸方案為1運(yùn)出100噸, 2運(yùn)出200噸, 6點(diǎn)云錦60噸, 7點(diǎn)運(yùn)進(jìn)180噸. </p><p>　　上述兩個(gè)例子都是最大流算法在實(shí)際中的應(yīng)用, 其實(shí)上面提到的只是生活中的一個(gè)方面, 最大流算法應(yīng)用廣泛, 其更多的解法還需我們努力去發(fā)掘.</p><p>　　4 網(wǎng)絡(luò)最大流其他算法簡(jiǎn)要介紹</p><p>　　上面提到的標(biāo)號(hào)算法是現(xiàn)在

57、運(yùn)籌學(xué)教科書中主要介紹的方法, 也是現(xiàn)在計(jì)算最大流量的重要算法, 來(lái)源于Ford和Fulkerson. 其他算法還包括預(yù)流推進(jìn)算法、Edmonds – Karp算法、Dinic算法、SAP算法、最大容量路徑算法、Capacity Scaling Algorithm等, 它們各有其優(yōu)點(diǎn), 復(fù)雜度也各有差異. 下面來(lái)簡(jiǎn)要介紹一下這些算法:</p><p>　　Shortest Augmenting Path (SAP

58、)是每次尋找最短增廣路的一類算法, Edmonds - Karp 算法以及后來(lái)著名的Dinic算法都屬于此. SAP算法思想為: 在無(wú)權(quán)邊的有向圖中尋找最短路, 最簡(jiǎn)單的方法就是廣度優(yōu)先搜索 (BFS), E-K算法就直接來(lái)源于此. 每次用一遍BFS尋找從源點(diǎn)到終點(diǎn)的最短路作為增廣路徑, 然后增廣流量并修改剩余網(wǎng)絡(luò), 直到不存在新的增廣路徑. E-K算法的時(shí)間復(fù)雜度為 由于BFS要搜索全部小于最短距離的分支路徑之后才能找到終點(diǎn)因此可以想

59、象頻繁的BFS效率是比較低的. 實(shí)踐中此算法使用的機(jī)會(huì)較少.</p><p>　　Dinic算法：BFS尋找重點(diǎn)速度太慢, 而DFS又不能保證找到最短路徑. 1970年Dinic提出一種思想, 其結(jié)合了BFS與DFS的優(yōu)勢(shì), 采用構(gòu)造分層網(wǎng)絡(luò)的方法可以較快找到最短增廣路, 此算法又稱為阻塞流算法（Blocking Flow Algorithm）.</p><p>　　首先定義分層網(wǎng)絡(luò), 在

60、生于網(wǎng)絡(luò)中從起始進(jìn)行BFS, 這樣每個(gè)頂點(diǎn)在BFS樹(shù)中會(huì)得到一個(gè)距源點(diǎn)的距離, 若 直接從出發(fā)可到達(dá)的點(diǎn)距離為1, 下一層距離為2……, 稱所有具有相同距離的頂點(diǎn)位于同一層, 在分層網(wǎng)絡(luò)中, 只保留滿足條件的邊, 這樣在分層網(wǎng)絡(luò)中的任意路徑就成為到達(dá)頂點(diǎn)的最短路徑. Dinic算法每一用一遍BFS構(gòu)建分層網(wǎng)絡(luò), 然后在中一遍DFS找到所有到終點(diǎn)的路徑增廣; 之后重新構(gòu)造, 若終點(diǎn)不在中則算法結(jié)束. Dinic算法的時(shí)間復(fù)雜度為. 由于較

61、少的代碼量和不錯(cuò)的運(yùn)行效率, Dinic算法在實(shí)踐中比較常見(jiàn).</p><p>　　Improved SAP算法：通常的SAP算法在尋找增廣路時(shí)總要先進(jìn)行BFS, BFS最壞情況下復(fù)雜度為, 這樣使得普通SAP算法最壞情況下時(shí)間復(fù)雜度達(dá)到了. 為了避免這種情況, Ahuja和Orlin在1987年提出了Improved SAP算法, 它充分利用了距離標(biāo)號(hào)的作用, 每次發(fā)現(xiàn)頂點(diǎn)無(wú)出弧時(shí)不是像Dinic算法那樣到最后

62、進(jìn)行BFS, 而是就地對(duì)頂點(diǎn)距離重標(biāo)號(hào), 這樣相當(dāng)于在遍歷的同時(shí)順便構(gòu)建了新的分層網(wǎng)絡(luò), 每輪尋找之間不必再插入全圖的BFS操作, 極大提高了運(yùn)行效率. 與Dinic算法不同, ISAP中的距離標(biāo)號(hào)是每個(gè)頂點(diǎn)到達(dá)終點(diǎn)的距離,之后從源點(diǎn)開(kāi)始, 進(jìn)行如下三步操作: （1） 當(dāng)前頂點(diǎn)為終點(diǎn)時(shí)增廣; （2） 當(dāng)前頂點(diǎn)有滿足的出弧時(shí)前進(jìn); （3） 當(dāng)前頂點(diǎn)無(wú)滿足條件的出弧時(shí)重標(biāo)號(hào)并回退一步. 整個(gè)循環(huán)當(dāng)源點(diǎn)的距離符號(hào)時(shí)結(jié)束. 雖然ISAP算法時(shí)間

63、復(fù)雜度與Dinic相同, 都是, 但在實(shí)際表現(xiàn)中要好很多. 要提的一點(diǎn)是關(guān)于ISAP的一個(gè)所謂GAP優(yōu)化. 由于從到得一條最短路徑的頂點(diǎn)距離標(biāo)號(hào)單調(diào)遞減, 且相鄰頂點(diǎn)標(biāo)號(hào)差嚴(yán)格等于1, 因此可以預(yù)見(jiàn)如果在當(dāng)前網(wǎng)絡(luò)中距離標(biāo)號(hào)為的頂</p><p>　　最大容量路徑算法：1972年E-K提出另外一種最大流算法. 即每次尋找增廣路時(shí)不找最短路徑, 而是尋找容量最大路徑.可以預(yù)見(jiàn), 此方法與SAP算法相比可更快逼近最大流

64、, 從而降低增廣操作的次數(shù). 實(shí)際算法也很簡(jiǎn)單, 只用把前面E-K算法的BFS部分替換為一個(gè)類Dijkstra算法即可. BFS是, 簡(jiǎn)單Dijkstra時(shí)間復(fù)雜度為, 因此效果可想而知.</p><p>　　Capacity Scaling Algorithm：此算法在尋找增廣路時(shí)不必要局限于尋找最大容量, 而是只要找到一個(gè)可接受的較大值即可, 一方面有效降低尋找增廣路時(shí)的復(fù)雜度, 另一方面增廣操作次數(shù)也不會(huì)增

65、加太多. 時(shí)間復(fù)雜度為, 實(shí)際效率稍好于前面提到的E-K算法, 但是仍然不及Dinic和ISAP算法.</p><p>　　其實(shí)正如其他作者在論文中所提到的那樣, 實(shí)際中面對(duì)不同問(wèn)題解決的方法可能不止一種, 甚至有很多解決的方法, 下面就是一個(gè)實(shí)際問(wèn)題的縮影, 而且運(yùn)用的不是傳統(tǒng)方法, 而是用一種新的算法得到它的最大流.</p><p>　　例2: 求圖4-1中的網(wǎng)絡(luò)最大流量.</p

66、><p><b>　　解:</b></p><p>　　如圖4-2所示, 找到了容量網(wǎng)絡(luò)中的極大一致鏈, 找到該鏈上各弧容量的最小值 記為. </p><p>　?。?）在極大一致鏈上的每條弧容量分別減去該最小值, 得到圖4-3的容量網(wǎng)絡(luò):</p><p>　　同理, 得到 給弧上每條弧容量分別減去, 得到圖4-4:<

67、/p><p><b>　　同上方法得到下圖:</b></p><p>　　對(duì)圖4-6進(jìn)行調(diào)整得到</p><p>　　計(jì)算結(jié)束, 此時(shí)得到容量網(wǎng)絡(luò)的最大流為: .</p><p>　　上面的算法稱為銷鏈算法, 與經(jīng)典的Ford-Fulkerson標(biāo)號(hào)算法相比, 該算法避免了多次對(duì)網(wǎng)絡(luò)的標(biāo)號(hào)過(guò)程, 大大降低了算法的復(fù)雜度. 這

68、里的極大一致鏈也使得算法得到了極大的優(yōu)化, 加快了整個(gè)算法的執(zhí)行速度, 上例的實(shí)例也驗(yàn)證了算法的效率和實(shí)用性. </p><p><b>　　5 小結(jié)</b></p><p>　　本文重在對(duì)現(xiàn)有的一些求網(wǎng)絡(luò)最大流算法進(jìn)行介紹, 以及對(duì)經(jīng)典算法進(jìn)行了舉例. 當(dāng)然, 最重要的還是能把這些算法應(yīng)用在實(shí)際生活中. 我們知道, 一種算法的好壞取決于其精確度和復(fù)雜度, 現(xiàn)有的IS

69、AP算法無(wú)疑是所有算法里面差不多是最好的, 但是增廣路算法還是其基礎(chǔ), 我們要在很好理解增廣路算法的基礎(chǔ)上才能更好理解其他算法. 也只有很好理解傳統(tǒng)方法才能創(chuàng)造新算法. 本文介紹的算法可借助編譯程序計(jì)算出他們的復(fù)雜度, 然后將它們進(jìn)行對(duì)比, 能發(fā)現(xiàn)各自的優(yōu)點(diǎn). 如今, 網(wǎng)絡(luò)流問(wèn)題在實(shí)際中應(yīng)用越來(lái)越廣泛, 新的算法也在不斷出現(xiàn), 一些經(jīng)典的算法在過(guò)去幾十年間得到了很大的改進(jìn), 使得最大流問(wèn)題的研究也越來(lái)越趨向成熟. 關(guān)鍵是在實(shí)際中我們能否

70、找到其和最大流問(wèn)題的聯(lián)系, 否則會(huì)走很多彎路. 事實(shí)上, 很多應(yīng)用問(wèn)題所對(duì)應(yīng)的最大流問(wèn)題都有比較明顯的特征, 但充分利用特征, 設(shè)計(jì)面向應(yīng)用問(wèn)題的算法并不多. 隨著計(jì)算機(jī)技術(shù)的發(fā)展, 相信在不久的將來(lái), 網(wǎng)絡(luò)最大流問(wèn)題能得到更好的發(fā)展.</p><p><b>　　參考文獻(xiàn)</b></p><p>　　廖敏. 運(yùn)籌學(xué)基礎(chǔ)與應(yīng)用 [M]. 南京: 南京大學(xué)出版社, 20

71、09: 190-197.</p><p>　　弗雷德里克?S?希利爾, 杰拉爾德?J?利伯曼（胡運(yùn)權(quán)等譯）. 運(yùn)籌學(xué)導(dǎo)論 [M]. 北京:清華大學(xué)出版社, 2007 : 375-381.</p><p>　　L R Ford, D R Fulkerson. Maximum flow through a network. Canadian Journal of Math, 1956, 8(5

72、): 399-404.</p><p>　　王志強(qiáng). 網(wǎng)絡(luò)最大流的新算法 [D]. 陜西: 寶雞文理學(xué)院, 2009. </p><p>　　張憲超, 陳國(guó)良, 萬(wàn)穎瑜等. 網(wǎng)絡(luò)最大流問(wèn)題研究進(jìn)展 [J]. 計(jì)算機(jī)研究與發(fā)展學(xué)報(bào), 2003, 40(9): 1281-1292.</p><p>　　A.V. Goldberg and R.E. Tarjan. A n

73、ew approach to the maximum-flow problem. Journal of the ACM, 1988, 35: 921-940.</p><p>　　趙可培. 運(yùn)籌學(xué) [M]. 第二版. 上海: 上海財(cái)經(jīng)出版社, 2008: 243-249.</p><p>　　R. K. Ahuja and J.B. Orlin. A fast and simple alg

74、orithm for the maximum flow problem. Oper. Res. 1989, 37: 748-759.</p><p>　　Maria Grazia Scutella. A note on the parametric maximum flow problem and some related reoptimization issues. Ann Oper Res, 2007, 15