關(guān)于網(wǎng)絡(luò)構(gòu)建的最大通過能力問題

楊?。ㄙF州民族大學(xué)　理學(xué)院，貴州　貴陽　550025）

關(guān)于網(wǎng)絡(luò)構(gòu)建的最大通過能力問題

楊健
（貴州民族大學(xué)理學(xué)院，貴州貴陽550025）

摘要：給定一個(gè)有向網(wǎng)絡(luò)D以及關(guān)于弧上的容量函數(shù)和構(gòu)建費(fèi)用函數(shù)，要在網(wǎng)絡(luò)D中尋找一個(gè)子網(wǎng)絡(luò)D'，使得D'的總構(gòu)建費(fèi)用不超過費(fèi)用預(yù)算，且要求網(wǎng)絡(luò)D'中從始發(fā)點(diǎn)到目的點(diǎn)的通過能力達(dá)到最大.這就是最大通過能力問題，本論文討論了該問題的兩種特殊情形，即最大通過能力的路問題和容量相等的最大通過能力問題，分別給出多項(xiàng)式算法，并分析算法的時(shí)間復(fù)雜度.

關(guān)鍵詞：最大通過能力問題；多項(xiàng)式算法；時(shí)間復(fù)雜度

1　問題的現(xiàn)實(shí)背景及其模型

最大通過能力問題在社會(huì)生產(chǎn)生活中有著非常廣泛的應(yīng)用，特別是在工程建設(shè)中，比如在鋪設(shè)石油管道，架設(shè)輸電網(wǎng)絡(luò)，構(gòu)建通訊線路等情況時(shí)，常常會(huì)遇到這樣的問題，由于實(shí)際的需要，我們要計(jì)劃構(gòu)建從地點(diǎn)s到地點(diǎn)t的連通網(wǎng)絡(luò)，有許多構(gòu)建方案是可行的，但由于受到預(yù)算資金的制約，要求我們必須要在現(xiàn)有的預(yù)算下構(gòu)建一個(gè)性能最好的連通網(wǎng)絡(luò)，這里所謂的性能是指網(wǎng)絡(luò)中從地點(diǎn)s到地點(diǎn)t所能承載的最大輸送規(guī)模，這些類似的問題可以抽象為如下最大通過能力問題：

定義1給定一個(gè)雙賦權(quán)網(wǎng)絡(luò)D=（V，A;c，w;B;s，t)，V和A分別是網(wǎng)絡(luò)D的頂點(diǎn)集合和弧集合，c和w分別是關(guān)于弧的容量函數(shù)和構(gòu)建費(fèi)用函數(shù)，B是給定的構(gòu)建預(yù)算，s是給定的始發(fā)點(diǎn)，t是目的點(diǎn).要求在網(wǎng)絡(luò)D中尋找一個(gè)子網(wǎng)絡(luò)D'，使得D'的總構(gòu)建費(fèi)用，而從始發(fā)點(diǎn)s到目的點(diǎn)t的最大通過能力，即網(wǎng)絡(luò)D'中從始發(fā)點(diǎn)s到目的點(diǎn)t的最大流量，達(dá)到最大.

最大通過能力問題是強(qiáng)NP-完備的，它不存在擬多項(xiàng)式算法，下面僅討論該問題的兩種特殊情形，它們?nèi)匀挥蟹浅：玫默F(xiàn)實(shí)意義，針對(duì)這兩個(gè)問題，分別給出多項(xiàng)式算法.

2　最大通過能力的路問題

定義2最大通過能力的路問題是指，給定網(wǎng)絡(luò)D=（V，A;c，w;B;s，t)，其中V和A分別是網(wǎng)絡(luò)D的頂點(diǎn)集合和弧集合，c是弧上的容量函數(shù)，w是弧上的構(gòu)建費(fèi)用函數(shù)，B是給定的構(gòu)建預(yù)算，s和t分別是始發(fā)點(diǎn)和目的點(diǎn).要求在網(wǎng)絡(luò)D中尋找一條s-t路p，使得p的總構(gòu)建費(fèi)用B，且路p的通過能力達(dá)到最大.

顯然，一條路的通過能力是由路上弧的最小容量來決定的，對(duì)此，這里設(shè)計(jì)一個(gè)最短路迭代算法加以解決，并證明這是一個(gè)有效算法.

算法1最短路迭代算法

輸入：網(wǎng)絡(luò)D=（V，A;c，w;B;s，t).

輸出：一條通過能力最大的路P. Begin

Step1.初始時(shí)，令P=?；

Step2.利用Dijkstra算法在網(wǎng)絡(luò)D中尋找關(guān)于構(gòu)建費(fèi)用的s-t最短路，記其為p，其路長為，通過能力為；

Step3.若w（p)＞B或當(dāng)前網(wǎng)絡(luò)中不存在s-t最短路時(shí)，則算法終止，輸出當(dāng)前路P；否則，轉(zhuǎn)Step4；

Step4.清空P，并將路p存入P中，同時(shí)令D?D/{e|c（e) ≤c（p)}，轉(zhuǎn)Step2.

End

定理1最短路迭代算法是最大通過能力路問題的有效算法，并且它的時(shí)間復(fù)雜度為O（mn2).

證明設(shè)算法在循環(huán)到第k次循環(huán)時(shí)得到輸出解pk，當(dāng)前網(wǎng)絡(luò)為Dk，而在第k+1次循環(huán)時(shí)算法終止，這時(shí)路pk的構(gòu)建費(fèi)用w（pk)≤B.若pk不是問題的最優(yōu)解，且設(shè)p為最優(yōu)解，則w（pk)≤B，且有c（pk)＜c（p).由于算法在第k次循環(huán)的Step4中刪除了Dk中容量小于或等于c（pk)的弧，得到一個(gè)新的網(wǎng)絡(luò)Dk+1，而路p上的弧容量都不小于c（p)，故路p上的所有弧必存在新的網(wǎng)絡(luò)Dk+1中，因w（p)≤B，所以算法在k+1步不會(huì)終止，這與假設(shè)矛盾，故算法1所求得的解是最優(yōu)解.下面來分析算法的時(shí)間復(fù)雜度，由于在算法的每次循環(huán)中，都會(huì)在當(dāng)前的網(wǎng)絡(luò)中刪除一些弧，得到一個(gè)新的網(wǎng)絡(luò)進(jìn)入下次循環(huán)，如果每次都只刪除一條弧，最后網(wǎng)絡(luò)中不含弧，算法終止，那么算法最多循環(huán)m+1次，而每次循環(huán)要調(diào)用Dijkstra算法，由于Dijkstra算法的時(shí)間復(fù)雜度是O（n2)，所以最短路迭代算法的時(shí)間復(fù)雜度是O（mn2)，證畢.

3容量相等的最大通過能力問題

對(duì)于最大通過能力問題，甚至當(dāng)所有弧的構(gòu)建費(fèi)用全為1時(shí)，它仍然是強(qiáng)NP-完備的.在這里我們考慮所有弧的容量都相等時(shí)的情形，這個(gè)問題在現(xiàn)實(shí)中仍然具有廣泛的應(yīng)用性，例如，我們?cè)诩茉O(shè)電網(wǎng)時(shí)，常常利用的是同一種規(guī)格的電纜；我們?cè)阡佋O(shè)管道時(shí)，用的也可能是同種管道.因此，解決這個(gè)問題對(duì)我們的實(shí)際應(yīng)用還是很有幫助的.下面我們來討論這種情形.

設(shè)D*是關(guān)于網(wǎng)絡(luò)D的最大通過能力問題的一個(gè)最優(yōu)解，k是網(wǎng)絡(luò)D中在總構(gòu)建費(fèi)用不超過B的情況下，弧不交的s-t路的最大條數(shù)，c是網(wǎng)絡(luò)D中弧的容量.那么我們有以下定理.

定理2在構(gòu)建預(yù)算B的限制下，網(wǎng)絡(luò)D中從s到t的最大通過能力等于k?c.

證明設(shè)D*是網(wǎng)絡(luò)D在預(yù)算限制為B時(shí)，通過能力達(dá)到最大的子網(wǎng)絡(luò)，由于網(wǎng)絡(luò)D中所有弧的容量相等，所以D*的通過能力，即其最大流量等于D*中弧不交的s-t路的最大條數(shù)k*與弧容量c的乘積.設(shè)k是網(wǎng)絡(luò)D中在總構(gòu)建費(fèi)用不超過B的情況下，弧不交的s-t路的最大條數(shù)，顯然有k*≤k，又它們的通過能力為kc，而k*c≥kc，即k*≥k，故k*=k，定理得證.

從上述定理可知，要求在預(yù)算限制B下，通過能力最大的子網(wǎng)絡(luò)，實(shí)際可以轉(zhuǎn)化為在預(yù)算限制B下，求弧不交的s-t路的最大條數(shù)，而利用限制性最大流問題的相關(guān)算法，后者是容易求出來的.實(shí)際上，我們可以令網(wǎng)絡(luò)中所有弧的容量為1，其余參數(shù)不變，從而得到一個(gè)新的網(wǎng)絡(luò)，這樣就將后者轉(zhuǎn)化為求解在費(fèi)用限制B下新網(wǎng)絡(luò)的限制性最大流問題，我們要求得到的最大流是整數(shù)流，然后取這個(gè)整數(shù)流中所有流量為1的弧，就得到一些弧不交的路，并且因?yàn)槭亲畲笳麛?shù)流，所以這些弧不交的路是在的限制下的最大條數(shù).下面我們給出的算法是在限制性最大流問題的連續(xù)最短路算法[5]基礎(chǔ)上設(shè)計(jì)的多項(xiàng)式算法.

算法2修正的連續(xù)最短路算法

輸入：網(wǎng)絡(luò)D=（V，A;c，w;B;s，t).

輸出：通過能力最大的子網(wǎng)絡(luò).

Begin

Step1.令網(wǎng)絡(luò)D中所有弧的容量為1，令每條弧上單位流量的費(fèi)用等于該條弧上的構(gòu)建費(fèi)用，流的總費(fèi)用限制為B，構(gòu)造一個(gè)新網(wǎng)絡(luò)D'=（V，A;1，w;B;s，t).

Step2.利用連續(xù)最短路算法求解新網(wǎng)絡(luò)D'中從s到t的限制性整數(shù)最大流f：

（1）初始時(shí)，令流f=0，π=0是一個(gè)關(guān)于頂點(diǎn)的函數(shù)（稱為點(diǎn)勢），k表示所選s-t路的條數(shù)（初始時(shí)為0），構(gòu)造網(wǎng)絡(luò)D'關(guān)于初始流f的剩余網(wǎng)絡(luò)D'（f)，計(jì)算剩余網(wǎng)絡(luò)中關(guān)于弧的減小費(fèi)用函數(shù)wπ；

（2）當(dāng)B＞-π（t)時(shí)，執(zhí)行以下循環(huán)：在剩余網(wǎng)絡(luò)D'（f)中計(jì)算從s到所有點(diǎn)關(guān)于wπ的最短路長，記為關(guān)于頂點(diǎn)的函數(shù)d，此時(shí)尋找一條最短的s-t路p，在路p上增廣1個(gè)單位流，更新原始網(wǎng)絡(luò)中的流f，并重新構(gòu)造剩余網(wǎng)絡(luò)，π?π-d，更新減小費(fèi)用函數(shù)wπ，B?B+π（t)，k?k+1；

Step3.在所求得的網(wǎng)絡(luò)D'的限制性整數(shù)最大流f中，選取流值為1的弧，并輸出.

End

定理3修正的連續(xù)最短路算法能找到弧容量相等的最大通過能力問題的最優(yōu)解，并且時(shí)間復(fù)雜度為O（mn2).

證明由定理2可知，算法能夠找出弧容量相等的最大通過能力問題的最優(yōu)解.下面分析算法的時(shí)間復(fù)雜度，從算法中看到，時(shí)間復(fù)雜度主要由Step2決定，這一步調(diào)用了一次連續(xù)最短路算法，在每次連續(xù)最短路算法的循環(huán)過程中，都增廣一個(gè)單位的流，可見Step2最多進(jìn)行了m步循環(huán)，每步循環(huán)都調(diào)用了Dijkstra算法，而Dijkstra算法的時(shí)間復(fù)雜度為O（n2)，因此算法的時(shí)間復(fù)雜度為O（mn2)，證畢.

4　結(jié)論

最大通過能力問題具有很好的現(xiàn)實(shí)意義，但該問題是強(qiáng)NP-完備的.本文討論了該問題的兩種同樣具有現(xiàn)實(shí)意義的特殊情形，并給出了多項(xiàng)式時(shí)間算法，而對(duì)該問題的一般情形，有待進(jìn)一步研究探討，從而設(shè)計(jì)相關(guān)的近似算法.

參考文獻(xiàn)：

〔1〕田豐，馬仲蕃.圖與網(wǎng)絡(luò)流理論[M].北京：科學(xué)出版社，1985.

〔2〕J.A.Bondy，U.S.R.Murty.Graph Theory with Applications [M].American Elsever，New York，1976.

〔3〕C.H.Papadimitriou，K.Steiglitz.CombinatorialOptimization：Algorithms and Complexity[M].Printice Hall，1982.

〔4〕M.R.Garey，D.S.Johnson.Computer And Intractability，A Guide To The Theory Of NP-Completeness[M]. New York：W.H.Freeman，1979.

〔5〕R.K.Ahuja，J.B.Orlin.A Capacity Scaling Algorithm for the Constrained Maximum Flow Problem[J]. Cambridge，1995.

中圖分類號(hào)：O157.5

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1673-260X（2015）07-0005-02