邵麗萍，趙禮峰

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

0 引 言

最大流問題是圖論領(lǐng)域中的重要問題之一，該問題有很直觀的現(xiàn)實(shí)背景，如在交通運(yùn)輸網(wǎng)絡(luò)中的貨物運(yùn)輸、車輛限行，生產(chǎn)制造中的制造工具，通信網(wǎng)絡(luò)中包的路由選擇，電網(wǎng)系統(tǒng)的電流等問題[1-4]都可用最大流模型來描述。因此對最大流算法研究有重要意義。

到目前為止，對最大流問題的研究已有50多年的歷史，并且形成了一套完整的理論體系。針對最大流問題主要有兩類算法，即增載軌算法和預(yù)流推進(jìn)算法。經(jīng)典的增載軌算法有Ford-Fulkerson標(biāo)號算法[5]、最短增廣鏈算法[6]、最短增載軌算法[7]等。經(jīng)典的預(yù)流推進(jìn)算法有Karzanov的分層阻塞流算法[8]、Cher-kassky的最高標(biāo)號預(yù)流推進(jìn)算法[9]等。其中增載軌算法是沿路徑進(jìn)行推進(jìn)的，預(yù)流推進(jìn)算法是沿邊進(jìn)行推進(jìn)并把多余部分返回。增載軌算法因計算過程簡單而應(yīng)用廣泛。除了以上這些最大流問題的經(jīng)典算法，許多學(xué)者也提出了改進(jìn)的最大流算法[10-12]。如今，這些算法是研究大規(guī)模網(wǎng)絡(luò)的基礎(chǔ)。

在增載軌算法中，最短增廣鏈算法應(yīng)用廣泛，它是通過給定的初始可行流在分層剩余網(wǎng)絡(luò)上沿最短路徑進(jìn)行增廣流值，同時不斷地更新分層剩余網(wǎng)絡(luò)和最大流流值，直至終點(diǎn)得不到標(biāo)號為止。雖然最短增廣鏈算法排除了增廣鏈選取的任意性，但在實(shí)際應(yīng)用中，效率并不是很高。所以，文中提出了一種改進(jìn)算法，刪除原容量網(wǎng)絡(luò)中沒有起作用的弧，并且分層剩余網(wǎng)絡(luò)刪除飽和弧時，刪除原容量網(wǎng)絡(luò)中對應(yīng)的弧，避免產(chǎn)生回溯現(xiàn)象，簡化尋找可增廣鏈的過程，以提高算法效率。

1 基本概念

1.1 最大流模型

定義一個含容量的網(wǎng)絡(luò)[13]，記為G=(V,A,c)，其中V={v1,v2,…,vn}，A={(vi,vj)|i,j∈V}，弧(vi,vj)稱為節(jié)點(diǎn)vi的出弧，同時也稱為節(jié)點(diǎn)vj的入弧，并且稱vi為vj的入鄰點(diǎn)，vj為vi的出鄰點(diǎn)，定義流fst為網(wǎng)絡(luò)G=(V,A,c)中從始點(diǎn)s到終點(diǎn)t的流，如果fst滿足下列條件：

(1)

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

1.2 廣探法(廣度優(yōu)先搜索)

廣度優(yōu)先搜索[14]是生成分層網(wǎng)絡(luò)、尋找最短增廣鏈與構(gòu)造距離標(biāo)號函數(shù)的基礎(chǔ)，節(jié)點(diǎn)采用先進(jìn)先出的遍歷方式，其算法步驟如下：

Step1：在包含始點(diǎn)vs終點(diǎn)vt的容量網(wǎng)絡(luò)G=(V,A,c)中，始點(diǎn)vs記為標(biāo)號未檢查，令h(vs)=0，ls=-1。

Step2：若所有已標(biāo)號節(jié)點(diǎn)已檢查完，轉(zhuǎn)Step4；若存在未檢查的已標(biāo)號節(jié)點(diǎn)，找到最先標(biāo)號的節(jié)點(diǎn)vi，轉(zhuǎn)Step3。

Step3：考察vi的所有出弧(vi,vj)，若vj未標(biāo)號，將vj記為未檢查已標(biāo)號，且令h(vj)=h(vi)+1，lj=i；若vj已標(biāo)號則不做處理；若vi的出弧全部考察完，則節(jié)點(diǎn)vi記為已檢查，轉(zhuǎn)Step2。

Step4：算法終止，h(vi)為容量網(wǎng)絡(luò)G=(V,A,c)中最短(vs,vt)路的長度。

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

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

由剩余網(wǎng)絡(luò)的定義及廣度優(yōu)先搜索算法，可以定義剩余網(wǎng)絡(luò)U(f)=(V,A(f),c(f))的一個子網(wǎng)絡(luò)AG(f)=(V',A'(f),c(f))，如下：

(2)

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

1.4 BA無標(biāo)度網(wǎng)絡(luò)

BA無標(biāo)度網(wǎng)絡(luò)[15-16]被用來模擬不斷增長的網(wǎng)絡(luò)節(jié)點(diǎn)的無標(biāo)度網(wǎng)絡(luò)模型，其創(chuàng)建過程如下：

(1)開始于一個包括m0個節(jié)點(diǎn)的網(wǎng)絡(luò)，每次新增一個節(jié)點(diǎn)，都要相應(yīng)地連接到m(m

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

2.1 最短增廣鏈算法步驟

輸入：原始容量網(wǎng)絡(luò)G=(V,A,c)和始點(diǎn)vs終點(diǎn)vt，節(jié)點(diǎn)數(shù)n，弧數(shù)m；

輸出：容量網(wǎng)絡(luò)的最大流f。

Step1：在原始容量網(wǎng)絡(luò)G=(V,A,c)中，取零流f作為初始可行流，根據(jù)f構(gòu)造網(wǎng)絡(luò)G的剩余網(wǎng)絡(luò)U(f)，并利用廣探法對剩余網(wǎng)絡(luò)U(f)進(jìn)行分層，進(jìn)而求出分層剩余網(wǎng)絡(luò)AG(f)。若在AG(f)中終點(diǎn)vt得不到標(biāo)號，結(jié)束算法，f為容量網(wǎng)絡(luò)的最大流，否則轉(zhuǎn)Step2。

Step2：求分層剩余網(wǎng)絡(luò)AG(f)中vs→vt的一條最短路p，沿路p增加流值，并刪除AG(f)中所有的飽和弧。

Step3：求分層剩余網(wǎng)絡(luò)AG(f)中vs→vt的一條最短路p，若不存在，則轉(zhuǎn)Step1；否則轉(zhuǎn)Step2。

2.2 算法思想

在尋找最短增廣鏈的過程中，經(jīng)常出現(xiàn)需要遍歷沒有起作用的弧，使得算法效率降低。針對這種情況，對最短增廣鏈算法進(jìn)行兩處改進(jìn)。第一處在Step1之前，先刪除原容量網(wǎng)絡(luò)中沒有起作用的弧，簡化Step1中構(gòu)造剩余網(wǎng)絡(luò)及分層剩余網(wǎng)絡(luò)過程。第二處在Step2中刪除AG(f)中所有飽和弧后，同時刪去原容量網(wǎng)絡(luò)中對應(yīng)的弧，簡化Step1中重新構(gòu)造網(wǎng)絡(luò)的過程。

2.3 算法步驟

Step1：遍歷原始容量網(wǎng)絡(luò)G=(V,A,c)中除了始點(diǎn)終點(diǎn)的其余節(jié)點(diǎn)，判斷其是否有出弧，若沒有刪除vi的所有入弧。

Step2：取零流f作為初始可行流，根據(jù)f構(gòu)造網(wǎng)絡(luò)G的剩余網(wǎng)絡(luò)U(f)，并利用廣探法對剩余網(wǎng)絡(luò)U(f)進(jìn)行分層，進(jìn)而求出分層剩余網(wǎng)絡(luò)AG(f)。若在AG(f)中終點(diǎn)vt得不到標(biāo)號，結(jié)束算法，f為容量網(wǎng)絡(luò)的最大流，否則轉(zhuǎn)Step3。

Step3：求分層剩余網(wǎng)絡(luò)AG(f)中vs→vt的一條最短路p，沿路p增加流值，刪除AG(f)中所有飽和弧。

Step4：求分層剩余網(wǎng)絡(luò)AG(f)中vs→vt的一條最短路p，若不存在，則在原網(wǎng)絡(luò)中刪除Step3中相應(yīng)的飽和弧，再轉(zhuǎn)Step1；否則轉(zhuǎn)Step3。

2.4 可行性分析

在新算法的操作過程中，刪除了沒有起作用的弧，對最大流的求解并沒有影響。因?yàn)樵谒惴ㄇ蠼膺^程中，這些弧不進(jìn)入最短增廣鏈。刪除AG(f)中所有的飽和弧后，同時刪去原容量網(wǎng)絡(luò)中對應(yīng)的弧，刪除的飽和弧在以后的增廣過程中，它的流值不可能增加或減少[17]，只是避免產(chǎn)生回溯現(xiàn)象，從而簡化了重新尋找可增廣鏈的過程。設(shè)容量網(wǎng)絡(luò)G=(V,A,c)有m條弧，每次增廣后，至少刪除一條飽和弧，則最多經(jīng)過m次增廣后，網(wǎng)絡(luò)G=(V,A,c)中就不存在從始點(diǎn)vs到終點(diǎn)vt的可增廣鏈，此時算法終止，即新算法不會進(jìn)入死循環(huán)中。

2.5 復(fù)雜度分析

在容量網(wǎng)絡(luò)G=(V,A,c)中，設(shè)節(jié)點(diǎn)數(shù)為n，弧數(shù)為m。在Step1中執(zhí)行一次搜索的復(fù)雜度為O(m)，步數(shù)不超過O(n)，在執(zhí)行Step2時，由廣探法知，每次構(gòu)造剩余分層網(wǎng)絡(luò)的復(fù)雜性為O(m)，最多執(zhí)行n-1次。Step3和Step4中最多增廣m次，每次增廣的計算量為O(n)，所以新算法的時間復(fù)雜度為：

O(mn)+O(mn)+O(mn2)=O(mn2)

(3)

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

例：容量網(wǎng)絡(luò)G如圖1所示，求從始點(diǎn)vs到終點(diǎn)vt的網(wǎng)絡(luò)最大流。

圖中，每條弧旁的數(shù)字表示容量，取初始可行流為零流。首先通過Step1，刪除原容量網(wǎng)絡(luò)中沒有起到作用的弧(v1,v3)，(v4,v3)，(vt,v3)。通過Step2-Step3得到分層剩余網(wǎng)絡(luò)中最短增廣鏈有3條弧，分別為P1=vsv1v4vt、P2=vsv2v4vt，增廣流值為12。在增廣流值的過程中弧(vs,v1)、(v2,v4)達(dá)到飽和，此時AG(f)中不存在vs→vt的一條路P，如圖2所示，即原容量網(wǎng)絡(luò)中不存在只有3條弧的增廣鏈。

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

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

通過Step4，在原容量網(wǎng)絡(luò)中刪除弧(vs,v1)、(v2,v4)，返回Step1-Step3再重新構(gòu)建分層剩余網(wǎng)絡(luò)，如圖3所示。此時有最短增廣鏈P=vsv2v1v4vt，含有4條弧。

圖3 重新構(gòu)建的分層剩余網(wǎng)絡(luò)圖

增廣流值1，在增廣流值的過程中弧(v1,v4)達(dá)到飽和，此時AG(f)中不存在vs→vt的一條路P，即原容量網(wǎng)絡(luò)中不存在只有4條弧的增廣鏈。返回Step1-Step2再重新構(gòu)建分層剩余網(wǎng)絡(luò)，此時分層剩余網(wǎng)絡(luò)中vt得不到標(biāo)號，于是可得最大流f，流值為13。

4 仿真實(shí)驗(yàn)

4.1 實(shí)驗(yàn)環(huán)境與設(shè)計

該算法在MATLAB2012b軟件中進(jìn)行仿真，處理器為Intel(R) Core(TM)i5-4210U CPU @ 1.70 GHz 2.40 GHz,內(nèi)存4 GB，Window7版本64位操作系統(tǒng)。

仿真實(shí)驗(yàn)采用的隨機(jī)網(wǎng)絡(luò)是由BA無標(biāo)度網(wǎng)絡(luò)的方法隨機(jī)生成的，網(wǎng)絡(luò)規(guī)模設(shè)為500，1 000，1 500，2 000，2 500，3 000個節(jié)點(diǎn)，且針對給出的網(wǎng)絡(luò)規(guī)模均進(jìn)行10次仿真實(shí)驗(yàn)求平均值。在這樣的仿真條件下，對最短增廣鏈算法與新算法進(jìn)行平均運(yùn)行時間的求解。

4.2 實(shí)驗(yàn)結(jié)果衡量指標(biāo)

將可行流流值、運(yùn)行時間作為實(shí)驗(yàn)結(jié)果的衡量指標(biāo)。f：最短增廣鏈算法求得的最大流流值；f'：新算法求得的最大流流值；t：最短增廣鏈算法的平均運(yùn)行時間；t'：新算法的平均運(yùn)行時間。

4.3 實(shí)驗(yàn)數(shù)據(jù)統(tǒng)計與分析

通過觀察表1中兩種算法在不同規(guī)模網(wǎng)絡(luò)上的實(shí)驗(yàn)數(shù)據(jù)統(tǒng)計，可以看出最短增廣鏈算法與新算法都能精確地求出網(wǎng)絡(luò)最大流，而且新算法的平均運(yùn)行時間低于最短增廣鏈算法。

表1 兩種算法在不同規(guī)模網(wǎng)絡(luò)上的實(shí)驗(yàn)數(shù)據(jù)統(tǒng)計

圖4的實(shí)驗(yàn)結(jié)果表明，在相同的網(wǎng)絡(luò)規(guī)模下，新算法要比最短增廣鏈算法所用的運(yùn)行時間短，這與之前的分析相吻合。

圖4 算法平均運(yùn)行時間的比較

5 結(jié)束語

隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，網(wǎng)絡(luò)最大流的應(yīng)用在現(xiàn)實(shí)生活中扮演著越來越重要的角色。文中在最短增廣鏈算法的基礎(chǔ)上，提出了一種最短增廣鏈改進(jìn)算法。該算法刪除了原容量網(wǎng)絡(luò)中沒有起作用的弧，并且在分層剩余網(wǎng)絡(luò)中刪除的飽和弧，相應(yīng)的在原網(wǎng)絡(luò)中刪除該弧，簡化了構(gòu)造剩余網(wǎng)絡(luò)及分層剩余網(wǎng)絡(luò)的過程，降低了計算量，使整個算法的執(zhí)行效率得以提高。通過數(shù)值實(shí)例驗(yàn)證了該算法的簡便性、實(shí)用性，并在BA無標(biāo)度網(wǎng)絡(luò)下進(jìn)行了仿真實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，在相同的網(wǎng)絡(luò)規(guī)模下，該算法要比最短增廣鏈算法效率高。