邵麗萍，趙禮峰

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

0 引 言

網(wǎng)絡(luò)最大流問(wèn)題是一個(gè)屬于圖論和運(yùn)籌學(xué)的問(wèn)題[1-3]。最初Fulkerson等[4]在處理最大流問(wèn)題時(shí)，運(yùn)用了圖論的方法。后來(lái)，在1956年Ford-Fulkerson給出了求最大流問(wèn)題的標(biāo)號(hào)算法[5]；Dinic(1970),Edmonds和Karp(1972)獨(dú)立提出了改進(jìn)Ford-Fulkerson算法的思想：每次都沿最短(即弧數(shù)最少的)增廣鏈進(jìn)行增廣，即最短增廣鏈算法[6-7]；Karzanov(1974)提出了預(yù)流的概念，基于預(yù)流的概念，進(jìn)一步提出了預(yù)流推進(jìn)的算法；Cherkassky提出了最高標(biāo)號(hào)預(yù)流推進(jìn)算法[8]。這些經(jīng)典的算法是研究大規(guī)模網(wǎng)絡(luò)的基礎(chǔ)。在這些研究之后，很多學(xué)者針對(duì)特殊網(wǎng)絡(luò)或經(jīng)典算法的改進(jìn)方面，提出了許多最大流問(wèn)題的算法[9-16]。

針對(duì)Ford-Fulkerson算法存在標(biāo)號(hào)的繁瑣、增廣鏈尋找的任意性和運(yùn)行效率慢的缺陷，文中提出了一種基于寬度優(yōu)先的網(wǎng)絡(luò)最大流求解算法。該算法利用寬度優(yōu)先搜索原理，尋找一條包含剩余容量最大的弧的最短增廣鏈，且刪除飽和弧后，運(yùn)用了修復(fù)最短增廣鏈的方法[17]，簡(jiǎn)化了網(wǎng)絡(luò)且避免了反復(fù)尋找新的增廣鏈，達(dá)到了優(yōu)化Ford-Fulkerson算法的目的。

1 基本概念

1.1 最大流的模型

定義1[6]：定義一個(gè)含容量的網(wǎng)絡(luò)，記為G=(V,A,c)，定義流fst為網(wǎng)絡(luò)G=(V,A,c)中從始點(diǎn)s到終點(diǎn)t的流，如果fst滿足下列條件：

則fst是網(wǎng)絡(luò)G的一個(gè)可行流。在所有滿足條件的可行流中，流量最大的可行流被稱為最大流，記作fmax。上式中滿足f(i,j)

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

剩余網(wǎng)絡(luò)[5-6](residual network)是指在一張含可行流的容量網(wǎng)絡(luò)圖中所有非飽和弧及所有節(jié)點(diǎn)的集合，亦可用反向弧在網(wǎng)絡(luò)中標(biāo)記出飽和弧及當(dāng)前流。記剩余網(wǎng)絡(luò)為U(f)=(V,A(f),c(f))，需滿足兩個(gè)關(guān)系：

(1)?(i,j)∈A(G)，若f(i,j)

(2)?(i,j)∈A(G)，若f(i,j)>0，則CU(j,i)=f(i,j)。

2 一種改進(jìn)的最大流算法

2.1 算法思想

改進(jìn)算法的主要思想是：找一條從始點(diǎn)vs到終點(diǎn)vt包含剩余容量最大的弧的最短增廣鏈P，然后對(duì)其不斷修復(fù)，減少重新尋找可增廣鏈的執(zhí)行次數(shù)。首先，在容量網(wǎng)絡(luò)G=(V,A,c)中，取任意一個(gè)可行流f(一般取零流)。在容量網(wǎng)絡(luò)G=(V,A,c)中，使用寬度優(yōu)先原則，搜索一條從始點(diǎn)vs到終點(diǎn)vt包含剩余容量最大的弧的最短增廣鏈P，然后在最短增廣鏈P上刪除飽和弧和調(diào)整相應(yīng)弧的容量。進(jìn)一步是增廣鏈修復(fù)的過(guò)程，搜索滿足條件的節(jié)點(diǎn)，找到一條包含刪除弧兩個(gè)端點(diǎn)的新的增廣鏈。具體修復(fù)的過(guò)程是：取距離始點(diǎn)vs最近的刪除弧(vs,vm)及距離終點(diǎn)vt最近的刪除弧(vq,vn)，得到斷點(diǎn)為vs、vn，尋找包含vs到vn的一條路徑，且修復(fù)的最短增廣鏈包含剩余容量最大的弧，如圖1所示。若找不到滿足條件的節(jié)點(diǎn)，則意味著修復(fù)結(jié)束。在剩余容量網(wǎng)絡(luò)中重新找一條包含剩余容量最大的弧的最短增廣鏈，重復(fù)以上操作。若在剩余容量網(wǎng)絡(luò)中，找不到從始點(diǎn)vs到終點(diǎn)vt包含剩余容量最大的弧的最短增廣鏈時(shí)，則整個(gè)算法終止。

圖1 增廣鏈的修復(fù)過(guò)程

2.2 算法步驟

在容量網(wǎng)絡(luò)G=(V,A,c)中，開始于任意一個(gè)可行流f(一般取零流)，執(zhí)行以下步驟：

Step1：從始點(diǎn)vs出發(fā)，找一條從始點(diǎn)vs到終點(diǎn)vt包含剩余容量最大的弧的最短增廣鏈P(寬度優(yōu)先原則)。如果不存在，結(jié)束，f就是G的最大流；

Step2：求出該最短增廣鏈P上各弧容量的最小值δ。刪除飽和弧，并在最短增廣鏈P的各弧上減去δ；

Step3：修復(fù)增廣鏈P，轉(zhuǎn)Step2，如果不能修復(fù)，則轉(zhuǎn)Step1。

2.3 算法可行性分析

在新算法的操作過(guò)程中，刪除包含剩余容量最大的弧的最短增廣鏈上的飽和弧，對(duì)最大流的求解并沒(méi)有影響。因?yàn)樵谝院髨?zhí)行算法的過(guò)程中，這條弧的容量不可能減少或增加[18]，只是簡(jiǎn)化了重新尋找可增廣鏈的過(guò)程，且在剩余容量網(wǎng)絡(luò)修復(fù)過(guò)程中，避免了重復(fù)搜索相關(guān)的弧。設(shè)容量網(wǎng)絡(luò)G=(V,A,c)有m條弧，每次增廣后，至少刪除一條飽和弧，則最多經(jīng)過(guò)m次增廣后，網(wǎng)絡(luò)G=(V,A,c)中就不存在從始點(diǎn)vs到終點(diǎn)vt的可增廣鏈，此時(shí)算法終止，即新算法不會(huì)陷入死循環(huán)。

2.4 算法復(fù)雜度分析

在容量網(wǎng)絡(luò)G=(V,A,c)中，設(shè)節(jié)點(diǎn)數(shù)為n，弧數(shù)為m。在Step1中執(zhí)行一次寬度優(yōu)先搜索的復(fù)雜度為O(m)，且沿寬度優(yōu)先搜索尋找包含剩余容量最大的弧的最短增廣鏈P時(shí)，步數(shù)不超過(guò)O(n)。在執(zhí)行Step2時(shí)，每次至少刪除一條飽和弧，故最多執(zhí)行m次尋找包含剩余容量最大的弧的最短增廣鏈，所以新算法的時(shí)間復(fù)雜度為：O(mn2)+O(m2)=O(mn2)。

新算法在實(shí)際的操作過(guò)程中，降低了時(shí)間復(fù)雜度。由于尋找包含剩余容量最大的弧的最短增廣鏈、刪除飽和弧及修復(fù)增廣鏈，都會(huì)減少下一步尋找包含剩余容量最大的弧的最短增廣鏈的搜索次數(shù)。

3 數(shù)值實(shí)例與分析

例：如圖2所示，求從始點(diǎn)vs到終點(diǎn)vt的網(wǎng)絡(luò)最大流。其中每條弧旁的數(shù)字表示容量。

圖2 容量網(wǎng)絡(luò)G

解:(1)在容量網(wǎng)絡(luò)G=(V,A,c)中，將初始可行流取為零流f；

(2)從始點(diǎn)vs出發(fā)，找一條包含剩余容量最大的弧的最短增廣鏈。選取最短增廣鏈P=vsv2v4vt，δ=min{5,6,6}=5，將δ的值加到流值f上，得到新的可行流，仍記為f。刪除飽和弧(vs,v2)及(v2,v4)，并在最短增廣鏈P的各弧上減去δ，如圖3所示。

圖3 刪除飽和弧后的網(wǎng)絡(luò)圖

(3)修復(fù)最短增廣鏈P，其中vs，v4為斷點(diǎn)，修復(fù)可得P=vsv1v4vt為最短增廣鏈，δ=min{5,5,1}=1，將δ的值加到流值f上，得到新的可行流，仍記為f。刪除飽和弧(v4,vt)，并在最短增廣鏈P的各弧上減去δ，如圖4所示。

圖4 修復(fù)后刪除飽和弧的網(wǎng)絡(luò)圖

(4)修復(fù)最短增廣鏈P，其中v4，vt為斷點(diǎn)，修復(fù)可得P=vsv1v4v5vt為最短增廣鏈，δ=min{4,4,4,6}=4，將δ的值加到流值f上，得到新的可行流，仍記為f。刪除飽和弧(vs,v1)，(v1,v4)及(v4,v5)，并在最短增廣鏈P的各弧上減去δ。

(5)此時(shí)在容量網(wǎng)絡(luò)G=(V,A,c)中，不存在從始點(diǎn)vs到終點(diǎn)vt的可增廣鏈。于是可得圖5所示的最大流f，流值為10。

圖5 最大流f

注：用該算法只需一次尋找增廣鏈，兩次修復(fù)增廣鏈。若用Ford-Fulkerson算法，則需要三次尋找增廣鏈，兩次修復(fù)增廣鏈的過(guò)程才能得到最大流值10，過(guò)程復(fù)雜，空間占用大，運(yùn)行時(shí)間長(zhǎng)，這里就不給出詳細(xì)的求解過(guò)程。

4 算法的仿真與比較

將該算法在MATLAB2012b軟件中進(jìn)行仿真實(shí)驗(yàn)。仿真實(shí)驗(yàn)所采用的隨機(jī)網(wǎng)絡(luò)是由BA無(wú)標(biāo)度網(wǎng)絡(luò)的方法隨機(jī)生成的，仿真實(shí)驗(yàn)的網(wǎng)絡(luò)規(guī)模設(shè)為500,1 000,1 500,2 000,2 500,3 000,3 500個(gè)節(jié)點(diǎn)，且針對(duì)給出的網(wǎng)絡(luò)規(guī)模均進(jìn)行五次仿真實(shí)驗(yàn)求平均值。在這樣的仿真條件下，利用寬度優(yōu)先原則對(duì)Ford-Fulkerson算法與文中算法進(jìn)行平均運(yùn)行時(shí)間的比較，如圖6所示。

圖6 平均運(yùn)行時(shí)間的比較曲線

由圖6可以得到，在對(duì)BA無(wú)標(biāo)度網(wǎng)絡(luò)進(jìn)行最大流求解過(guò)程中，在相同的網(wǎng)絡(luò)規(guī)模下，文中算法要比Ford-Fulkerson算法所用的運(yùn)行時(shí)間短，這與之前的分析相吻合。

5 結(jié)束語(yǔ)

最大流問(wèn)題是具有廣泛應(yīng)用的經(jīng)典組合優(yōu)化問(wèn)題，文中是在Ford-Fulkerson算法的基礎(chǔ)上，提出了一種基于寬度優(yōu)先的網(wǎng)絡(luò)最大流求解算法。該算法避免了標(biāo)號(hào)的過(guò)程，并且借助寬度優(yōu)先搜索原理、尋找包含剩余容量最大的弧的最短增廣鏈、刪除飽和弧及增廣鏈修復(fù)的方法，把復(fù)雜的網(wǎng)絡(luò)簡(jiǎn)單化，計(jì)算量也得到了降低，使整個(gè)算法的執(zhí)行效率得以提高。通過(guò)數(shù)值實(shí)例驗(yàn)證了該算法的簡(jiǎn)便性、實(shí)用性，且仿真實(shí)驗(yàn)說(shuō)明了該算法的運(yùn)行速率要比Ford-Fulkerson算法快。