複製鏈接
請複製以下鏈接發送給好友

網絡流理論

鎖定
網絡流理論(network-flows)是一種類比水流的解決問題方法,與線性規劃密切相關。網絡流的理論和應用在不斷髮展,出現了具有增益的流、多終端流、多商品流以及網絡流的分解與合成等新課題。網絡流的應用已遍及通訊、運輸、電力、工程規劃、任務分派、設備更新以及計算機輔助設計等眾多領域。
中文名
網絡流理論
外文名
Network flow theory
提出者
L.R.福特和D.R.富爾克森
提出時間
1956年
應用學科
網絡
學    科
計算機技術

網絡流理論理論研究

圖論中的一種理論與方法,研究網絡上的一類最優化問題。1955年,T.E.哈里斯在研究鐵路最大通量時首先提出在一個給定的網絡上尋求兩點間最大運輸量的問題。1956年,L.R.福特和D.R.富爾克森等人給出瞭解決這類問題的算法,從而建立了網絡流理論。在一個公路網中,頂點v1…v6表示6座城鎮,每條邊上的權數表示兩城鎮間的公路長度。要問:若從起點v1將物資運送到終點v6去,應選擇那條路線才能使總運輸距離最短?這樣一類問題稱為最短路問題。如果在一個輸油管道網中,v1表示發送點,v6表示接收點,其他點表示中轉站,各邊的權數表示該段管道的最大輸送量。要問怎樣安排輸油線路才能使從v1到v6的總運輸量為最大?這樣的問題稱為最大流問題

網絡流理論理論創建

最大流理論是由福特和富爾克森於1956年創立的,他們指出最大流的流值等於最小割(截集)的容量這個重要的事實,並根據這一原理設計了用標號法求最大流的方法,後來又有人加以改進,使得求解最大流的方法更加豐富和完善。最大流問題的研究密切了圖論和運籌學,特別是與線性規劃的聯繫,開闢了圖論應用的新途徑。
最大流問題僅注意網絡流的流通能力,沒有考慮流通的費用。實際上費用因素是很重要的。例如在交通運輸問題中,往往要求在完成運輸任務的前提下,尋求一個使總運輸費用最省的運輸方案,這就是最小費用流問題。如果只考慮單位貨物的運輸費用,那麼這個問題就變成最短路問題。由此可見,最短路問題是最小費用流問題的基礎。現已有一系列求最短路的成功方法。最小費用流(或最小費用最大流)問題,可以交替使用求解最大流和最短路兩種方法,通過迭代得到解決。網絡最大流問題和它的對偶問題——最小截問題,是一對經典組合優化問題,它們在許多工程領域和科學領域有重要的應用,是計算機科學和運籌學重要的內容,最大流問題已經有40多年的研究歷史,近年來,隨着各種網絡的飛速發展,最大流問題的研究也取得了很大的進展,對最大流問題研究做了詳細的總結,並對下一步研究趨勢進行了預測。

網絡流理論發展歷程

網絡流的理論和應用在不斷髮展,出現了具有增益的流、多終端流、多商品流以及網絡流的分解與合成等新課題。網絡流的應用已遍及通訊、運輸、電力、工程規劃、任務分派、設備更新以及計算機輔助設計等眾多領域。

網絡流理論常用算法

1、augment path,直譯為“增廣路徑”,其思想大致如下:
原有網絡為G,設有一輔助圖G',其定義為V(G') = V(G),E(G')初始值(也就是容量)與E(G)相同。每次操作時從Source點搜索出一條到Sink點的路徑,然後將該路徑上所有的容量減去該路徑上容量的最小值,然後對路徑上每一條邊添加或擴大反方向的容量,大小就是剛才減去的容量。一直到沒有路為止。此時輔助圖上的正向流就是最大流。
我們很容易覺得這個算法會陷入死循環,但事實上不是這樣的。我們只需要注意到每次網絡中由Source到Sink的流都增加了,若容量都是整數,則這個算法必然會結束。
尋找通路的時候可以用DFS,BFS最短路等算法。就這兩者來説,BFS要比DFS快得多,但是編碼量也會相應上一個數量級。
增廣路方法可以解決最大流問題,然而它有一個不可避免的缺陷,就是在極端情況下每次只能將流擴大1(假設容量、流為整數),這樣會造成性能上的很大問題,解決這個問題有一個複雜得多的算法,就是預推進算法。
2、push label,直譯為“預推進”算法。
3、壓入與重標記(Push-Relabel)算法
除了用各種方法在剩餘網絡中不斷找增廣路(augmenting)的Ford-Fulkerson系的算法外,還有一種求最大流的算法被稱為壓入與重標記(Push-Relabel)算法。它的基本操作有:壓入,作用於一條邊,將邊的始點的預流盡可能多的壓向終點;重標記,作用於一個點,將它的高度(也就是label)設為所有鄰接點的高度的最小值加一。Push-Relabel系的算法普遍要比Ford-Fulkerson系的算法快,但是缺點是相對難以理解。
Relabel-to-Front使用一個鏈表保存溢出頂點,用Discharge操作不斷使溢出頂點不再溢出。Discharge的操作過程是:若找不到可被壓入的臨邊,則重標記,否則對臨邊壓入,直至點不再溢出。算法的主過程是:首先將源點出發的所有邊充滿,然後將除源和匯外的所有頂點保存在一個鏈表裏,從鏈表頭開始進行Discharge,如果完成後頂點的高度有所增加,則將這個頂點置於鏈表的頭部,對下一個頂點開始Discharge。
Relabel-to-Front算法的時間複雜度是O(V^3),還有一個叫Highest Label Preflow Push的算法複雜度據説是O(V^2*E^0.5)。我研究了一下HLPP,感覺它和Relabel-to-Front本質上沒有區別,因為Relabel-to-Front每次前移的都是高度最高的頂點,所以也相當於每次選擇最高的標號進行更新。還有一個感覺也會很好實現的算法是使用隊列維護溢出頂點,每次對pop出來的頂點discharge,出現了新的溢出頂點時入隊。
Push-Relabel類的算法有一個名為gap heuristic的優化,就是當存在一個整數0k的頂點v做更新,若它小於V+1就置為V+1。 [1] 

網絡流理論應用

網絡流模型在OI(信息學競賽)中也有重要的應用,許多高端的競賽如APIO,CTSC,都非常重視選手在網絡流上的建模技巧。上述所説的最大流、最小割、最小費用最大流、最小費用流、二分圖匹配、有上下界的可行流等算法都對應着一些模型,其中劉汝佳(曾經IOI國家隊隊員)在他的白書訓練指南中第五章裏詳細的介紹了上述算法各種應用,同時也有各種習題提供建模技巧,其中有一些如拆點,加邊的技巧。但總體網絡流在信息學競賽中不重視選手的算法實現,更看重選手的數學建模能力。 [2] 
參考資料
  • 1.    林履端. 網絡流與最大流問題[J]. 福州師專學報,2000,(06):1-6.
  • 2.    趙小歡,夏靖波,付凱,李明輝. 高速網絡流頻繁項挖掘算法[J]. 計算機研究與發展,2014,(11):2458-2469.