包含交叉頂點(diǎn)的最大流改進(jìn)算法

羅甜甜,趙禮峰

(南京郵電大學(xué) 理學(xué)院,南京 210023)

0 概述

網(wǎng)絡(luò)最大流問題緊密結(jié)合圖論與運(yùn)籌學(xué),為圖論的應(yīng)用開辟了新途徑。解決最大流問題即討論如何充分利用裝置有限的容量來實(shí)現(xiàn)運(yùn)輸流量最大。針對這一問題,很多學(xué)者提出了相應(yīng)的求解算法,主要可分為增廣鏈算法和預(yù)流推進(jìn)算法兩類。經(jīng)典增廣鏈算法有Ford-Fulkerson算法[1]、Edmonds-karp算法[2]和最短增廣鏈算法[3],經(jīng)典預(yù)流推進(jìn)算法有阻塞流算法[4]和推進(jìn)重標(biāo)號算法[5]。許多學(xué)者對網(wǎng)絡(luò)最大流問題也做了進(jìn)一步深入的研究[6],針對經(jīng)典算法提出了多種改進(jìn)算法[7-11],如利用容差進(jìn)行修正的最大流2F算法[7]、有條件限制的最大流求解算法[9]、動態(tài)網(wǎng)絡(luò)的最大流增量算法[10]及大規(guī)模網(wǎng)絡(luò)的最大流求解算法[11]。文獻(xiàn)[12-13]則提出了最短增廣鏈改進(jìn)算法。

最短增廣鏈算法構(gòu)建的分層剩余網(wǎng)絡(luò)AD(f),使網(wǎng)絡(luò)中的(vs,vt)路始終是剩余網(wǎng)絡(luò)D(f)中的最短(vs,vt)路。相比D(f),在AD(f)中更易尋找(vs,vt)路,但有時AD(f)中含有交叉頂點(diǎn),如果仍然任意選擇增廣鏈而不考慮增廣先后順序,則可能會導(dǎo)致之后構(gòu)建的AD(f)中某些增廣鏈缺失。

為提高最短增廣鏈算法的準(zhǔn)確性,本文提出一種基于交叉頂點(diǎn)的最大流改進(jìn)算法。在分層剩余網(wǎng)絡(luò)AD(f)中依次選擇頂點(diǎn)容差較小的頂點(diǎn),以下一步推進(jìn)的原則找到第一條增廣鏈,在此基礎(chǔ)上尋找與該條增廣鏈有交叉頂點(diǎn)的相關(guān)增廣鏈,從而避免在AD(f)中選擇增廣鏈的任意性,提高算法效率。

1 基本概念

定義1容量網(wǎng)絡(luò)

給定一個有向圖G(V,A),c是定義在A上的正值函數(shù),?a∈A,a=(vi,vj),c(a)=cij,其中,V、A、c分別表示該有向圖的頂點(diǎn)集、弧集和弧上的容量值,稱網(wǎng)絡(luò)D=(V,A,c)為容量網(wǎng)絡(luò)[14]。

定義2剩余網(wǎng)絡(luò)

剩余網(wǎng)絡(luò)為D(f)=(V,A(f),cf),其中,f為容量網(wǎng)絡(luò)D=(V,A,c)上的可行流。定義:

記A(f)=A+(f)∪A-(f),對?(vi,vj)∈A(f),令:

稱cij(f)為剩余網(wǎng)絡(luò)D(f)的剩余容量[14-15]。

廣探法即廣度優(yōu)先搜索[16-18],是構(gòu)造分層剩余網(wǎng)絡(luò)的基礎(chǔ)方法,具體步驟如下:

步驟1在含有源點(diǎn)vs和匯點(diǎn)vt的容量網(wǎng)絡(luò)D=(V,A,c)中,源點(diǎn)Vs記為標(biāo)號未檢查,令h(vs)=0,ls=-1。

步驟2若存在已標(biāo)號未檢查的頂點(diǎn),找到最先標(biāo)號的頂點(diǎn)vi,轉(zhuǎn)步驟3;若所有已標(biāo)號頂點(diǎn)都檢查完,轉(zhuǎn)步驟4。

步驟3考察vi的所有出弧(vi,vj),若vj未標(biāo)號,則將vj記為已標(biāo)號未檢查,令h(vj)=h(vi)+1,lj=i;若vj已標(biāo)號則不作處理;若vi的所有出弧全部考察完,則頂點(diǎn)vi記為已檢查,轉(zhuǎn)步驟2。

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

定義3分層剩余網(wǎng)絡(luò)

根據(jù)剩余網(wǎng)絡(luò)和廣探法,可以給出剩余網(wǎng)絡(luò)的一個子網(wǎng)絡(luò),即分層剩余網(wǎng)絡(luò)AD(f)[14-15],其定義如下:

AD(f)=(V′(f),A′(f),cf)

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

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

{(vi,vt)∈A(f)|h(vi)=h(vt)-1}

定義4頂點(diǎn)容差

頂點(diǎn)v(v∈V)的所有出弧容量減去該頂點(diǎn)的所有入弧容量的值為頂點(diǎn)v(v∈V)的容差。

定義5交叉頂點(diǎn)

在分層剩余網(wǎng)絡(luò)AD(f)中,除源點(diǎn)與匯點(diǎn)之外,如果存在一個頂點(diǎn)包含在兩條及兩條以上的增廣鏈中,則稱該點(diǎn)為交叉頂點(diǎn)。

定義6交叉頂點(diǎn)原則

在含有交叉頂點(diǎn)的網(wǎng)絡(luò)圖中,選擇增廣鏈時優(yōu)先搜索與源點(diǎn)關(guān)聯(lián)且容差最小的頂點(diǎn)作為增廣鏈的下一步推進(jìn)點(diǎn)。確定一條增廣鏈后,對與上一條有重復(fù)頂點(diǎn)所在的增廣鏈進(jìn)行增廣。

定義7頂點(diǎn)的度

設(shè)M=(V,A)為一個非空有向圖,頂點(diǎn)v∈V,與頂點(diǎn)v所關(guān)聯(lián)的弧的數(shù)目即為頂點(diǎn)的度[18]。

BA無標(biāo)度網(wǎng)絡(luò)是被用來模擬不斷增長的網(wǎng)絡(luò)頂點(diǎn)的無標(biāo)度網(wǎng)絡(luò)模型[19-20],其創(chuàng)建過程如下:

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

2 基于交叉頂點(diǎn)的最大流算法

2.1 算法設(shè)計思想

雖然最短增廣鏈算法構(gòu)建了分層剩余網(wǎng)絡(luò),使得AD(f)的(vs,vt)路都是D(f)中的最短(vs,vt)路,簡化了網(wǎng)絡(luò),但在AD(f)中仍存在多條增廣鏈的可能,而且有時幾條增廣鏈中會有一些重合頂點(diǎn)存在,如果在這種情況下依然任意選擇AD(f)中的增廣鏈,可能會造成某些增廣鏈的缺失,使得最終的最大流值偏小。針對這一情況,本文對最短增廣鏈算法尋找增廣鏈的過程進(jìn)行改進(jìn),不再對AD(f)中多條增廣鏈采取視同一律的處理方式,而是根據(jù)交叉頂點(diǎn)原則來尋找增廣鏈。

2.2 算法步驟

初始化在容量網(wǎng)絡(luò)D中取初始可行流fk(一般取零流作為初始可行流),令k=1。

步驟1構(gòu)造D關(guān)于可行流fk的剩余網(wǎng)絡(luò)D(fk),并對該網(wǎng)絡(luò)應(yīng)用廣探法構(gòu)建分層剩余網(wǎng)絡(luò)AD(fk)。如果在構(gòu)建AD(fk)時匯點(diǎn)vt得不到標(biāo)號,則算法結(jié)束,fk即為網(wǎng)絡(luò)最大流;否則轉(zhuǎn)步驟2。

步驟2在AD(fk)中根據(jù)交叉頂點(diǎn)原則尋找增廣鏈,即(vs,vt)路p,轉(zhuǎn)步驟3;若不存在(vs,vt)路,則令fk+1=fk,k=k+1,轉(zhuǎn)步驟1。

3 算法可行性與復(fù)雜度分析

3.1 算法可行性分析

本文算法是在最短增廣鏈算法基礎(chǔ)上的改進(jìn),改進(jìn)之處在于尋找增廣鏈時按照交叉頂點(diǎn)原則尋找,每次找到增廣鏈進(jìn)行增廣后,至少會使容量網(wǎng)絡(luò)中的一條弧成為飽和弧。設(shè)容量網(wǎng)絡(luò)D=(V,A,c)中共有m條弧,若至多經(jīng)過m次增廣后D中不存在源點(diǎn)到匯點(diǎn)的增廣鏈,即在構(gòu)建分層剩余網(wǎng)絡(luò)時匯點(diǎn)得不到標(biāo)號,則滿足算法的終止條件,算法在有限步內(nèi)即可停止,不會陷入無限循環(huán)。

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

設(shè)容量網(wǎng)絡(luò)D=(V,A,c),其頂點(diǎn)數(shù)為n,弧數(shù)為m。本文算法整體分為兩部分,即構(gòu)建分層剩余網(wǎng)絡(luò)和尋找增廣鏈。由于步驟1中構(gòu)建造層剩余網(wǎng)絡(luò)AD(fk)的層數(shù)隨k單調(diào)遞增,AD(fk)的最高層數(shù)至多是(n-1)層,因此算法中最多建立n個分層剩余網(wǎng)絡(luò)。

由廣探法可知,每構(gòu)建一個分層剩余網(wǎng)絡(luò)的復(fù)雜度為O(m),因此,本文算法構(gòu)建分層剩余網(wǎng)絡(luò)的總復(fù)雜度為O(nm)。

在一個分層剩余網(wǎng)絡(luò)中,最多有m條弧,由于每增廣1次至少刪去1條弧,因此至多增廣m次,而每次增廣的計算量為O(n),所以，在一個分層剩余網(wǎng)絡(luò)中尋找增廣鏈的復(fù)雜度為O(mn),從而尋找增廣鏈的總復(fù)雜度為O(n2m)。

綜上可知,本文算法的復(fù)雜度為:

O(nm)+O(n2m)=O(n2m)

4 算法實(shí)例與比較

給出以下實(shí)例:在容量網(wǎng)絡(luò)D中,求從源點(diǎn)vs到匯點(diǎn)vt的最大流,如圖1所示,其中,弧邊的數(shù)值表示該弧的容量大小,下同。

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

當(dāng)容量網(wǎng)絡(luò)中存在多條源點(diǎn)到匯點(diǎn)的路徑,且這些路徑之間包含相同頂點(diǎn)時,分別應(yīng)用本文算法和最短增廣鏈算法進(jìn)行求解。

本文算法求解過程如下:

1)取零流f1作為初始可行流,得到剩余網(wǎng)絡(luò)D(f1),利用廣探法構(gòu)造分層剩余網(wǎng)絡(luò)AD(f1),見圖2。

圖2 分層剩余網(wǎng)絡(luò)AD(f1)

2)在AD(f1)中計算與vs相關(guān)聯(lián)頂點(diǎn)的容差,并將容差值標(biāo)在相應(yīng)頂點(diǎn)的旁邊。選擇容差值最小的頂點(diǎn)作為下一步推進(jìn)點(diǎn)增廣,得到增廣鏈p1=vsv2v4vt,可行流f2見圖3,其中,弧邊的數(shù)值表示該弧的流量大小,下同。

圖3 可行流f2

3)在AD(f2)中繼續(xù)選擇與p1有交叉頂點(diǎn)的增廣鏈進(jìn)行增廣,得到增廣鏈p2=vsv1v4vt,可行流f3見圖4。

圖4 可行流f3

4)在AD(f3)中繼續(xù)選擇與p2有交叉頂點(diǎn)的增廣鏈進(jìn)行增廣,得到增廣鏈p3=vsv1v6vt,可行流f4見圖5。

圖5 可行流f4

5)此時,在AD(f4)中沒有與p1～p3有交叉頂點(diǎn)的增廣鏈,只剩下增廣鏈p4=vsv3v5vt,由此得到可行流f5,見圖6。

圖6 可行流f5

6)此時,在AD(f5)中沒有(vs,vt)路,令f5=f6,重新構(gòu)造分層剩余網(wǎng)絡(luò)AD(f6),見圖7,并在其中找到增廣鏈p5=vsv3v5v6vt,可行流f7見圖8。

圖7 分層剩余網(wǎng)絡(luò)AD(f6)

圖8 可行流f7

7)此時,AD(f7)中沒有(vs,vt)路,令f7=f8,構(gòu)建剩余網(wǎng)絡(luò)D(f8),見圖9。由于D(f8)中不存在(vs,vt)路,因此f8為容量網(wǎng)絡(luò)D的最大流,流值為19。

圖9 剩余網(wǎng)絡(luò)D(f8)

最短增廣鏈算法求解過程如下:

1)取零流f1作為初始可行流,構(gòu)建分層剩余網(wǎng)絡(luò)AD(f1),見圖2。

2)在圖2中找增廣鏈,找到增廣鏈p1～p4:

增廣之后,得到可行流f′2,見圖10。

圖10 可行流f′2

3)繼續(xù)構(gòu)建剩余網(wǎng)絡(luò)D(f′2),見圖11。發(fā)現(xiàn)D(f′2)中不存在(vs,vt)路,算法結(jié)束。f′2記為容量網(wǎng)絡(luò)D的最大流,流值為16。

圖11 剩余網(wǎng)絡(luò)D(f′2)

可以看出,最短增廣鏈算法在分層剩余網(wǎng)絡(luò)中選取增廣鏈的任意性會導(dǎo)致增廣鏈缺失,從而使最后得到的最大流值偏小。

5 仿真與結(jié)果分析

5.1 實(shí)驗環(huán)境與設(shè)計

本文使用的實(shí)驗仿真平臺是MATLAB2016a,處理器為Intel?CoreTMi3-4030U CPU @1.90 GHz,內(nèi)存4 GB,Windows7版本64位操作系統(tǒng)。

仿真實(shí)驗采用的是BA無標(biāo)度隨機(jī)網(wǎng)絡(luò),將網(wǎng)絡(luò)規(guī)模設(shè)為頂點(diǎn)數(shù)為500、1 000、1 500、2 000、2 500、3 000、3 500。在給定的網(wǎng)絡(luò)規(guī)模下,對本文算法和最短增廣鏈算法進(jìn)行10次仿真實(shí)驗。其中,參數(shù)f1和t1分別表示最短增廣鏈算法的最大流值及其運(yùn)行時間的平均值,參數(shù)f2和t2分別表示本文算法的最大流值及其運(yùn)行時間的平均值。

5.2 實(shí)驗結(jié)果分析

實(shí)驗結(jié)果如表1所示,其中列出了2種算法在不同網(wǎng)絡(luò)規(guī)模下得到的最大流值及算法的平均運(yùn)行時間?？梢钥闯?本文算法較最短增廣鏈算法結(jié)果更精準(zhǔn)，并且運(yùn)行時間相差較小。

表1 本文算法與最短增廣鏈算法在不同網(wǎng)絡(luò)規(guī)模下的實(shí)驗結(jié)果

6 結(jié)束語

最短增廣鏈算法在分層剩余網(wǎng)絡(luò)中尋找增廣鏈的任意性可能導(dǎo)致增廣鏈缺失。針對該問題,本文提出一種基于交叉頂點(diǎn)的改進(jìn)算法。在尋找增廣鏈時不再視同一律,而是遵循頂點(diǎn)交叉原則,從而避免增廣鏈缺失的情況,提高算法的準(zhǔn)確性。實(shí)驗結(jié)果表明,該算法得到的最大流值比最短增廣鏈算法更準(zhǔn)確,并且運(yùn)行效率相當(dāng)。后續(xù)將在保證準(zhǔn)確率的基礎(chǔ)上,進(jìn)一步提高算法的運(yùn)行效率。