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

（紅河學院數學學院，云南蒙自 661100）

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

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

（紅河學院數學學院，云南蒙自 661100）

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

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

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

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

1 問題描述和模型

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

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

其數學模型為

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

2 DCRCMST問題的計算復雜性證明

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

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

定義4 DCMST（D）問題：給定無向網絡G＝（V，E，D，W），是否存在一棵生成樹T，使得T的總代價W（T）≤β1以及每個節(jié)點的當前度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′的字符串輸入長度是多項式時間內可計算的.

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

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

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

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

變換f中構造都是多項式時間內可完成的，則f為多項式時間變換，即DCMST（D）問題可多項式變換到DCRCMST（D）問題.

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

3 啟發(fā)式算法

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

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

算法的具體步驟如下：

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

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

Step 2 若割［S，ˉS］＝?，則G不連通，結束，否則轉到Step 3；

Step 3 將割［S，ˉS］中端點和權值都滿足約束的邊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′＝?，則查找失敗，結束，否則轉到Step 4；

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

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

4 數值實驗

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

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

圖1 例1中網絡示意圖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 選用研究度約束最小生成樹常用的數據實例［3，10］，節(jié)點規(guī)模n＝8，度限制dmax＝（dv1， dv2，…，dv8）＝｛3，3，3，3，3，3，3，3｝.設半徑約束為50，節(jié)點v1為根.邊的權矩陣為

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

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

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

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

5 結 語

DCMST問題屬于異常困難的組合優(yōu)化問題，DCRCMST問題是比DCMST問題復雜性更高的問題，求解的困難程度與度約束、半徑約束以及圖的連接性態(tài)有關.本文給出的啟發(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算法的決策樹構建［J］.沈陽大學學報，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］吳家皋，葉曉國，姜愛全.一種異構環(huán)境下覆蓋多播網絡路由算法［J］.軟件學報，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，FENG 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

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

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

李 艷】