羅甜甜，趙禮峰

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

0 引 言

最大流問題是一種組合最優(yōu)化問題，在許多實(shí)際的網(wǎng)絡(luò)系統(tǒng)中都存在著流量和最大流問題，例如鐵路運(yùn)輸系統(tǒng)中的車輛流[1-3]、城市排水系統(tǒng)中的水流問題[4-6]、控制系統(tǒng)中的信息流問題等[7-9]都可以抽象出最大流模型，從而轉(zhuǎn)化為最大流問題。所以最大流問題應(yīng)用廣泛，實(shí)踐性強(qiáng)。求解網(wǎng)絡(luò)最大流的常用算法可以分為增廣路徑算法和預(yù)流推進(jìn)算法[10]。其中后者的編碼程度過高，因而前者為經(jīng)常使用的算法。而屬于增廣路徑算法的主要有：Ford-Fulkerson算法[11]，Edmonds-Karp算法和最短增廣鏈算法[12]，ISAP算法。設(shè)容量網(wǎng)絡(luò)D的頂點(diǎn)數(shù)為m，弧數(shù)為n，弧容量的最大值為cmax，F(xiàn)ord-Fulkerson算法的算法復(fù)雜度則為O(mncmax)，當(dāng)容量網(wǎng)絡(luò)某些弧容量為無理數(shù)時(shí)，此算法便會(huì)陷入無限循環(huán)。Edmonds-Karp對(duì)其修正，用寬度優(yōu)先取代了深度優(yōu)先。最短增廣鏈算法是將頂點(diǎn)按照其與源點(diǎn)的最短距離分層，分層時(shí)用寬度優(yōu)先法，而尋求增廣路徑時(shí)采用深度優(yōu)先策略。兩者結(jié)合效率明顯高于Edmonds-Karp算法。ISAP算法是對(duì)最短增廣鏈算法的優(yōu)化，即通過深度優(yōu)先不斷修改距離標(biāo)號(hào)的方式省去每一次的寬度優(yōu)先。但由于最短增廣鏈算法在構(gòu)建分層剩余網(wǎng)絡(luò)中選取增廣鏈仍然存在隨機(jī)性使得某些增廣鏈缺失，導(dǎo)致算法執(zhí)行后的結(jié)果偏小，失去其準(zhǔn)確性。

該文針對(duì)最短增廣鏈算法在分層剩余網(wǎng)絡(luò)后尋找增廣鏈不考慮先后順序使得最大流值偏小這一問題進(jìn)行改進(jìn)，沿用了最短增廣鏈算法通過寬度優(yōu)先將頂點(diǎn)分層的思想，將頂點(diǎn)根據(jù)層數(shù)，源弧容量，匯弧容量和頂點(diǎn)容差這四個(gè)因素來確定頂點(diǎn)被選擇的先后順序。然后根據(jù)相應(yīng)規(guī)則來選取增廣鏈，此規(guī)則可以保證最短增廣鏈優(yōu)先選取，并可以井然有序地快速找出所有增廣鏈。

1 基本概念

定義1[13]：容量網(wǎng)絡(luò)D=(V,A,c)，其中V表示D中頂點(diǎn)的集合，A為D中弧的集合，c表示弧上的容量。

定義2[13]：流量。設(shè)f是容量網(wǎng)絡(luò)D中弧集A上的一個(gè)實(shí)函數(shù)，?a=(vi,vj)∈A，記f(a)=fij。如果函數(shù)f={fij|(vi,vj)∈A}滿足守恒條件：

則稱f是D的一個(gè)流，此時(shí)，fij稱為通過弧(vi,vj)上的流量。

定義3[13]：頂點(diǎn)層數(shù)：在容量網(wǎng)絡(luò)D中，用寬度優(yōu)先搜索[14-15]找出從源點(diǎn)vs到任意一點(diǎn)vi(vi∈V)的最短路的長(zhǎng)度hi稱為頂點(diǎn)vi的層數(shù)，即由vs到vi的路徑中所含的最少弧數(shù)。(第零層只有一個(gè)節(jié)點(diǎn)就是源點(diǎn)即hs=0)。

定義4[16]：剩余網(wǎng)絡(luò)D(f)=(V,A(f),cf),其中V表示容量網(wǎng)絡(luò)D中頂點(diǎn)的集合，f為D上的可行流，A(f)是D(f)上弧的集合，其中，

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

A+(f)={(vi,vj)|(vi,vj)∈A,fij

A-(f)={(vi,vj)|(vj,vi)∈A,fij>0}

cij(f)為(vi,vj)關(guān)于f的剩余容量，其中，

定義5[16]：分層剩余網(wǎng)絡(luò)記為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}

定義6：源弧容量：由源點(diǎn)vs到頂點(diǎn)vi(vi∈V)所構(gòu)成的弧的容量c(vs,vi)，記為αi。

定義7：匯弧容量：由頂點(diǎn)vi(vi∈V)到匯點(diǎn)vt所構(gòu)成的弧的容量c(vi,vt)，記為βi。

定義8：頂點(diǎn)容差：頂點(diǎn)vi(vi∈V)的所有出弧容量減去該頂點(diǎn)的所有入弧容量的值為頂點(diǎn)vi(vi∈V)的容差，記為γi。

定義9：中間頂點(diǎn)(除源點(diǎn)、匯點(diǎn)外)標(biāo)號(hào)過程：對(duì)于頂點(diǎn)vi，當(dāng)hi=1時(shí)，求出αi和γi，將其標(biāo)號(hào)為(1,αi,γi)；當(dāng)1

定義10：重置頂點(diǎn)下標(biāo)規(guī)則：已知網(wǎng)絡(luò)D，其頂點(diǎn)數(shù)為n，則將源點(diǎn)vs重置為v1，匯點(diǎn)vt重置為vn。除源點(diǎn)匯點(diǎn)外，中間頂點(diǎn)的重置標(biāo)號(hào)依次為v2,v3,…,vn-1。首先按照頂點(diǎn)層數(shù)hi由低至高的順序依次由小到大編號(hào)重置；當(dāng)hi相等時(shí)，分三種情況考慮：

(1)hi=1，按照源弧容量αi由低至高的順序依次由小到大編號(hào)重置，當(dāng)αi相等時(shí)，再按照容差γi由低至高的順序依次由小到大編號(hào)重置；

(2)當(dāng)最高層的頂點(diǎn)唯一，且13)時(shí)，當(dāng)最高層頂點(diǎn)不唯一，且13)時(shí)，都按照容差γi由低至高的順序依次由小到大編號(hào)重置；

(3)當(dāng)最高層的頂點(diǎn)唯一，且hi=ht-1時(shí)，或者當(dāng)最高層的頂點(diǎn)不唯一，且hi=ht時(shí)，都按照匯弧容量βi由低至高的順序依次由小到大編號(hào)重置，當(dāng)βi相等時(shí)，再按照容差γi由低至高的順序依次由小到大編號(hào)重置。

定理：設(shè)f是容量網(wǎng)絡(luò)D中的可行流，則f是D的最大流當(dāng)且僅當(dāng)D中不存在f增廣鏈。

2 新算法思想及步驟

2.1 算法思想

求網(wǎng)絡(luò)最大流[17]的基本思想是根據(jù)定理1，即從容量網(wǎng)絡(luò)D中的一個(gè)可行流出發(fā)，尋找增廣鏈進(jìn)行增廣，直至D中不存在增廣鏈為止。根據(jù)此思路，目的是尋找增廣鏈，關(guān)鍵是確定選取增廣鏈的先后順序。首先是根據(jù)一定規(guī)則對(duì)頂點(diǎn)下標(biāo)進(jìn)行重置，形成與原網(wǎng)絡(luò)D相對(duì)應(yīng)的新網(wǎng)絡(luò)D1。然后按照優(yōu)先選取頂點(diǎn)標(biāo)號(hào)值較大的增廣鏈增廣的原則在D1中尋找增廣鏈，直至不存在從源點(diǎn)到匯點(diǎn)的增廣鏈即可結(jié)束該算法。

2.2 算法步驟

Step1:利用寬度優(yōu)先搜索求出原容量網(wǎng)絡(luò)D中各個(gè)頂點(diǎn)的層數(shù)，再根據(jù)定義9對(duì)中間頂點(diǎn)進(jìn)行標(biāo)號(hào)。

Step2：根據(jù)定義10對(duì)頂點(diǎn)下標(biāo)進(jìn)行重置，形成對(duì)應(yīng)的新網(wǎng)絡(luò)D1。

Step3：初始化新網(wǎng)絡(luò)D1，令D1中每條弧的流量為0。

Step4：從頂點(diǎn)v1出發(fā)，判斷D1中是否存在一條從v1到vn(n為網(wǎng)絡(luò)D1的頂點(diǎn)個(gè)數(shù))的增廣鏈，若存在轉(zhuǎn)Step5，否則轉(zhuǎn)Step7。

Step5：從頂點(diǎn)v1出發(fā)，沿著與其關(guān)聯(lián)弧所在頂點(diǎn)下標(biāo)值較大的原則找一條從v1到vn的增廣鏈，若存在轉(zhuǎn)Step6，否則轉(zhuǎn)Step7。

Step6：調(diào)整，求該鏈上各弧容量的最小值δ，并將此增廣鏈中對(duì)應(yīng)弧的容量后面標(biāo)上δ，其中δ=min{cij-fij}。在飽和弧上標(biāo)上終止弧標(biāo)志“||”，增廣后轉(zhuǎn)Step4。

Step7：計(jì)算所有以v1為發(fā)點(diǎn)的弧的流量和，得到最大流值v(f)，算法結(jié)束。

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

3.1 可行性分析

新算法的主要思想是沿著所規(guī)定好的原則尋找增廣路徑，每次增廣至少使一條弧達(dá)到飽和。假設(shè)網(wǎng)絡(luò)D中共有m條弧，那么最多通過m次增廣后，網(wǎng)絡(luò)D中就不存在從源點(diǎn)到匯點(diǎn)的增廣鏈，即算法結(jié)束。說明算法經(jīng)過有限次步驟就會(huì)終止，不會(huì)陷入無限循環(huán)。

3.2 復(fù)雜度分析

新算法主要分為兩個(gè)過程：一是標(biāo)記、比較和編號(hào)過程，通過這些準(zhǔn)備工作構(gòu)建新網(wǎng)絡(luò)流圖；二是增廣過程，沿著頂點(diǎn)下標(biāo)值大的原則尋找增廣鏈。設(shè)容量網(wǎng)絡(luò)D的頂點(diǎn)數(shù)為n，弧數(shù)為m。該算法執(zhí)行時(shí)，第一個(gè)過程屬于準(zhǔn)備過程只執(zhí)行一次，而執(zhí)行一次準(zhǔn)備工作的計(jì)算量分別是：(1)計(jì)算層數(shù)O(n)次；(2)計(jì)算容差最多需要O((n-2)m)次；(3)比較大小重新編號(hào)最多需要O(2nlog2n)次。第二個(gè)過程最多執(zhí)行O(m)次，于是該算法的時(shí)間復(fù)雜度為：

O(n)+O((n-2)m)+O(2nlog2n)+O(m)=O(2nlog2n+nm)

4 應(yīng)用實(shí)例

例：求出圖1的容量網(wǎng)絡(luò)D中從源點(diǎn)vs到匯點(diǎn)vt的網(wǎng)絡(luò)最大流。

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

解：方法一(文中算法)：

(1)首先根據(jù)寬度優(yōu)先搜索求出各頂點(diǎn)層數(shù)，得：

(2)對(duì)于hi=1，要求出αi和γi，于是可得：

因?yàn)閔t=3<4，對(duì)于1

(3)由(2)所得數(shù)據(jù)對(duì)頂點(diǎn)標(biāo)號(hào)，如圖2所示。

圖2 標(biāo)號(hào)后的容量網(wǎng)絡(luò)D

(4)再根據(jù)定義8重置頂點(diǎn)下標(biāo)：令

重新構(gòu)造容量網(wǎng)絡(luò)D1，如圖3所示。

圖3 容量網(wǎng)絡(luò)D1

(5)在D1中按照優(yōu)先選取頂點(diǎn)下標(biāo)值較大的原則尋找增廣鏈：

增廣后的網(wǎng)絡(luò)流圖如圖4所示。

圖4 可行流f

在圖4中找不到v1到v8的增廣鏈了，故圖4即為最大流f，計(jì)算最大流值為V(f)=4+3+3+5+1=16。

方法二(最短增廣鏈算法)：

(1)在D中取f1為初始可行流，令f1為零流。然后構(gòu)建分層剩余網(wǎng)絡(luò)AD(f1)，見圖5。

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

(2)在圖5中找增廣鏈，找到了如下幾條增廣鏈：

增廣之后，得到可行流f2，見圖6。

圖6 可行流f2

(3)繼續(xù)構(gòu)建剩余網(wǎng)絡(luò)D(f2)，見圖7。發(fā)現(xiàn)D(f2)中不存在(vs,vt)路，算法結(jié)束。f2即為容量網(wǎng)絡(luò)D的最大流，在圖6中計(jì)算與源點(diǎn)關(guān)聯(lián)的所有弧的流量和為14，即最大流的流值為14?？梢娕c方法一相比流值偏小。

圖7 剩余網(wǎng)絡(luò)D(f2)

5 算法的仿真與比較

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

該算法使用的實(shí)驗(yàn)仿真平臺(tái)是MATLAB2016a，處理器為Intel(R) Core(TM) i3-4030U CPU @1.90 GHz，內(nèi)存4 GB，Windows7版本64位操作系統(tǒng)。

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

5.2 實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)與分析

根據(jù)表1的內(nèi)容可以看到兩種算法在不同的網(wǎng)絡(luò)規(guī)模下得出的最大流值情況以及算法的平均運(yùn)行時(shí)間。明顯可以得出新算法比最短增廣鏈算法的結(jié)果更精準(zhǔn)。由圖8可以看到新算法的運(yùn)行時(shí)間較短。

表1 新算法與最短增廣鏈算法在不同網(wǎng)絡(luò)規(guī)模的運(yùn)行數(shù)據(jù)

圖8 新算法與最短增廣鏈算法的平均運(yùn)行時(shí)間

6 結(jié)束語

文中針對(duì)最短增廣鏈算法在構(gòu)建分層剩余網(wǎng)絡(luò)后選取增廣鏈增廣的先后順序不當(dāng)而影響最大流值偏小的問題進(jìn)行了改進(jìn)處理。首先對(duì)頂點(diǎn)標(biāo)號(hào)根據(jù)其在整個(gè)網(wǎng)絡(luò)圖所處位置按一定規(guī)律重新編號(hào)，為后面尋找增廣鏈有規(guī)可循且節(jié)約了時(shí)間，也使得網(wǎng)絡(luò)圖更加清晰直觀。通過很多實(shí)例和實(shí)驗(yàn)仿真證實(shí)了算法的準(zhǔn)確性和高效性。