限制性支撐樹最大容量擴(kuò)張問題

楊子蘭，楊惠娟，李 睿*

（1.麗江文化旅游學(xué)院信息學(xué)院，云南麗江 674199；2.昭通學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，云南昭通 657000）

隨著互聯(lián)網(wǎng)的不斷發(fā)展，人們的生活變得越來越網(wǎng)絡(luò)化、數(shù)據(jù)化、信息化、智能化，這給通信網(wǎng)絡(luò)的流量傳輸能力帶來嚴(yán)峻的考驗(yàn)。通信網(wǎng)絡(luò)分為有線通信網(wǎng)絡(luò)和無線通信網(wǎng)絡(luò)。盡管無線通信網(wǎng)絡(luò)有很好的發(fā)展優(yōu)勢，但是有線通信網(wǎng)絡(luò)一直保持著無可替代的地位。如5G 通信系統(tǒng)中5G 基站的建設(shè)需要密集組網(wǎng)，只有光纖通信網(wǎng)絡(luò)傳輸技術(shù)能為其提供低延時(shí)和高帶寬的通信，進(jìn)而實(shí)現(xiàn)5G 的順利入網(wǎng)〔1〕。光纖通信網(wǎng)絡(luò)屬于有線通信網(wǎng)絡(luò)。有線通信網(wǎng)絡(luò)往往是大型通信網(wǎng)絡(luò)的主干道和基礎(chǔ)設(shè)施，特別是考慮到遠(yuǎn)程通信的可靠性和穩(wěn)定性，有線通信具有不可替代的作用〔2〕。有線通信網(wǎng)絡(luò)在實(shí)際應(yīng)用中將金屬材質(zhì)的導(dǎo)線作為連通載體，可以傳輸?shù)男畔ㄎ谋尽⑽募D像、音頻等〔3〕。

文獻(xiàn)〔4〕中作者指出未來網(wǎng)絡(luò)作為戰(zhàn)略性新興產(chǎn)業(yè)的重要發(fā)展方向，預(yù)計(jì)在2030 年將支撐萬億級、人機(jī)物、全時(shí)空、安全、智能的連接與服務(wù)，將重點(diǎn)聚焦在加速業(yè)務(wù)創(chuàng)新、促進(jìn)運(yùn)營商轉(zhuǎn)型、滿足工業(yè)互聯(lián)網(wǎng)需求等方面的發(fā)展。面對如此龐大的需求壓力和發(fā)展壓力，對現(xiàn)有的網(wǎng)絡(luò)進(jìn)行升級變成學(xué)者們一直關(guān)注的一個(gè)熱點(diǎn)問題〔5-7〕，然而在現(xiàn)有的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)基礎(chǔ)上進(jìn)行升級，需要消耗資源，升級后網(wǎng)絡(luò)必須保證通信質(zhì)量且需要維護(hù)，這些都涉及費(fèi)用問題。因此，如何對現(xiàn)有的通信網(wǎng)絡(luò)進(jìn)行科學(xué)合理的升級使其滿足不斷增長的用戶流量需求成為一個(gè)重點(diǎn)問題。對通信網(wǎng)絡(luò)容量進(jìn)行升級不僅要考慮當(dāng)前用戶的流量需求、單位擴(kuò)容費(fèi)用以及擴(kuò)容后的維護(hù)費(fèi)用，還要確保通信質(zhì)量以及可靠性。與此同時(shí)，通信線路太長不僅會增加成本，還會影響通信質(zhì)量。

結(jié)合以上實(shí)際情況，為應(yīng)對高峰期客戶的流量需求值，為確保可靠的通信，本研究旨在原有的有線通信網(wǎng)絡(luò)中找到一個(gè)子網(wǎng)絡(luò)，對子網(wǎng)絡(luò)進(jìn)行適當(dāng)?shù)纳壥沟谜麄€(gè)子網(wǎng)絡(luò)的流量傳輸能力盡可能地大。同時(shí)，子網(wǎng)絡(luò)的線路總長不能超過限制值。求總費(fèi)用最少的網(wǎng)絡(luò)升級方案，本研究把用戶抽象成圖論中的頂點(diǎn)，把傳輸信息的連通載體抽象成圖論中的邊，提出基于流量需求d 的限制性支撐樹最大容量擴(kuò)張問題（the maximum capacity expansion of spanning tree problem with constraints，MCESTC）。

MCESTC 定義如下：給定一個(gè)無向圖G=（V，E，l，c，p，p'），其中V 表示圖G 的頂點(diǎn)集，E 表示圖G的邊集合，｜V｜=n，｜E｜=m。對?e∈E，設(shè)l（e）、c（e）、p（e）、p'（e）分別表示邊e 的長度權(quán)重、容量、單位擴(kuò)張費(fèi)用、單位邊維護(hù)費(fèi)用，且l（e）、c（e）、p（e）、p'（e）≥0，則p（e）+p'（e）表示邊e 上的單位邊擴(kuò)張總費(fèi)用。考慮在圖G 中找到一棵支撐樹T 使其滿足條件：（1）l（T）＝Σe∈Tl（e）≤L；（2）cap（T）≥d，其中L＞0表示長度權(quán)重限制指標(biāo)值，d＞0 表示當(dāng)前的流量需求值，cap（T）=min｛c（e）｜e∈T｝。?e∈E，設(shè)△c（e）表示邊e 上實(shí)際增加的容量，則可建立MCESTC 數(shù)學(xué)模型如下：

其中，Г 是圖G 中所有支撐樹構(gòu)成的集合。

本研究提出的MCESTC 是一種新的擴(kuò)容模型。與文獻(xiàn)〔5-7〕相比較，此模型不同之處在于不僅考慮了擴(kuò)容后的維護(hù)費(fèi)用，還考慮了整個(gè)子網(wǎng)絡(luò)T 的流量通行能力盡可能大于等于d。文獻(xiàn)〔5〕中網(wǎng)絡(luò)中支撐樹的邊擴(kuò)容問題屬于本研究的一種特殊情形。

由于限制性支撐樹問題（constrained spanning tree problem，CST）是NP-難問題，并且借鑒文獻(xiàn)〔5〕中命題1 的證明方法，可證明本研究的MCESTC 和CST 問題是多項(xiàng)式時(shí)間等價(jià)的，所以本研究MCESTC 問題也是NP-難問題。

本研究的創(chuàng)新點(diǎn)有3 個(gè)方面：第一個(gè)方面是模型的創(chuàng)新。本研究不僅考慮擴(kuò)容時(shí)的擴(kuò)張費(fèi)用，還考慮了擴(kuò)容后的維護(hù)費(fèi)用，并且還考慮了整個(gè)子網(wǎng)絡(luò)T 的流量通行能力盡可能大，得到的數(shù)學(xué)模型更符合實(shí)際情況。第二個(gè)方面是算法的創(chuàng)新。擴(kuò)容時(shí)，傳統(tǒng)的刪邊策略大都采用降低樹的長度權(quán)重值的策略，整個(gè)過程中從不允許樹的長度值增加，這樣容易出現(xiàn)無解的情況。本研究提出的算法中刪邊策略采用雙邊替換策略，允許增加樹的長度值，每一次的刪邊替換中，到底選擇增加樹的長度值還是選擇減少樹的長度值的策略，這取決于哪種策略對整個(gè)問題的貢獻(xiàn)最大。第三個(gè)方面是理論應(yīng)用的創(chuàng)新。本研究恰當(dāng)?shù)匕讯繄D、完美匹配等理論應(yīng)用在算法中，效果較好。

1 雙邊替換基礎(chǔ)知識

參考文獻(xiàn)〔8〕，對于?e∈E，設(shè)p*（e）=（p（e）+p'（e））△c（e）（權(quán)重p*（e）為邊e 的總擴(kuò)張費(fèi)用），得出以下定義：

定義1 （樹邊替換）設(shè)T 是圖G 的一棵樹，對于?e∈T，e'∈GT，假如有T｛e｝∪｛e'｝仍然構(gòu)成圖G 的一棵樹，則稱（e'，e）為圖G 中關(guān)于T 的一個(gè)樹邊替換。

定義2 設(shè)（e'，e）為圖G 中關(guān)于T 的一個(gè)樹邊替換。記l（e'，e）=l（e'）-l（e），p*（e'，e）＝p*（e'）-p*（e），則稱為長度與費(fèi)用權(quán)重之間的交換比率，即r（e'，e）表示費(fèi)用權(quán)重p*每改變一個(gè)單位，長度權(quán)重改變r(jià)（e'，e）個(gè)單位。

定義3 （雙邊替換）設(shè)T 是圖G 的一棵支撐樹，l（T）＞L，圖G 中所有關(guān)于T 的樹邊替換構(gòu)成的集合記為TER。設(shè)△L=L-l（T），△P*=P*OPT-p*（T），P*OPT是MCESTC 問題的一個(gè)最優(yōu)解，則定義以下3種類型的雙邊替換：

（1）（e'，e）∈TER，假如l（e'，e）＜0，p*（e'，e）≤0或l（e'，e）≤0，p*（e'，e）＜0，則稱（e'，e）是第一種類型的雙邊替換。圖G 中所有關(guān)于支撐樹T 的第一種類型的雙邊替換構(gòu)成的集合記為BER-Ⅰ；（2）設(shè)（e'1，e1）∈TER，l（e'1，e1）＜0，p*（e'1，e1）＞0，使得＜0，p*（e'，e）＞0｝；設(shè)（e'2，e2）∈TER，l（e'2，e2）＞0，使 得（e'2，e2）＝arg則假如r（e'1，e1）≥r（e'2，e2），稱（e'1，e1）為第二種類型的雙邊替換；假如r（e'1，e1）＜r（e'2，e2），稱（e'2，e2）為第三種類型的雙邊替換。圖G 中所有關(guān)于支撐樹T 的第二種類型的雙邊替換構(gòu)成的集合記為BER-Ⅱ，關(guān)于支撐樹T 的第三種類型的雙邊替換構(gòu)成的集合記為BER-Ⅲ。

引理1 設(shè)T，T ' 是圖G 的兩棵不同的支撐樹，記E1=E（T）E（T '），E2=E（T '）E（T）。構(gòu)造二部圖H=（U，V，E），其中U＝E1，V＝E2，E（H）＝｛（e'，e）｜e∈E1，e'∈E2，T｛e｝∪｛e'｝是一棵支撐樹｝〔8〕。

根據(jù)引理1，可以得出以下推論。

選擇我院2016年1月至2017年8月收治的70例COPD急性加重期患者為研究對象,以隨機(jī)數(shù)字表法分為A組與B兩組各35例。A組:男性19例,女性16例,年齡63~84歲,平均年齡(73.5±2.4)歲;COPD急性加重期病程3~16d,平均病程(8.0±1.5)d。B組:男性18例,女性17例,年齡63~85歲,平均年齡(74.0±2.2)歲;COPD急性加重期病程2~15d,平均病程(8.5±1.0)d。兩組患者一般資料無明顯差異(P>0.05),存在可比性。

推論1 設(shè)T 是圖G 的一棵支撐樹，T* 是MCESTC 問題的最優(yōu)支撐樹，則TT*與T*T 之間存在一個(gè)完美匹配P 滿足以下條件：

（1）｜P｜=｜TT*｜=｜T*T｜；（2）?x，y∈P，x≠y，有x∩y=?；（3）對于?（e'，e）∈P，有e∈TT*，e'∈T*T 成立，并且T｛e｝∪｛e'｝是一棵支撐樹。

2 MCESTC 問題的算法分析

在文獻(xiàn)〔8〕中，作者對CST 問題展開研究，并采用雙邊替換策略設(shè)計(jì)一個(gè)精確算法求解了邊的長度權(quán)重取值為1 或0 的CST 問題。本研究提出的MCESTC 問題是一種新的CST 問題且是NP-難的。本研究提出的擴(kuò)容模型的目標(biāo)函數(shù)與文獻(xiàn)〔8〕的目標(biāo)函數(shù)不同，并且模型多了整個(gè)子網(wǎng)絡(luò)T 的流量通行能力盡可能大于等于d 的約束條件，所以研究的問題比文獻(xiàn)〔8〕中的CST 問題更復(fù)雜，更具挑戰(zhàn)性。對于屬于NP-難的組合優(yōu)化問題，有些時(shí)候考慮的是能盡快找到一個(gè)滿意解，因此常常設(shè)計(jì)一個(gè)啟發(fā)式算法求解該類問題。受文獻(xiàn)〔8〕的啟發(fā)，對文獻(xiàn)〔8〕中的雙邊替換算法進(jìn)行修改，設(shè)計(jì)出一個(gè)雙邊替換算法求解擴(kuò)容模型。具體思路如下：

首先，考慮找到圖G 的一棵支撐樹T 且保證cap（T）=d。為實(shí)現(xiàn)此目標(biāo)，只需對?e∈E，當(dāng)容量c（e）＜d 時(shí)，取△c（e）＝d-c（e）；當(dāng)c（e）≥d 時(shí)，取△c（e）＝0 即可。其次，在不考慮長度權(quán)重限制的條件下，求出關(guān)于權(quán)重p*最小的支撐樹T。最后，檢查T的長度權(quán)重值，若l（T）≤L，則T 為MCESTC 問題的一個(gè)可行解，算法停止；若l（T）＞L，則采用允許增加T 的長度權(quán)重值的雙邊替換策略，對T 的長度權(quán)重進(jìn)行調(diào)整，直到調(diào)整后的T 滿足l（T）≤L。

當(dāng)l（T）＞L 時(shí)，假如關(guān)于支撐樹T 的第一類型的雙邊替換BER-Ⅰ≠?，則選擇（e'，e）∈BER-Ⅰ，置T=T∪｛e'｝｛e｝，這樣能保證不增加總費(fèi)用p*的前提下，最大可能地減少l（T）的值。假如關(guān)于支撐樹T 的第一類型的雙邊替換BER-Ⅰ=?，則首先選（e'1，e1）＝arg min（e'，e）∈TER｛r（e'，e）｜l（e'，e）＜0，p*（e'，e）＞0｝，即選擇費(fèi)用權(quán)重p*每增加一個(gè)單位時(shí)，單位長度減少量最大的雙邊替換（e'1，e1），此時(shí)；其次選擇（e'2，e2）＝arg max（e'，e）∈TER｛r（e'，e）｜l（e'，e）＞0，p*（e'，e）＜0｝，即選擇費(fèi)用權(quán)重p*每減少一個(gè)單位時(shí)，單位長度增加量最小的雙邊替換（e'2，e2），此時(shí)；最后，在（e'1，e1）與（e'2，e2）之間選擇對整體更有利的雙邊替換（e*'，e*）=arg max｛r（e'1，e1），r（e'2，e2）｝。置T ＝T ∪｛e*'｝｛e*｝，這樣即使選到BER-Ⅲ中的雙邊替換，也能保證在長度權(quán)重增加量較少的情況下，減少總費(fèi)用p*。根據(jù)以上思路，允許增加T 的長度權(quán)重的雙邊替換策略具體步驟如下：

第1 步：在圖G 中求出關(guān)于支撐樹T 的樹邊替換，記TER=｛（e'，e）｜e∈T，e'∈GT 且T｛e｝∪｛e'｝是一棵支撐樹｝。把TER 分成BER-Ⅰ、BER-Ⅱ、BER-Ⅲ3 類；第2 步：優(yōu)先選擇BER-Ⅰ中的雙邊替換進(jìn)行替換。若BER-Ⅰ=?，則在BER-Ⅱ、BER-Ⅲ中選擇r（e'，e）值最大的雙邊替換，即選擇雙邊替換（e*'，e*）=arg max（e'，e）∈TER｛r（e'，e）｜（e'，e）∈BER-Ⅱ或（e'，e）∈BER-Ⅲ｝，置T＝T∪｛e*'｝｛e*｝；第3 步：若l（T）≤L，則T 為MCESTC 問題的一個(gè)可行解，算法停止；若l（T）＞L，則重復(fù)第2 步，直到調(diào)整后的支撐樹T 滿足l（T）≤L。

當(dāng)T 是不考慮長度權(quán)重限制的條件下關(guān)于權(quán)重p*最小的支撐樹時(shí)，顯然關(guān)于支撐樹T 的第一類型的雙邊替換BER-Ⅰ=? 成立。綜合以上分析，設(shè)計(jì)詳細(xì)的算法步驟如下：

MCESTC 算法：

輸出：支撐樹T。

第1 步：置p*（e）＝（p（e）+p'（e））△c（e），構(gòu)造新圖G'=（V，E，p*，L，d）。其中?e∈E，當(dāng)容量c（e）＜d時(shí)，△c（e）=d-c（e）；當(dāng)c（e）≥d，△c（e）=0。

第2 步：在不考慮長度權(quán)重限制的條件下，用Prim 算法〔9〕在新圖G'中求出關(guān)于權(quán)重p*最小的支撐樹T。

第3 步：若l（T）≤L，則T 為MCESTC 問題的一個(gè)可行解，算法停止；若l（T）＞L，則轉(zhuǎn)第4 步。

第4 步：在圖G'中求出關(guān)于支撐樹T 的樹邊替換，記TER=｛（e'，e）｜e∈T，e'∈GT 且T｛e｝∪｛e'｝是一棵支撐樹｝。把TER 分成BER-Ⅰ、BER-Ⅱ、BER-Ⅲ3 類。

第5 步：優(yōu)先選擇BER-Ⅰ中的雙邊替換（e'，e）進(jìn)行替換。若BER-Ⅰ=?，則在BER-Ⅱ、BER-Ⅲ中選擇r（e'，e）值最大的雙邊替換，即選擇（e*'，e*）=arg max（e'，e）∈TER｛r（e'，e）｜（e'，e）∈BER-Ⅱ或（e'，e）∈BER-Ⅲ｝，置T＝T∪｛e*'｝｛e*｝，轉(zhuǎn)第3 步。

盡管有較多的多項(xiàng)式時(shí)間算法可以用來求解最小支撐樹問題〔10〕，但是到目前為止，Kruskal 算法〔11〕和Prim 算法是兩個(gè)比較簡單的算法，所以本研究算法中，采用Prim 算法在新圖G'中求出關(guān)于權(quán)重p*最小的支撐樹T。

定理1 若MCESTC 問題存在可行解，則算法MCESTC 一定能求出MCESTC 問題的一個(gè)滿意解，其算法時(shí)間復(fù)雜度為O（mn2）。

證明：設(shè)Ti是算法MCESTC 的第3 步至第5 步經(jīng)過第i 次循環(huán)得到的支撐樹，若l（Ti）≤L，則輸出可行解Ti，算法停止；否則不斷調(diào)用MCESTC 算法的第3 步至第5 步，進(jìn)行雙邊替換，直到l（Ti）≤L，輸出可行解Ti，算法停止。所以若MCESTC 問題存在可行解，則MCESTC 算法能求出MCESTC 問題的可行解。

算法第2 步考慮在新圖G'中求出關(guān)于權(quán)重p*最小的支撐樹T，即找出使得目標(biāo)函數(shù)值Σe∈Tp*（e）=Σe∈T（p（e）+p'（e））△c（e）最小的支撐樹T，如果l（T）≤L，則T 為MCESTC 問題的最優(yōu)解，算法停止；若l（T）＞L，則選擇對整個(gè)問題貢獻(xiàn)最大的雙邊替換進(jìn)行替換（見算法第5 步），直到l（T）≤L 為止。所以MCESTC 算法能求出MCESTC 問題的一個(gè)滿意解。

MCESTC 算法中的第1 步構(gòu)造新圖，能在線性時(shí)間內(nèi)完成；第2 步利用Prim 算法，求出關(guān)于權(quán)重p*最小的支撐樹T，時(shí)間復(fù)雜度為O（n2）；第3 步至第5 步最多循環(huán)l（T）次，且l（T）≤n，每一次循環(huán)中的算法復(fù)雜度主要取決于找到雙邊替換的復(fù)雜度，找到雙邊替換的復(fù)雜度為O（mn）。故MCESTC 算法的總的時(shí)間復(fù)雜度為O（mn2）。

3 實(shí)列

給定無向網(wǎng)絡(luò)圖G=（V，E，l，c，p，p'），見圖1。L=11，d=3，G 中每條邊上的權(quán)重?cái)?shù)據(jù)見表1。

圖1 網(wǎng)絡(luò)G

設(shè)p*（e）=（p（e）+p'（e））△c（e），根據(jù)MCESTC算法第1 步，得到表1 中△c（e）和p*（e）兩行的數(shù)據(jù)。根據(jù)MCESTC 算法第2 步，取v1為初始點(diǎn)，利用Prim算法求得關(guān)于權(quán)重p*最小的支撐樹T，見圖2。

圖2 支撐樹T

因?yàn)閘（T）＝22＞L，根據(jù)MCESTC 算法第4 步，求出關(guān)于T 的雙邊替換：不存在l（e'，e）＜0，p*（e'，e）≤0 或l（e'，e）≤0，p*（e'，e）＜0 的雙邊替換，也不存在l（e'，e）＞0，p*（e'，e）＜0 的雙邊替換，但是存在l（e'，e）＜0，p*（e'，e）＞0 的雙邊替換：（e2，e7），（e4，e9），（e8，e9），（e6，e9），（e2，e10）。根據(jù)MCESTC 算法第5 步有BER-Ⅰ=?、BER-Ⅱ=｛（e4，e7）｝、BER-Ⅲ=?，置T=T∪｛e4｝｛e9｝，T 的圖形見圖3。

圖3 修正的支撐樹T

同理，因?yàn)閘（T）=12＞L，再次調(diào)用MCESTC 算法第4 步至第5 步得出BER-Ⅰ=?、BER-Ⅱ=｛（e2，e10）｝、BER-Ⅲ=?，置T=T∪｛e1｝｛e10｝，此時(shí)因?yàn)閘（T）=11＝L，輸T，算法停止。可行解T 的圖形見圖4。

圖4 可行解支撐樹T