求解最小費(fèi)用流的一種新算法

紀(jì)亞勁，劉艷清，趙禮峰

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

0 引 言

最小費(fèi)用流問(wèn)題是圖論領(lǐng)域中的核心問(wèn)題之一，也是網(wǎng)絡(luò)優(yōu)化中的重要問(wèn)題。該問(wèn)題主要是在容量費(fèi)用網(wǎng)絡(luò)中計(jì)算從源點(diǎn)至匯點(diǎn)的費(fèi)用最小的可行流，并且也可以看成線(xiàn)性規(guī)劃問(wèn)題[1-2]，在生產(chǎn)分配、交通運(yùn)輸、信息通訊、網(wǎng)絡(luò)管理、電網(wǎng)等領(lǐng)域都得到了很好的應(yīng)用[3-7]。因此，研究最小費(fèi)用流算法具有重要的意義。

迄今為止，最小費(fèi)用流問(wèn)題的研究已經(jīng)有50多年的歷史，并且也形成了非常完善的理論體系。最小費(fèi)用流的經(jīng)典算法[1]可以分為兩類(lèi)：利用圖論的理論方法，包括Klein在1967年提出的負(fù)費(fèi)用回路算法，還有Busack和Gowen在1961年提出的最小費(fèi)用路算法等；利用線(xiàn)性規(guī)劃理論，先將最小費(fèi)用流問(wèn)題轉(zhuǎn)化為線(xiàn)性規(guī)劃模型，然后求解最小費(fèi)用可行流，主要有原始對(duì)偶算法、狀態(tài)算法等等。其中第一類(lèi)算法由于計(jì)算簡(jiǎn)單而被廣泛應(yīng)用。除了這些經(jīng)典算法，還有許多學(xué)者提出了改進(jìn)的最小費(fèi)用流算法[8-12]。

其中最小費(fèi)用路算法是由初始可行流通過(guò)沿最小費(fèi)用路增廣得到另一個(gè)流值增加且費(fèi)用最小的可行流，直到流值為v0或是最大流且費(fèi)用最小的可行流，即最小費(fèi)用流。由于最小費(fèi)用路算法在執(zhí)行過(guò)程中需要多次尋找最小費(fèi)用路徑，導(dǎo)致算法時(shí)間復(fù)雜度偏高，并且在實(shí)際應(yīng)用中，一般不一定需要求出最小費(fèi)用最大流，只需求出預(yù)定流值的最小費(fèi)用流即可。所以，文中針對(duì)最小費(fèi)用路算法進(jìn)行改進(jìn)，利用改進(jìn)的Dijkstra算法[13-14]尋找所有源點(diǎn)至匯點(diǎn)的路徑并且在余網(wǎng)絡(luò)中進(jìn)行增廣，以求出預(yù)定流值的最小費(fèi)用流，提高算法效率。

1 基本概念

定義1：設(shè)N=(V,A,c,w)為帶源點(diǎn)vs和匯點(diǎn)vt的容量費(fèi)用網(wǎng)絡(luò)，v0(v0>0)是某固定流值，那么N中最小費(fèi)用流問(wèn)題的線(xiàn)性規(guī)劃模型為：

MIN ∑wijfij

定義2：對(duì)于給定的容量網(wǎng)絡(luò)N=(V,A,c)及N上的一個(gè)可行流f={fij|(vi,vj)∈A}，?(vi,vj)∈A，若0≤fij

圖1 余網(wǎng)絡(luò)生成示意

2 最小費(fèi)用路算法

2.1 算法步驟

Step1：取初始可行流f(例如零流)；

Step2：若v(f)=v0，終止。否則轉(zhuǎn)Step3；

Step3：構(gòu)造剩余網(wǎng)絡(luò)D(f)，找到一條最短費(fèi)用路徑P，找不到則停止；

Step4：沿P增廣流值δ=min{cf(P),v0-v(f)}，得到新的可行流，轉(zhuǎn)Step2。

2.2 算法存在的劣勢(shì)

(1)每次更新剩余網(wǎng)絡(luò)后，該算法都要重新在剩余網(wǎng)絡(luò)中尋找最小費(fèi)用路作為增廣鏈增廣，假設(shè)每次增廣至少增廣流值為1，那么該算法最多需要利用v0次ford最短路算法來(lái)尋找最小費(fèi)用路，所以該算法還是偏復(fù)雜。

(2)最小費(fèi)用路算法是在剩余網(wǎng)絡(luò)的基礎(chǔ)上進(jìn)行增廣，那么該算法可以計(jì)算出網(wǎng)絡(luò)的最小費(fèi)用最大流，對(duì)于求網(wǎng)絡(luò)最小費(fèi)用流其適用性比較廣，但對(duì)于只需要求預(yù)定流值的最小費(fèi)用流來(lái)說(shuō)，該算法可能顯得冗余。

3 一種求最小費(fèi)用流的新算法

3.1 算法思想

新的最小費(fèi)用流算法的基本思想是利用改進(jìn)的Dijkstra算法先求出從源點(diǎn)至匯點(diǎn)的所有費(fèi)用路徑，記錄下每條路徑的費(fèi)用w。將所有路徑費(fèi)用按從小到大排列。首先構(gòu)造關(guān)于初始可行流f(例如零流)的余網(wǎng)絡(luò)N(f)，在N(f)中選擇費(fèi)用最小的路徑進(jìn)行增廣，增廣后更新可行流f及余網(wǎng)絡(luò)N(f)，刪除網(wǎng)絡(luò)中容量為0的弧和不存在的費(fèi)用路徑記錄，繼續(xù)選擇當(dāng)前費(fèi)用最小的有向路徑增廣。重復(fù)以上步驟，直至增流至預(yù)定流值v0或者不存在可增廣路徑為止。

3.2 算法步驟

Step1：根據(jù)容量費(fèi)用網(wǎng)絡(luò)N=(V,A,c,w)構(gòu)造費(fèi)用的鄰接矩陣D'。

Step2：刪掉矩陣D'的第一行第一列得到D。

Step3：只保留矩陣D'的第一行且刪掉第一列得到矩陣D1。

Step4：Dk=Dk-1?D，構(gòu)造秩為k的矩陣Dk，保留各節(jié)點(diǎn)之間的所有路徑項(xiàng)，直至所得的節(jié)點(diǎn)數(shù)等于n時(shí)停止。計(jì)算P=∪Di(i=1,2,…,n)，只保留從源點(diǎn)到匯點(diǎn)的所有有向路徑S1,S2,…,Sr。

Step5：比較有向路徑S1,S2,…,Sr的費(fèi)用權(quán)值，把費(fèi)用權(quán)值從小到大排列。

Step6：按權(quán)值從小到大的順序依次對(duì)滿(mǎn)足增流條件的有向路徑增流，直到增流至預(yù)定流值v0或者不存在可增廣路徑為止。

3.3 算法的可行性

新算法執(zhí)行時(shí)，首先通過(guò)改進(jìn)的Dijkstra算法找到從源點(diǎn)到匯點(diǎn)的所有路徑，算法Step4中的終止條件是當(dāng)算法執(zhí)行到第n-1步，得到的節(jié)點(diǎn)數(shù)為n時(shí)終止，防止算法陷入死循環(huán)。其次根據(jù)路徑費(fèi)用權(quán)值從小到大增廣流值。每增廣一次流值，調(diào)整流量后，將增廣鏈上容量為0的弧從網(wǎng)絡(luò)中刪除。設(shè)網(wǎng)絡(luò)N的預(yù)定流值為v0，每次增廣的流值最少為1，因此最多經(jīng)過(guò)v0次增廣，此時(shí)算法結(jié)束，得到最小費(fèi)用流，該算法不會(huì)陷入死循環(huán)。

3.4 算法的復(fù)雜度

(1)時(shí)間復(fù)雜度。

設(shè)容量費(fèi)用網(wǎng)絡(luò)N的頂點(diǎn)數(shù)為n，有向弧數(shù)為m，v0為預(yù)定流值，并且假設(shè)N中所有弧容量以及v0均為整數(shù)。改進(jìn)的Dijkstra算法的時(shí)間復(fù)雜度為O(n2)，所以Step1-Step5的算法時(shí)間復(fù)雜度為O(n2)，Step6沿最小費(fèi)用路對(duì)流進(jìn)行增廣的計(jì)算量為O(n)。由此可知，定流值比例的最小費(fèi)用路新算法的時(shí)間復(fù)雜度為O(n2+n2+n)=O(n2)。

(2)空間復(fù)雜度。

在新算法執(zhí)行過(guò)程中，需要存儲(chǔ)網(wǎng)絡(luò)中所有弧的費(fèi)用權(quán)值和容量權(quán)值，它們由兩個(gè)n×n鄰接矩陣分別存儲(chǔ)，復(fù)雜性為O(n2)。同時(shí)算法Step4中還需要記錄r條有向路徑，每條路徑的復(fù)雜度為O(n)，Step6中沿有向路徑增流其復(fù)雜度為O(n)，整個(gè)算法最多循環(huán)v0次。因此新算法的空間復(fù)雜度為：O(n2+rn+v0n)=O(n·max{v0,n})。

4 算法驗(yàn)證

如圖2所示，圖1中每條弧上的第一個(gè)數(shù)字為容量，第二個(gè)數(shù)字為費(fèi)用，求從源點(diǎn)1至匯點(diǎn)6的最小費(fèi)用流。

圖2 原網(wǎng)絡(luò)

(1)利用改進(jìn)的Dijkstra算法在原網(wǎng)絡(luò)中找到6條從源點(diǎn)至匯點(diǎn)的費(fèi)用路徑，分別為：S1=1246，S2=1356，S3=13246，S4=12456，S5=135246，S6=132456。費(fèi)用分別為：w1=11,w2=10,w3=16,w4=9,w5=16,w6=14，按從小到大排序：S4,S2,S1,S6,S5。

(2)按照順序依次進(jìn)行增流,直到不存在從源點(diǎn)1至匯點(diǎn)6的可增廣路徑為止，最終算出的最小費(fèi)用流為f=9,w=99。

5 算法仿真分析

5.1 硬件環(huán)境

利用MATLAB軟件進(jìn)行仿真實(shí)驗(yàn)，編程環(huán)境為MATLAB2012b，CPU為Intel(R) Core(TM)i7-4720HQ CPU @ 2.60 Hz,內(nèi)存為8 GB，64位Window7系統(tǒng)。

5.2 實(shí)驗(yàn)設(shè)置

仿真分為兩部分。第一部分針對(duì)上述例題，利用新算法與Busacker-Gowan算法通過(guò)實(shí)驗(yàn)驗(yàn)證結(jié)果的正確性以及比較兩個(gè)算法的運(yùn)行時(shí)間。第二部分是對(duì)于ER隨機(jī)網(wǎng)絡(luò)進(jìn)行仿真分析，此部分實(shí)驗(yàn)分為兩組：第一組是稀疏網(wǎng)絡(luò)測(cè)試，第二組是非稀疏網(wǎng)絡(luò)測(cè)試。

5.3 實(shí)例驗(yàn)證

對(duì)于上述實(shí)例中的網(wǎng)絡(luò)，輸入預(yù)定流值v0=20，若網(wǎng)絡(luò)的實(shí)際最大流流值小于等于預(yù)定流值，那么最小費(fèi)用流算法求出的是網(wǎng)絡(luò)最大流及對(duì)應(yīng)的最大流最小費(fèi)用；若網(wǎng)絡(luò)的實(shí)際最大流流值大于預(yù)定流值，那么求出的是預(yù)定流值下的最小費(fèi)用。

重復(fù)10次實(shí)驗(yàn)求得結(jié)果的流值都為9，對(duì)應(yīng)的費(fèi)用均為99。具體的可行流矩陣f與費(fèi)用矩陣w如下：

并且新算法與Busacker-Gowan算法的運(yùn)行時(shí)間平均值分別為：6.2770e-4 s和7.0935e-4 s。通過(guò)以上實(shí)驗(yàn)分析得出新算法與Busacker-Gowan算法的結(jié)論一樣，由于此例的節(jié)點(diǎn)數(shù)過(guò)少，所以?xún)煞N算法運(yùn)行時(shí)間關(guān)系不明顯。接下來(lái)針對(duì)大型的ER隨機(jī)網(wǎng)絡(luò)作比較。

5.4 隨機(jī)網(wǎng)絡(luò)實(shí)驗(yàn)與分析

5.4.1 ER隨機(jī)網(wǎng)絡(luò)

ER隨機(jī)網(wǎng)絡(luò)模型[15]定義為：對(duì)于一個(gè)節(jié)點(diǎn)數(shù)為n的網(wǎng)絡(luò)，其中任意兩點(diǎn)以概率p連接，網(wǎng)絡(luò)中邊的數(shù)目是一個(gè)隨機(jī)變量X，X的取值范圍是從0到n(n-1)/2的整數(shù)。生成的不同網(wǎng)絡(luò)共有2n(n-1)/2個(gè)。

結(jié)合ER隨機(jī)網(wǎng)絡(luò)和文中對(duì)網(wǎng)絡(luò)的要求，給出以下ER隨機(jī)網(wǎng)絡(luò)生成過(guò)程：

(1)創(chuàng)建一個(gè)n階零矩陣C作為原網(wǎng)絡(luò)的容量矩陣；

(2)創(chuàng)建一個(gè)n階零矩陣W作為原網(wǎng)絡(luò)的費(fèi)用矩陣；

(3)由ER隨機(jī)網(wǎng)絡(luò)參數(shù)p(概率)值，對(duì)于網(wǎng)絡(luò)中的任意兩點(diǎn)，給定一個(gè)隨機(jī)數(shù)r(0

(4)對(duì)步驟(3)中得到的所有邊，分別賦予兩個(gè)0～50間的隨機(jī)整數(shù)作為容量函數(shù)和費(fèi)用函數(shù)。

在ER隨機(jī)網(wǎng)絡(luò)中，若參數(shù)p<0.2，則規(guī)定其網(wǎng)絡(luò)為稀疏網(wǎng)絡(luò)，若p≥0.2,則規(guī)定為非稀疏網(wǎng)絡(luò)[16]。以下分別在稀疏ER隨機(jī)網(wǎng)絡(luò)和非稀疏ER隨機(jī)網(wǎng)絡(luò)中進(jìn)行仿真實(shí)驗(yàn)對(duì)比。

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

文中主要以最小費(fèi)用值、可行流流值、運(yùn)行時(shí)間作為主要性能指標(biāo)。f：Busacker-Gowan算法求得的可行流流值；f'：新算法求得的可行流流值；w：Busacker-Gowan算法求得的最小費(fèi)用值；w'：新算法求得的最小費(fèi)用值；t：Busacker-Gowan算法的運(yùn)行時(shí)間；t'：新算法的運(yùn)行時(shí)間。

5.4.3 稀疏ER隨機(jī)網(wǎng)絡(luò)實(shí)驗(yàn)

選取p=0.08生成的稀疏容量費(fèi)用網(wǎng)絡(luò)為原始網(wǎng)絡(luò)，分別使用Busacker-Gowan算法和新算法計(jì)算預(yù)定流值的最小費(fèi)用流，網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為200至1 000。從表1中可以看出，兩種算法求出最小費(fèi)用流的費(fèi)用和流值都相等。表1和圖3中運(yùn)行時(shí)間為十次實(shí)驗(yàn)運(yùn)行時(shí)間取平均值，可以看出在稀疏ER隨機(jī)網(wǎng)絡(luò)中新算法比經(jīng)典算法的效率更高，并且隨著節(jié)點(diǎn)數(shù)的增加，效果更加明顯。

5.4.4 非稀疏ER隨機(jī)網(wǎng)絡(luò)實(shí)驗(yàn)

選取p=0.25生成的非稀疏容量費(fèi)用網(wǎng)絡(luò)作為原始網(wǎng)絡(luò)，同樣比較兩種算法，網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)依然從200至1 000，取10次實(shí)驗(yàn)兩種算法運(yùn)行時(shí)間的平均值。兩種算法計(jì)算得到的最小費(fèi)用流的費(fèi)用及流值如表2和圖4所示。可以看出，文中算法的時(shí)間效率依然高于Busacker-Gowan算法，但是在非稀疏網(wǎng)絡(luò)中優(yōu)化的效率沒(méi)有稀疏網(wǎng)絡(luò)中明顯，所以文中算法更適用于稀疏網(wǎng)絡(luò)。

圖3 稀疏網(wǎng)絡(luò)兩種算法運(yùn)行時(shí)間對(duì)比

圖4 非稀疏網(wǎng)絡(luò)兩種算法運(yùn)行時(shí)間對(duì)比

表1 稀疏ER隨機(jī)網(wǎng)絡(luò)兩種算法的運(yùn)行結(jié)果(p=0.08)

表2 非稀疏ER隨機(jī)網(wǎng)絡(luò)兩種算法的運(yùn)行結(jié)果(p=0.25)

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

網(wǎng)絡(luò)最小費(fèi)用流的應(yīng)用是一項(xiàng)十分有意義的研究工作。文中對(duì)經(jīng)典算法加以改進(jìn)，提出了一種新算法，通過(guò)計(jì)算所有費(fèi)用路徑，經(jīng)過(guò)排序依次對(duì)其增廣流值

至預(yù)定流值,最終計(jì)算出最小費(fèi)用流。該算法相對(duì)經(jīng)典算法在時(shí)間上具有比較明顯的優(yōu)化，而且隨著網(wǎng)絡(luò)規(guī)模的增大，效果更顯著。該算法在兩種網(wǎng)絡(luò)比較中更加適用于稀疏網(wǎng)絡(luò)。在實(shí)際應(yīng)用中，很多網(wǎng)絡(luò)都是稀疏網(wǎng)絡(luò)，因此文中算法能為這些領(lǐng)域提供較為有力的支持。

[1] 謝 政.網(wǎng)絡(luò)算法與復(fù)雜性理論[M].長(zhǎng)沙：國(guó)防科技大學(xué)出版社，2003.

[2] 王桂平，王 衍，任嘉辰.圖論算法理論、實(shí)現(xiàn)及應(yīng)用[M].北京：北京大學(xué)出版社，2011.

[3] 謝凡榮.運(yùn)輸網(wǎng)絡(luò)中求最小費(fèi)用最大流的一個(gè)算法[J].運(yùn)籌與管理，2000,9(4)：33-38.

[4] FAN J，LIAO I F，TAN S X D，et al．Localized on-chip power delivery network optimization via sequence of linear programming[C]//Proceedings of the 7th international symposium on quality electronic design.Piscataway:IEEE Computer Society,2006:272-277．

[5] RISETTI G G,RIZZINI D L,STACHNISS C,et al.Online constraint network optimization for efficient maximum likelihood map learning[C]//IEEE international conference on robotics and automation.[s.l.]:IEEE,2008:1880-1885.

[6] CARLONI C，NOBILE L．Maximum circumferential stress criterion applied to orthotropic materials[J].Fatigue and Fracture of Engineering Materials and Structures,2005,28(9):825-833．

[7] DALMAS D，LAKSIMI A．On the method of determination of strain energy release rate during fatigue delamination in composite materials[J]．Applied Composite Materials，1999，6(5):327-340．

[8] 程德文，吳育華．求最小費(fèi)用最大流的改進(jìn)標(biāo)號(hào)法[J]．系統(tǒng)管理學(xué)報(bào)，2009，18(2):237-240．

[9] 金友良，張同全．最小費(fèi)用排序問(wèn)題[J]．云南民族大學(xué)學(xué)報(bào):自然科學(xué)版，2007，16(3):222-224．

[10] 趙禮峰，宋常城，白 睿.基于最小費(fèi)用最大流問(wèn)題的“排序”算法[J]．計(jì)算機(jī)技術(shù)與發(fā)展,2011，21(12):82-85．

[11] 趙禮峰，白 睿，宋常城．求解最小費(fèi)用最大流的新方法[J]．計(jì)算機(jī)技術(shù)與發(fā)展，2012，22(5):94-96．

[12] 夏林林，葉茂瑩，楊凌云,等.求解最小費(fèi)用流問(wèn)題的蟻群算法[J].內(nèi)江師范學(xué)院學(xué)報(bào)，2010，25(6):30-32．

[13] 徐鳳生，李天志.所有最短路徑的求解算法[J].計(jì)算機(jī)工程與科學(xué)，2006,28(12)：83-84.

[14] 孫小軍，焦建民.一種求解最少時(shí)間的最小費(fèi)用路問(wèn)題的算法[J].計(jì)算機(jī)工程與科學(xué)，2008,30(7)：77-78.

[15] 謝 政,湯澤瀅.最小費(fèi)用最大雙流[J].高校應(yīng)用數(shù)學(xué)學(xué)報(bào),1996(1)：97-104.

[16] 汪小帆，李 翔，陳光榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M].北京:清華大學(xué)出版社，2005.