羅甜甜,趙禮峰

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

0 概述

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

最短增廣鏈算法構(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)中含有交叉頂點,如果仍然任意選擇增廣鏈而不考慮增廣先后順序,則可能會導(dǎo)致之后構(gòu)建的AD(f)中某些增廣鏈缺失。

為提高最短增廣鏈算法的準(zhǔn)確性,本文提出一種基于交叉頂點的最大流改進算法。在分層剩余網(wǎng)絡(luò)AD(f)中依次選擇頂點容差較小的頂點,以下一步推進的原則找到第一條增廣鏈,在此基礎(chǔ)上尋找與該條增廣鏈有交叉頂點的相關(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分別表示該有向圖的頂點集、弧集和弧上的容量值,稱網(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在含有源點vs和匯點vt的容量網(wǎng)絡(luò)D=(V,A,c)中,源點Vs記為標(biāo)號未檢查,令h(vs)=0,ls=-1。

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

步驟3考察vi的所有出弧(vi,vj),若vj未標(biāo)號,則將vj記為已標(biāo)號未檢查,令h(vj)=h(vi)+1,lj=i;若vj已標(biāo)號則不作處理;若vi的所有出弧全部考察完,則頂點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頂點容差

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

定義5交叉頂點

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

定義6交叉頂點原則

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

定義7頂點的度

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

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

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

2 基于交叉頂點的最大流算法

2.1 算法設(shè)計思想

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

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)時匯點vt得不到標(biāo)號,則算法結(jié)束,fk即為網(wǎng)絡(luò)最大流;否則轉(zhuǎn)步驟2。

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

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

3.1 算法可行性分析

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

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

設(shè)容量網(wǎng)絡(luò)D=(V,A,c),其頂點數(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 算法實例與比較

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

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

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

本文算法求解過程如下:

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)頂點的容差,并將容差值標(biāo)在相應(yīng)頂點的旁邊。選擇容差值最小的頂點作為下一步推進點增廣,得到增廣鏈p1=vsv2v4vt,可行流f2見圖3,其中,弧邊的數(shù)值表示該弧的流量大小,下同。

圖3 可行流f2

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

圖4 可行流f3

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

圖5 可行流f4

5)此時,在AD(f4)中沒有與p1～p3有交叉頂點的增廣鏈,只剩下增廣鏈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 實驗環(huán)境與設(shè)計

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

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

5.2 實驗結(jié)果分析

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

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

6 結(jié)束語

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