ZHAO Li-feng，JI Ya-bao

(College of Science,Nanjing University of Posts and Telecommunications,Nanjing 210023,China)

最大流問題的改進(jìn)最短增廣鏈算法

在最大流問題中，由于Ford-Fulkerson算法中增廣鏈選取的任意性，導(dǎo)致該算法不是有效的多項(xiàng)式算法。經(jīng)典的最短增廣鏈算法是通過在增廣過程中尋找最短增廣鏈，從而排除增廣鏈選取的任意性。但計(jì)算過程中為尋找最短增廣鏈，需要根據(jù)原網(wǎng)絡(luò)循環(huán)地構(gòu)建剩余網(wǎng)絡(luò)和剩余分層網(wǎng)絡(luò)，步驟非常繁雜。為改善以上不足，基于經(jīng)典最短增廣鏈算法，提出改進(jìn)最短增廣鏈算法。該算法的思想是：若在增廣剩余分層網(wǎng)絡(luò)中流值的過程中得到飽和弧，則刪除該弧對應(yīng)于原網(wǎng)絡(luò)中的弧，使原網(wǎng)絡(luò)得以簡化，以此可降低構(gòu)建剩余網(wǎng)絡(luò)和剩余分層網(wǎng)絡(luò)的復(fù)雜性，從而優(yōu)化最短增廣鏈算法。理論和仿真實(shí)驗(yàn)都表明，改進(jìn)算法不僅正確，而且比原算法效率更高。

最大流；最短增廣鏈；剩余網(wǎng)絡(luò)；剩余分層網(wǎng)絡(luò)

0 引 言

網(wǎng)絡(luò)最大流問題是經(jīng)典的組合優(yōu)化問題，是網(wǎng)絡(luò)流理論中的重要組成部分。最大流問題在現(xiàn)實(shí)生活中以及眾多科學(xué)領(lǐng)域中都有著廣泛的應(yīng)用，例如常見的交通網(wǎng)絡(luò)以及通信網(wǎng)絡(luò)都可以轉(zhuǎn)化成最大流問題來解決。因此網(wǎng)絡(luò)流的研究具有重要的現(xiàn)實(shí)意義，它可以優(yōu)化結(jié)構(gòu)、提高效率、發(fā)揮最大的社會(huì)和經(jīng)濟(jì)效益。

對網(wǎng)絡(luò)最大流理論的研究已經(jīng)取得了大量成果，并且也形成了完善的理論體系。最大流問題的經(jīng)典算法可以分為增載軌類算法和預(yù)留推進(jìn)類算法[1]。在增載軌類算法中有1956年發(fā)現(xiàn)的Ford-Fulkerson算法[2]和Dinic等提出的改進(jìn)Ford-Fulkerson算法(每次都沿著最短增廣鏈增廣)。Edmonds和Karp[3]提出利用剩余網(wǎng)絡(luò)尋找最短增廣鏈的最短增廣鏈算法。Dinic[4]構(gòu)建了阻塞流和分層網(wǎng)以設(shè)計(jì)最短增廣鏈算法。預(yù)留推進(jìn)類算法中包括由Goldberg和Tarjan提出的預(yù)流推進(jìn)算法[5]。在這些研究之后又有一些針對特殊網(wǎng)絡(luò)而提出的最大流問題的算法[6-12]，包括對于稀疏網(wǎng)絡(luò)、小容量網(wǎng)絡(luò)、無向網(wǎng)絡(luò)、點(diǎn)邊有容量約束網(wǎng)絡(luò)、節(jié)點(diǎn)環(huán)流型網(wǎng)絡(luò)、單位容量網(wǎng)絡(luò)等，文獻(xiàn)[13-14]對經(jīng)典的最大流算法進(jìn)行了研究。

對于Dinic等基于最短增廣鏈提出的最短增廣鏈算法，需要循環(huán)構(gòu)建剩余網(wǎng)絡(luò)和分層網(wǎng)絡(luò)，這個(gè)過程往往比較復(fù)雜。

文中在增廣過程中刪除某些已經(jīng)不再增廣的弧，從而簡化了原網(wǎng)絡(luò)，減少了構(gòu)建剩余網(wǎng)絡(luò)和分層網(wǎng)絡(luò)的復(fù)雜性，優(yōu)化了最短增廣鏈算法。

1 相關(guān)知識(shí)

1.1 最大流問題線性規(guī)劃模型

模型如下：

1.2 剩余網(wǎng)絡(luò)

給定一個(gè)帶發(fā)點(diǎn)vs和收點(diǎn)vt的容量網(wǎng)絡(luò)N=(V,vs,vt,E,C)及N上的可行流f，定義

A(f)=A+(f)∪A-(f)

稱cij(f)為弧(vi,vj)關(guān)于f的剩余容量。于是得到一個(gè)帶發(fā)點(diǎn)vs和收點(diǎn)vt的容量網(wǎng)絡(luò)N(f)=(V,vs,vt,A(f),cf)，稱之為N關(guān)于f的剩余網(wǎng)絡(luò)。

1.3 剩余分層網(wǎng)絡(luò)

對于N的關(guān)于f的剩余網(wǎng)絡(luò)N(f)=(V,vs,vt,A(f),cf)，定義N(f)的子網(wǎng)絡(luò)EN(f)=(V'(f),A'(f),cf)如下：

V'(f)={vt}∪{vi∈V|h(vi)

A'(f)={(vi,vj)∈A(f)|h(vj)=h(vi)+1

EN(f)稱為N關(guān)于f的剩余分層網(wǎng)絡(luò)。

2 改進(jìn)的最短增廣鏈算法

2.1 最短增廣鏈算法步驟

在網(wǎng)絡(luò)N=(V,vs,vt,E,C)中，從任意一個(gè)可行流f(一般可取零流)開始，執(zhí)行以下步驟：

步驟1：構(gòu)造剩余網(wǎng)絡(luò)N(f)并對其分層，構(gòu)造剩余分層網(wǎng)絡(luò)EN(f)。若EN(f)中y得不到標(biāo)號(hào)，結(jié)束，f就是最大流，否則轉(zhuǎn)步驟2。

步驟2：求EN(f)中vs→vt的一條路p，并沿路p增加流得到更大的流，并去掉EN(f)中所有飽和弧。

步驟3：求EN(f)中vs→vt的一條路p，若不存在則返回步驟1；否則返回步驟2。

2.2 改進(jìn)算法思想

在最短增廣鏈算法步驟3中，當(dāng)EN(f)中不存在vs→vt路時(shí)，就返回步驟1，在步驟1中重新構(gòu)造剩余分層網(wǎng)絡(luò)。在這個(gè)過程中發(fā)現(xiàn)，對于步驟2中增廣流后而得到的飽和弧在步驟1中的剩余分層網(wǎng)絡(luò)并不存在，即最短增廣鏈算法步驟2中增廣流后而得到的飽和弧在以后的增廣過程中這條弧的流值不可能增加或減少。

于是，在改進(jìn)算法中，只需要?jiǎng)h去原網(wǎng)絡(luò)中的這些飽和弧，便可以簡化步驟1中重新構(gòu)造網(wǎng)絡(luò)的過程。

2.3 改進(jìn)算法正確性和時(shí)間復(fù)雜度

定理1：對于最短增廣鏈上增廣流值后而得到的飽和弧，在以后的算法進(jìn)程中這條弧上的流值不可能再增加或減少。

證明：對這些飽和弧首先要構(gòu)造剩余網(wǎng)絡(luò)，再對其進(jìn)行分層，最后構(gòu)造出剩余分層網(wǎng)絡(luò)。在剩余分層網(wǎng)絡(luò)中尋找vs→vt路，對vs→vt路進(jìn)行圖中各個(gè)頂點(diǎn)的層次只可能增加或不變而不可能減少。已知在剩余分層網(wǎng)絡(luò)中尋找的vs→vt路對應(yīng)于原網(wǎng)絡(luò)的增廣鏈，現(xiàn)假設(shè)vs→vt路中的某條弧e對應(yīng)于原網(wǎng)絡(luò)增廣鏈中的前向弧，則實(shí)際情況是對弧e增加流值，當(dāng)增加流值未達(dá)到飽和時(shí)則在剩余分層網(wǎng)絡(luò)中與弧e關(guān)聯(lián)的節(jié)點(diǎn)的層次沒有改變，若增加流值達(dá)到飽和時(shí)與在剩余分層網(wǎng)絡(luò)中與弧e關(guān)聯(lián)的節(jié)點(diǎn)層次就會(huì)增加。再假設(shè)vs→vt路中對應(yīng)于原網(wǎng)絡(luò)中的后向弧，則實(shí)際情況是對弧e減少流值，當(dāng)減少流值未達(dá)到飽和時(shí)則在剩余分層網(wǎng)絡(luò)中與弧e關(guān)聯(lián)的節(jié)點(diǎn)的層次沒有改變，若減少流值達(dá)到飽和時(shí)與在剩余分層網(wǎng)絡(luò)中與弧e關(guān)聯(lián)的節(jié)點(diǎn)層次就會(huì)增加。于是增流達(dá)到飽和的弧在重新構(gòu)造剩余分層網(wǎng)絡(luò)時(shí)不滿足頂點(diǎn)層次要求，故不存在于重新構(gòu)造的剩余分層網(wǎng)絡(luò)中。即這條弧不可能存在于以后的增廣過程中。

定理2：改進(jìn)算法時(shí)間復(fù)雜度為O(n2m)。

證明：設(shè)容量網(wǎng)絡(luò)D的頂點(diǎn)數(shù)為n，弧數(shù)為m。步驟1中最多執(zhí)行n-1次，又由廣探法知，每次構(gòu)造剩余分層網(wǎng)絡(luò)的復(fù)雜性為O(m)。步驟2和步驟3中最多增廣m次，而每次增廣的計(jì)算量為O(n)，所以改進(jìn)的最短增廣鏈算法的算法復(fù)雜度為O(nm)+O(n2m)=O(n2m)。

2.4 改進(jìn)算法步驟

步驟1：構(gòu)造剩余網(wǎng)絡(luò)N(f)并對其分層，構(gòu)造剩余分層網(wǎng)絡(luò)EN(f)。若EN(f)中y得不到標(biāo)號(hào)，結(jié)束，f就是最大流，否則轉(zhuǎn)步驟2。

步驟2：求EN(f)中vs→vt的一條路p，并沿路p增加流得到更大的流，并去掉EN(f)中所有飽和弧。

步驟3：求EN(f)中vs→vt的一條路p，若不存在，則將在步驟2中達(dá)到飽和的弧在原網(wǎng)絡(luò)中刪除，再返回步驟1；否則返回步驟2。

3 數(shù)值實(shí)例

例：求圖1中網(wǎng)絡(luò)最大流。

圖1 原網(wǎng)絡(luò)圖

圖中，弧上的數(shù)字表示弧容量，初始流為零流。首先通過剩余分層網(wǎng)絡(luò)，最短增廣鏈為3條弧。通過步驟1～3得到增廣流值如圖2所示。流值為7，在增廣流值的過程中弧(v2,v3)和弧(v1,v4)達(dá)到飽和，增廣流值后EN(f)中不存在x→y的一條路p，即原網(wǎng)絡(luò)中不存在只有3條弧的增廣鏈。

圖2 增廣流值后的網(wǎng)絡(luò)圖

于是返回步驟1，在原網(wǎng)絡(luò)中刪除弧(v2,v3)和(v1,v2)，再構(gòu)建剩余分層網(wǎng)絡(luò)，見圖3。接著進(jìn)行步驟2和步驟3，此時(shí)最短增廣鏈v1→v2→v4→v5→v6含有4條弧。

圖3 刪除飽和弧(v2,v3)、(v1,v2)

增廣流值后流值為8。在增廣過程中弧(v4,v5)達(dá)到飽和，增廣流值后EN(f)中不存在x→y的一條路p，即原網(wǎng)絡(luò)中不存在只有4條弧的增廣鏈。再返回步驟1在原網(wǎng)絡(luò)中刪除弧(v2,v3)、(v1,v4)和(v4,v5)，再構(gòu)建剩余分層網(wǎng)絡(luò)，見圖4，此時(shí)剩余分層網(wǎng)絡(luò)中v6得不到標(biāo)號(hào)。于是圖4即為最大流，流值為8。

圖4 刪除飽和弧(v1,v4)后的剩余分層網(wǎng)絡(luò)圖

4 算法的仿真與比較

文中MATLAB仿真實(shí)驗(yàn)是在網(wǎng)絡(luò)規(guī)模為500,1 500,2 500和3 500個(gè)節(jié)點(diǎn)的隨機(jī)網(wǎng)絡(luò)上對經(jīng)典算法和改進(jìn)算法的運(yùn)行時(shí)間進(jìn)行比較(見表1)，針對每個(gè)規(guī)模的網(wǎng)絡(luò)均進(jìn)行十次實(shí)驗(yàn)求平均值。隨機(jī)網(wǎng)絡(luò)是由經(jīng)典BA無標(biāo)度網(wǎng)絡(luò)的方法隨機(jī)生成。

表1 兩種算法所得到的最大流值

通過表1可以看出，兩種算法同樣都能求解出最大流，并且都能求出網(wǎng)絡(luò)中每條弧中的具體流值(由于網(wǎng)絡(luò)比較大，具體流值情況沒有寫入)。

圖5的實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法相對于原算法節(jié)省了運(yùn)行時(shí)間，這與之前的分析吻合,并且節(jié)點(diǎn)數(shù)越多，改進(jìn)算法效率越高。

圖5 算法運(yùn)行時(shí)間對比

5 結(jié)束語

在網(wǎng)絡(luò)最大流問題中最短鏈增廣鏈算法是經(jīng)典算法。該算法是對2F算法的改進(jìn)，是一種強(qiáng)多項(xiàng)式算法，算法效率高。該算法對2F算法進(jìn)行的改進(jìn)是為了避免增廣鏈選取的任意性，每次增廣都通過構(gòu)建剩余網(wǎng)絡(luò)和分層網(wǎng)絡(luò)來尋找最短增廣鏈，從而使得算法的復(fù)雜性不再取決于網(wǎng)絡(luò)容量，而僅僅取決于網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)和邊數(shù)。但是構(gòu)建剩余網(wǎng)絡(luò)和分層網(wǎng)絡(luò)均比較復(fù)雜。文中在算法循環(huán)進(jìn)行的過程中不斷簡化需要構(gòu)建的剩余網(wǎng)絡(luò)和層次網(wǎng)絡(luò)，從而減少了構(gòu)建剩余網(wǎng)絡(luò)和分層網(wǎng)絡(luò)的復(fù)雜性。

[1] 張憲超，陳國良，萬穎瑜.網(wǎng)絡(luò)最大流問題研究進(jìn)展[J].計(jì)算機(jī)研究與發(fā)展，2003,40(9)：1281-1292.

[2]FordLR,FulkersonDR.Maximumflowthroughanetwork[J].CanadianJournalofMath,1956,8(5):399-404.

[3]EdmondsJ,KarpRM.Theoreticalimprovementsinalgorithmicefficiencyfornetworkflowproblems[J].JournaloftheAssociationforComputingMachinery,1972,19(2):248-264.

[4]DinicEA.Algorithmsforsolutionofaproblemofmaximumflowinnetworkswithpowerestimation[J].SovietMathematicsDoklady,1970,11(8):1277-1280.

[5] 謝 政.網(wǎng)絡(luò)算法與復(fù)雜性理論[M].長沙:國防科技大學(xué)出版社，2003.

[6] 趙禮峰，嚴(yán)子恒.基于增廣鏈修復(fù)的最大流求解算法[J].計(jì)算機(jī)應(yīng)用，2015,35(5)：1246-1249.

[7] 張憲超，陳國良.小容量網(wǎng)絡(luò)上的最大流算法[J].計(jì)算機(jī)研究與發(fā)展，2001,38(2)：194-198.

[8] 邱偉星，王以凡，沈金龍.一個(gè)求無向網(wǎng)絡(luò)最大流的算法[J].南京郵電學(xué)院學(xué)報(bào)，1997，14(4)：170-172.

[9] 郭 強(qiáng).無向網(wǎng)絡(luò)最大流問題研究[J].計(jì)算機(jī)工程與應(yīng)用，2005，41(9)：76-78.

[10] 張憲超，江 賀，陳國良.節(jié)點(diǎn)和邊都有容量的有向平面網(wǎng)絡(luò)中的最小截和最大流[J].計(jì)算機(jī)學(xué)報(bào)，2006,29(4)：544-551.

[11] 徐光聯(lián)，孫文新.節(jié)點(diǎn)環(huán)流網(wǎng)絡(luò)中的最大流算法[J].應(yīng)用科技，2014,41(1):48-53.

[12] 張憲超，江 賀，劉馨月，等.無向平面單位容量網(wǎng)絡(luò)中的最大流[J].計(jì)算機(jī)研究與發(fā)展,2008，45(S1):40-42.

[13] 孫澤宇，丁國強(qiáng)，程志謙.網(wǎng)絡(luò)最大流求解算法的研究[J].微計(jì)算機(jī)信息,2010，26(1-3):143-145.

[14] 孫澤宇.基于標(biāo)號(hào)法求解網(wǎng)絡(luò)最大流算法的研究[J].甘肅聯(lián)合大學(xué)學(xué)報(bào)：自然科學(xué)版,2009,23(4):64-66.

趙禮峰，紀(jì)亞寶

(南京郵電大學(xué) 理學(xué)院，江蘇 南京 210023)

Improved Shortest Augmenting Chain Algorithm of Maximum Flow

In maximum flow problem,since the Ford-Fulkerson algorithm chooses arbitrarily augmented chain,as a result the algorithm is not a valid polynomial one.Classical shortest augmenting chain algorithm is to find the shortest augmenting chain in the augmented chain process,thus eliminating the arbitrary of augmented chain selection.But in calculation process for finding the shortest augmenting chain,needing to build the remaining network and the remaining surplus hierarchical network based on the original network cycle,its step is very complicated.In order to improve the above problems,based on the classical shortest augmenting chain algorithm,an improved one for the shortest augmenting chain is put forward.The idea is that if the saturated arc is obtained in flow value processing augmented remaining hierarchical network,then the original arc corresponding to the network is deleted,making the original network simplified in order to reduce the complexity of constructing remaining network and the remaining layered network and optimize the shortest augmenting chain algorithm.The theory and simulation show that the improved algorithm is not only correct,but also higher in efficiency than the original algorithm.

maximum flow;shortest augmenting chain;remaining network;remaining layered network

2015-12-02

2016-03-09

時(shí)間：2016-08-01

國家自然科學(xué)基金青年基金項(xiàng)目(61304169)

趙禮峰(1959-)，男，教授，碩士研究生導(dǎo)師，研究方向?yàn)閳D論及其在通信中的應(yīng)用；紀(jì)亞寶(1990-)，男，碩士研究生，研究方向?yàn)閳D論及其在通信中的應(yīng)用。

http://www.cnki.net/kcms/detail/61.1450.TP.20160801.0907.044.html

TP301.6

A

1673-629X(2016)08-0052-03

10.3969/j.issn.1673-629X.2016.08.011

ZHAO Li-feng，JI Ya-bao

(College of Science,Nanjing University of Posts and Telecommunications,Nanjing 210023,China)