【運(yùn)籌學(xué)中的最大流問題探究15000字（論文）】

-[4]。在一個容量網(wǎng)絡(luò)中，預(yù)流是一個正邊流的集合，對于網(wǎng)絡(luò)中的節(jié)點(diǎn)(除源點(diǎn)、匯點(diǎn)之外)，其上的流入量不小于流出量。我們把流入量大于流出量的節(jié)點(diǎn)稱為活動節(jié)點(diǎn)，把活動節(jié)點(diǎn)V上流入量-流出量的差值稱為該活動節(jié)點(diǎn)的盈余量，記為e(V)。如果一個節(jié)點(diǎn)v對每一個與之相鄰的節(jié)點(diǎn)u都以弧容量大小的流向前推進(jìn)，則說明該節(jié)點(diǎn)v達(dá)到了最大推進(jìn)。預(yù)流推進(jìn)算法是給源點(diǎn)一個足夠大（等于源點(diǎn)鄰接邊的容量之和）的流，向鄰近結(jié)點(diǎn)推進(jìn)（push)，得到了一個活動頂點(diǎn)（還沒有流出，只是流入）集合，然后將這個集合的點(diǎn)沿著路徑推進(jìn)（流出）不斷的減小盈余量（或者是回退給上一個頂點(diǎn)），直到?jīng)]有活動頂點(diǎn)為止。每次推進(jìn)的流量是邊的容量。增大路徑算法總是維持一個可行流（流出量等于流入量）：它沿著增大路徑增加流，最終得到最大流。而預(yù)流-推進(jìn)算法維持的最大流不是可行流，因?yàn)槟承╉旤c(diǎn)的流入量比流出量要大：它們通過這些頂點(diǎn)推進(jìn)(push)流，直到達(dá)到一個可行流。再用水流來說明兩者的區(qū)別：增大路徑算法相當(dāng)于查找一個所有河流，獲得每條河流的最大流量（其中流量最小作為一條河流的最大流量，否則會出現(xiàn)決堤），最后把每條河流的最大流量累加就是最大流；預(yù)流-推進(jìn)方法相當(dāng)于水庫放水的過程，即最大流相當(dāng)于從水庫以河道的最大容量向下游推進(jìn)的過程。預(yù)流推進(jìn)改進(jìn)算法主要有先進(jìn)先出預(yù)流推進(jìn)及最高標(biāo)號預(yù)流推進(jìn)算法，它們的區(qū)別是對活躍節(jié)點(diǎn)的選取方式不同，前者對活躍節(jié)點(diǎn)的處理是按列隊(duì)先進(jìn)先出的方式進(jìn)行，后者對活躍節(jié)點(diǎn)的選擇遵循最高距離標(biāo)號原則。算法偽代碼如下：

intMAXFLOW(){hights();prepare();while(!Q.empty()){u=Q.get;foreacheinG'(fromu)push(e);if(!fixed(u))reCalc(u);}}算法流程：1.給源點(diǎn)s一個足夠（等于源點(diǎn)鄰接邊的容量之和）的流，流向它的鄰近頂點(diǎn)，使它的鄰近頂點(diǎn)構(gòu)成一個活動頂點(diǎn)的集合A2.遍歷活動頂點(diǎn)集合A的每一個點(diǎn)v，對v進(jìn)行如下操作：（1）對v的每一條鄰接邊以邊容量的流向前推進(jìn)流（如果每條鄰邊都以邊容量推進(jìn)過的（達(dá)到最大推進(jìn)），則執(zhí)行（2）），并將該頂點(diǎn)加入集合A（2）若（1）操作后頂點(diǎn)v的還有盈余量(e(v)>0)，則將流量退回（逆推進(jìn)）給上一個頂點(diǎn)（流給它的頂點(diǎn)），最后將v從集合A中移除，其中退回給的上一個頂點(diǎn)就變成了活動頂點(diǎn)要進(jìn)入集合A3.直到活動頂點(diǎn)集合A為空為止，流向匯點(diǎn)t的流量就是最大流量。這里主要的難點(diǎn)就是為什么要做退回（逆推進(jìn)）的操作。用一個例子來說明即可：對于頂點(diǎn)v，它有A和B兩條路徑到達(dá)匯點(diǎn)t，v的流入量是5，向A路徑的第一個頂點(diǎn)a推進(jìn)的流量是4（c<v,a>=4），那么只能向B路徑的一個頂點(diǎn)b推進(jìn)的流量是1（這時c<v,b>=3），但是在A路徑最終只有2流向匯點(diǎn)t，出現(xiàn)了盈余量，在B路徑去沒有達(dá)到最大流量，那么應(yīng)該把A路徑的盈余量轉(zhuǎn)移到B路徑去推進(jìn)，這得靠退回（逆推進(jìn)）操作來完成。退回操作就是把盈余量逆推進(jìn)給上一個頂點(diǎn)如果該算法使用的隊(duì)列Q是標(biāo)準(zhǔn)的先進(jìn)先出隊(duì)列，那么其時間復(fù)雜度為O(n2m)。如果使用的是優(yōu)先隊(duì)列，并且規(guī)定標(biāo)號最高的點(diǎn)優(yōu)先的話，我們就得到了另一種效率更高的算法：最高標(biāo)號預(yù)流推進(jìn)算法，其時間復(fù)雜度僅為O(n2第五章 小結(jié)風(fēng)雨幾十年，網(wǎng)絡(luò)最大流的研究成果已經(jīng)非常豐富，目前解決最大流問題算法的主要包括增廣鏈算法和預(yù)流推進(jìn)算法，網(wǎng)絡(luò)最大流模型和算法在工、商、農(nóng)等各個領(lǐng)域被廣泛的應(yīng)用，在很多情況下，實(shí)際生活中遇到的很多復(fù)雜的問題，通過分析并建立數(shù)學(xué)模型，將其轉(zhuǎn)化成為最大流問題，就可以輕松找到解決的方法?，F(xiàn)如今，計(jì)算機(jī)科學(xué)技術(shù)的蓬勃發(fā)展為最大流問題開辟了新的研究領(lǐng)域，例如在圖像處理中，由于圖像與網(wǎng)絡(luò)之間存在著對應(yīng)關(guān)系，圖像處理中的圖像分割技術(shù)也可以利用最大流最小割的相關(guān)算法來解決。隨著網(wǎng)絡(luò)的規(guī)模和復(fù)雜程度的不斷增加，如何提升網(wǎng)絡(luò)最大流算法效率、降低其時間復(fù)雜度是當(dāng)今的一個具有挑戰(zhàn)性的研究內(nèi)容。本文主要講解最大流問題的Ford-Fulkerson解法?？梢哉f這是一種方法，而不是算法，因?yàn)樗哂胁煌\(yùn)行時間的幾種實(shí)現(xiàn)，主要包括Ford-Fulkerson標(biāo)號法、Edmonds-Karp修正算法、Dinic算法等。該方法依賴于三種重要思想：殘留網(wǎng)絡(luò)，增廣路徑和割，最大流問題的核心依據(jù)是Ford-Fulkerson最大流最小割定理，在這個定理的基礎(chǔ)上，衍生出許多種不同的優(yōu)秀的算法，它們各有其優(yōu)點(diǎn)，復(fù)雜度也不盡相同。由Ford和Fulkerson提出的Ford-Fulkerson標(biāo)號算法是最原始最經(jīng)典的算法，也是其他此類算法的基礎(chǔ)，現(xiàn)在一般運(yùn)籌學(xué)教科書中介紹的都是這種算法，首先其容易理解；其次其精確度也很不錯。針對該標(biāo)號算法增廣路徑選取時是任意的，而這可能會導(dǎo)致算法效率低下這一缺陷，Edmonds和Karp對其進(jìn)行了修正，利用的是廣度優(yōu)先搜索思想讓算法始終沿著最短路徑增廣，產(chǎn)生了Edmonds-Karp修正算法。而Dinic算法結(jié)合了BFS與DFS兩種策略的優(yōu)勢，兼具前兩種算法的優(yōu)點(diǎn)，算法時間復(fù)雜度大大降低，是三種算法中效率最高的?？v觀全文，本文的正文部分開始于緒論，介紹了網(wǎng)絡(luò)最大流問題的研究背景、國內(nèi)外研究成果、研究意義。接著為了讀者可以更好的理解，所以整理了本文研究內(nèi)容所需要的理論基礎(chǔ)，包括圖論的理論基礎(chǔ)以及關(guān)于最大流的一些基本概念和定義定理理論，為下文研究算法打好基礎(chǔ)。接著引出求解網(wǎng)絡(luò)最大流的增廣路徑算法，并重點(diǎn)介紹了經(jīng)典的Ford-Fulkerson標(biāo)號算法，從算法原理、求解過程、應(yīng)用舉例、C語言代碼實(shí)現(xiàn)、算法的優(yōu)點(diǎn)及缺陷幾個方面進(jìn)行了詳盡的分析。文章末還對現(xiàn)有的一些主流的求解網(wǎng)絡(luò)最大流算法進(jìn)行了介紹，不難看出，各種算法的性能是在不斷提升的，究其原因，是為了更好的適應(yīng)社會飛速發(fā)展的需要，在歷史前進(jìn)的過程中，人們不斷地發(fā)現(xiàn)問題，并對算法不斷進(jìn)行研究改進(jìn)和優(yōu)化。隨著5G時代的到來，網(wǎng)絡(luò)最大流模型的應(yīng)用范圍又將進(jìn)一步擴(kuò)大，伴隨網(wǎng)絡(luò)、計(jì)算機(jī)視覺技術(shù)的飛速發(fā)展，相信在不久的將來，網(wǎng)絡(luò)最大流問題能得到更蓬勃的發(fā)展。

參考文獻(xiàn)弗雷德里克?S?希利爾,杰拉爾德?J?利伯曼（胡運(yùn)權(quán)等譯）.運(yùn)籌學(xué)導(dǎo)論[M].北京:清華大學(xué)出版社,2007:375-381.LRFord,DRFulkerson.Maximumflowthroughanetwork.CanadianJournalofMath,1956,8(5):399-404.A.V.GoldbergandR.E.Tarjan.Anewapproachtothemaximum-flowproblem.JournaloftheACM,1988,35:921-940謝政,李建平.網(wǎng)絡(luò)算法與復(fù)雜性理論[M].國防科技大學(xué)出版社,2003趙姝,蘇建忠,劉倩倩,等.分層法求解網(wǎng)絡(luò)最大流的研究[J].計(jì)算機(jī)研究與發(fā)展,2014,(8).doi:10.7544/issn1000-1239.2014.20130204.張柏禮,王媛瑗,洪亮,等.動態(tài)網(wǎng)絡(luò)中最大流快速增量求解[J].東南大學(xué)學(xué)報(bào)（自然科學(xué)版）,2017,(3).doi:10.3969/j.issn.1001-0505.2017.03.006.章柳燕,郭春生.基于跨平臺的連續(xù)最大流圖像分割并行實(shí)現(xiàn)[J].杭州電子科技大學(xué)學(xué)報(bào),2016,(4).doi:10.13954/ki.hdu.2016.04.004.趙禮峰,嚴(yán)子恒.基于增廣鏈修復(fù)的最大流求解算法[J].計(jì)算機(jī)應(yīng)用,2015,(5).KorfRE.Depth-firstiterative-deepening:Anoptimaladmissibletreesearch[J].Artificialintelligence,1985,27(1):97-109.Beam