石 磊，馮祖針，楊建強，龍 瑤

（紅河學(xué)院數(shù)學(xué)學(xué)院，云南蒙自 661100）

度、半徑約束最小生成樹問題及其算法

石 磊，馮祖針，楊建強，龍 瑤

（紅河學(xué)院數(shù)學(xué)學(xué)院，云南蒙自 661100）

提出了度、半徑約束最小生成樹問題，證明了該問題是NP-完全的.建立了該問題的數(shù)學(xué)規(guī)劃模型.進一步給出了快速啟發(fā)式求解算法，并分析了該算法的時間復(fù)雜性.分析和實例實驗表明該算法具有良好的效果.

最小生成樹問題；啟發(fā)式算法；度約束；半徑約束

最小生成樹（Minimum Spanning Tree，簡記為MST）［1］問題是網(wǎng)絡(luò)中的一個經(jīng)典問題，被廣泛應(yīng)用于網(wǎng)絡(luò)優(yōu)化問題中，如運輸問題、網(wǎng)絡(luò)路由選擇、分布式系統(tǒng)、預(yù)測與決策［2］等.

MST問題的各種變形問題受到普遍的重視和研究.文獻［3］對MST問題中的各節(jié)點加上一定的限制，得其一變形問題為度約束最小生成樹（Degree-Constrained Minimum Spanning Tree，簡記為DCMST）問題.文獻［4］研究了圖的每條邊含有多個權(quán)值的多目標(biāo)最小生成樹（Multi-Criteria Minimum Spanning Tree，簡記為MCMST）問題.單數(shù)據(jù)源節(jié)點的網(wǎng)絡(luò)通信中與生成樹相關(guān)的路由問題的研究通常為兩個主要方面：網(wǎng)絡(luò)綜合性能最優(yōu)化［5-6］，歸結(jié)為度約束最小生成樹問題；網(wǎng)絡(luò)中源節(jié)點到其他各節(jié)點的最大延遲最小化［7-8］，歸結(jié)為度約束最小半徑生成樹問題.上述MST變形問題都是NP-完全的.本文提出度、半徑約束最小生成樹（Degree-Constrained，Radius-Constrained Minimum Spanning Tree，簡記為DCRCMST）問題，此問題綜合考慮了上述網(wǎng)絡(luò)路由研究所考慮的兩個方面，因此有一定的實用價值.

1 問題描述和模型

設(shè)G＝（vs，V，E，D，W）是無向網(wǎng)絡(luò)，集合V的元素稱為節(jié)點，記為vi，其中，vs為V中唯一的根節(jié)點，簡稱根，且｜V｜＝n；集合E的元素稱為邊，（vi，vj）表示端點為vi和vj的邊，且｜E｜＝m；?vi∈V，對應(yīng)一個度約束值dmax（vi）∈N，稱為度約束，D＝｛dmax（vi）｜vi∈V｝；?（vi，vj）∈E，對應(yīng)一個非負權(quán)值wij或w（vi，vj），稱為長度或代價，W＝｛wij｜（vi，vj）∈E｝.設(shè)wij為正整數(shù).

定義2 度、半徑約束最小生成樹（DCRCMST）問題可以描述為尋找G的一個最小生成樹T，滿足當(dāng)前節(jié)點的度dT（vi）≤dmax（vi）（?vi∈T）和樹的半徑rad（T）≤Δmax（Δmax為半徑約束值）.取dmax（vi）和Δmax為正整數(shù).

其數(shù)學(xué)模型為

DCRCMST問題與諸多MST變形問題一樣，為NP-完全問題，則該問題無有效的算法，只能用啟發(fā)式算法或人工智能算法求解.下面將對DCRCMST問題的計算復(fù)雜性進行討論.

2 DCRCMST問題的計算復(fù)雜性證明

在研究一組合優(yōu)化問題的復(fù)雜性時，通常的處理方法是研究其對應(yīng)的判定問題.因此，將對DCRCMST問題對應(yīng)的判定形式（記為DCRCMST（D）［9］）進行研究.根據(jù)文獻［9］中的理論，要證明DCRCMST（D）為NP-完全問題，只需證明：①DCRCMST（D）∈NP；②一個NP-完全問題能多項式變換為DCRCMST（D）.

定義3 DCRCMST（D）問題：給定無向網(wǎng)絡(luò)G＝（vs，V，E，D，W），是否存在一棵以vs為根的生成樹T，使得T的總代價W（T）≤α1、半徑rad（T）≤α2以及每個節(jié)點的當(dāng)前度dT（vi）≤dmax（vi），其中，α1，α2∈Z＋.

定義4 DCMST（D）問題：給定無向網(wǎng)絡(luò)G＝（V，E，D，W），是否存在一棵生成樹T，使得T的總代價W（T）≤β1以及每個節(jié)點的當(dāng)前度dT（vi）≤dmax（vi），其中，β1∈Z＋.

定理 DCRCMST問題是NP-完全問題.

證明 選取一個已被證明為NP-完全的問題是度約束最小生成樹（DCMST）問題，給出DCRCMST問題和DCMST問題的判定形式.

（1）先證DCRCMST（D）問題∈NP問題.

①對任意DCRCMST（D）問題的一個實例Ⅰ，任取實例Ⅰ中一棵以vs為根的生成樹T′＝（vs，S′，E′0），則T′的字符串輸入長度是多項式時間內(nèi)可計算的.

因此DCRCMST（D）問題∈NP問題.

（2）再證DCMST（D）問題可多項式變換到DCRCMST（D）問題.

任取DCMST（D）問題的一個實例Ⅱ，Ⅱ是一個無向網(wǎng)絡(luò)G＝（V，E，D，W），是否存在一棵生成樹T，使得T的總代價W（T）≤β1以及每個節(jié)點的當(dāng)前度dT（vi）≤dmax（vi）.

Ⅱ有是的解，當(dāng)且僅當(dāng)對應(yīng)的Ⅱ′有是的解，即DCMST（D）問題可通過f變換到DCRCMST（D）問題.

變換f中構(gòu)造都是多項式時間內(nèi)可完成的，則f為多項式時間變換，即DCMST（D）問題可多項式變換到DCRCMST（D）問題.

綜上所述，DCRCMST（D）問題是NP-完全問題，即DCRCMST問題是NP-完全問題.

3 啟發(fā)式算法

本文提出一個基于Prim算法的啟發(fā)式算法.它從網(wǎng)絡(luò)G＝（vs，V，E，D，W）的根vs出發(fā)，不斷擴展一棵子樹T＝（vs，S，E0），直到S包括原網(wǎng)絡(luò)的全部節(jié)點，即｜S｜＝｜V｜，便得到滿足度、半徑約束的生成樹T.

其基本思想是：對V中的每個節(jié)點vi，賦予3個數(shù)值（稱為標(biāo)號）：剩余度標(biāo)號re＿d（vi），記錄該節(jié)點此時的剩余度，即還可接納的最大邊數(shù)；距離標(biāo)號u（vi），記錄在最終生成樹中vs到該節(jié)點可能的長度上界；前趨標(biāo)號pred（vi），記錄從vs到該節(jié)點的路長取到上界u（vi），該路中節(jié)點vi前面的那個直接前趨節(jié)點.從vs出發(fā)，每次選擇割［S］中滿足約束的權(quán)值最小的邊，然后修改節(jié)點的標(biāo)號，直到｜S｜＝｜V｜.算法結(jié)束時，距離標(biāo)號u（vi）表示生成樹T中從vs到該節(jié)點的路長，生成樹T的半徑

算法的具體步驟如下：

Step 0 初始化，S＝｛vs｝，令剩余度標(biāo)號re＿d（vs）＝dmax（vs），距離標(biāo)號u（vs）＝0，pred（vs）＝0，ˉS＝V-S；對ˉS中的節(jié)點，令剩余度標(biāo)號re＿d（vi）＝dmax（vi），距離標(biāo)號u（vi）＝＋∞，pred（vi）＝0；當(dāng)前生成樹T＝（vs，S，E0），E0＝?；

Step 1 若S＝V，則根據(jù)節(jié)點的前趨標(biāo)號輸出生成樹T，結(jié)束，否則轉(zhuǎn)到Step 2；

Step 2 若割［S，ˉS］＝?，則G不連通，結(jié)束，否則轉(zhuǎn)到Step 3；

Step 3 將割［S，ˉS］中端點和權(quán)值都滿足約束的邊e加入到集合S′，即對于S′中任意的邊e＝（v1，v2）（v1∈S，v2∈ˉS），都有re＿d（v1）＞0，re＿d（v1）-1＞0，u（v1）＋w（v1，v2）≤Δmax（Δmax為半徑約束值）.若S′＝?，則查找失敗，結(jié)束，否則轉(zhuǎn)到Step 4；

Step 4 選擇S′中權(quán)值最小邊e＊＝（v′1，v′2）加入到當(dāng)前生成樹T，即S＝S∪v′2，E0＝E0∪e＊；更新節(jié)點v′1和v′2的剩余度標(biāo)號re＿d（v′1）＝re＿d（v′1）-1和re＿d（v′2）＝re＿d（v′2）-1，節(jié)點v′2的距離標(biāo)號u（v′2）＝u（v′1）＋w（v′1，v′2），節(jié)點v′2的前趨標(biāo)號pred（v′2）＝v′1；轉(zhuǎn)到Step 1.

算法的時間復(fù)雜度分析：該算法主要計算量是在Step 4查找割［S，ˉS］中滿足約束條件的最小邊，該步的計算復(fù)雜度為o（m），因為Step 4最多執(zhí)行n-1步，所以該算法的時間復(fù)雜度為o（mn）.

4 數(shù)值實驗

為了測試算法的效果，用MATLAB編程測試了大量的數(shù)據(jù)實例，均獲得了良好的效果，這里只列舉部分結(jié)果.

例1 如圖1所示，節(jié)點規(guī)模n＝5，節(jié)點的度約束在節(jié)點標(biāo)號括號內(nèi)給出，邊上數(shù)字為邊的權(quán)值，半徑約束為5，設(shè)節(jié)點v1為根.

圖1 例1中網(wǎng)絡(luò)示意圖Fig.1 Network schematic of example 1

用本算法求得度、半徑約束最小生成樹T如圖2所示，總代價W（T）＝7，半徑rad（T）＝4.

圖2 例1中度、半徑約束的最小生成樹Fig.2 Degree-constrained，radius-constrainedminimum spanning tree in example 1

例2 選用研究度約束最小生成樹常用的數(shù)據(jù)實例［3，10］，節(jié)點規(guī)模n＝8，度限制dmax＝（dv1， dv2，…，dv8）＝｛3，3，3，3，3，3，3，3｝.設(shè)半徑約束為50，節(jié)點v1為根.邊的權(quán)矩陣為

用本算法求得度、半徑約束最小生成樹T，總代價W（T）＝125，半徑rad（T）＝49.

例3 為對大規(guī)模數(shù)據(jù)實例進行測試，現(xiàn)隨機生成一個n個節(jié)點的無向網(wǎng)絡(luò)Kn，網(wǎng)絡(luò)中邊的權(quán)值為［1，14］之間的隨機整數(shù)，節(jié)點的度約束為［1，［n／2］］之間的一個隨機整數(shù).分別取節(jié)點數(shù)n＝10，50，100，150，200，半徑約束分別為20，40，60，80，100.設(shè)節(jié)點v1為根.

用本算法分別求得度、半徑約束最小生成樹T的總代價和半徑如圖3所示.

圖3 例3中度、半徑約束的最小生成樹的總代價和半徑Fig.3 Total costs and radius of degree-constrained，radius-constrained minimum spanning tree in example 3

5 結(jié) 語

DCMST問題屬于異常困難的組合優(yōu)化問題，DCRCMST問題是比DCMST問題復(fù)雜性更高的問題，求解的困難程度與度約束、半徑約束以及圖的連接性態(tài)有關(guān).本文給出的啟發(fā)式算法能在一定程度上較好地求解此問題.其他更好的求解算法有待進一步研究.

［1］Ahuja R K，Magnanti T L，Orlin J B.Network Flows：Theory，Algorithms，and Applications［M］.Beijing：Mechanical Industry Press，2005.

［2］李世娟，馬驥，白鷺.基于改進ID3算法的決策樹構(gòu)建［J］.沈陽大學(xué)學(xué)報，2009，21（6）：23-25.

［3］Narula S C，Ho C A.Degree-constrained minimum spanning tree［J］.Computers and Operations Research，1980，7（4）：239-249.

［4］Fernandez F R，Hinojosa M A，Puerto J.Multi-criteria minimum cost spanning tree games［J］.European Journal of Operational Research，2004，158（2）：399-408.

［5］Pendarakis D，Shi S，Verma D，et al.ALMI：An Application Level Multicast Inf rast ructure［C］∥Proceedings of the 3rd USENIX Symposium on Internet Technologies ＆Systems.San Francisco，2001：49-60.

［6］Chu Y H，Rao S G，Zhang H.A Case for End System Multicast［C］∥Proceedings of the ACM SIGMETRICS. Santa Clara，2002：1-12.

［7］吳家皋，葉曉國，姜愛全.一種異構(gòu)環(huán)境下覆蓋多播網(wǎng)絡(luò)路由算法［J］.軟件學(xué)報，2005，16（6）：1112-1120.

［8］Banerjee S，Bhattacharjee B.A Comparative Study of Application Layer Multicast Protocols［C］∥Submitted for Review.Francis，2002：17-25.

［9］Papadimitriou C H.Computational Complexity［M］.Boston：Addison Wesley，2004.

［10］Narula S C，Ho C A.Degree-constrained minimum spanning tree［J］.Computers and Operations Research，1980，7（4）：239-249.

Degree-Constrained，Radius-Constrained Minimum Spanning Tree Problem and its Algorithm

SHI Lei，F(xiàn)ENG Zuzhen，YANG Jianqiang，LONG Yao

（Department of Mathematics，Honghe University，Mengzi 661100，China）

The degree-constrained，radius-constrained minimum spanning tree problem was put forward，and it was proved to be NP-complete.A mathematics programming model of the problem and a fast heuristic algorithm were proposed to solve the model.The time complexity of the algorithm was analyzed.The algorithm was proved to be effective by analysis and experiments.

minimum spanning tree problem；heuristic algorithm；degree-constrained；radius-constrained

TP 393.4

A

1008-9225（2012）04-0063-04

2012-02-03

云南省自然科學(xué)基金資助項目（2008CD186）.

石 磊（1984-），男，湖南衡陽人，紅河學(xué)院助教，碩士.

李 艷】