石磊，馮祖針，楊建強(qiáng)

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

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

石磊，馮祖針，楊建強(qiáng)

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

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

最小生成樹;啟發(fā)式算法;度約束;直徑約束

最小生成樹(minimum spanning tree，MST)［1］問題是網(wǎng)絡(luò)中的一個經(jīng)典問題，被廣泛應(yīng)用于網(wǎng)絡(luò)優(yōu)化問題中.MST問題中2個變形問題度約束最小生成樹(degree-constrained minimum spanning tree，DCMST)［2-3］問題和直徑約束最小生成樹(bounded diameter minimum spanning tree，BDMST)［4-5］問題受到普遍的重視和研究.文獻(xiàn)［6］證明了DCMST問題和當(dāng)直徑約束值Δ∈［4，n-1)的BDMST問題為NP -完全問題.

DCMST問題和BDMST問題都有著很強(qiáng)的應(yīng)用背景，如網(wǎng)絡(luò)通信、資源優(yōu)化、預(yù)測決策等.在某些領(lǐng)域求最小生成樹時，其數(shù)學(xué)模型中節(jié)點同時受到度約束和直徑約束，如覆蓋多播路由［7］.現(xiàn)有研究并未考慮節(jié)點需同時滿足度約束和直徑約束的最小生成樹問題，而此問題有一定的應(yīng)用價值.因此本文提出度、直徑約束最小生成樹(degree-constrained，radius-constrained minimum spanning tree，DCBDMST)問題，它是一個NP-完全問題，即不存在多項式求解算法，同時給出了DCBDMST問題的啟發(fā)式求解算法.

1 問題描述和模型

給定無向網(wǎng)絡(luò)G=(V，E，D，W)，任意節(jié)點vi∈V，且|V|=n;任意邊e=(vi，vj)∈E，且|E|=m.對?vi∈V對應(yīng)一個度約束值dmax(vi)∈N，稱為度約束，D={dmax(vi)|vi∈V}.對?(vi，vj)∈E對應(yīng)一個非負(fù)權(quán)值w(vi，vj)，稱為長度或代價，W={w(vi，vj) |(vi，vj)∈E}.

定義1［4］給定樹T=(ˉV，ˉE)，樹中2個節(jié)點的最大距離(所含邊的數(shù)目)稱為樹T的直徑，簡記diam(T).

定義2度、直徑約束最小生成樹(DCBDMST)問題可以描述為尋找G的一個最小生成樹T，滿足當(dāng)前節(jié)點的度dT(vi)≤dmax(vi)(?vi∈T)和樹的直徑diam(T)≤Δ，且4≤Δ≤n-1.取dmax(vi)和Δ是正整數(shù).

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

式(1)為目標(biāo)函數(shù)，式(2)為約束條件.下節(jié)將對DCBDMST問題的計算復(fù)雜性進(jìn)行討論.

2 DCBDMST計算復(fù)雜性證明

研究組合優(yōu)化問題復(fù)雜性通常的方法是研究其對應(yīng)的判定問題.因此將對DCBDMST問題對應(yīng)的判定形式(記為DCBDMST(D)［8］)進(jìn)行研究.要證明DCBDMST(D)問題為NP-完全問題只需證明［8］:①DCBDMST(D)問題∈NP;②一個NP-完全問題能經(jīng)多項式變換為DCBDMST(D)問題.

定義3BDMST(D)問題:給定無向網(wǎng)絡(luò)G= (V，E，D，W)，是否存在一棵生成樹T，使得T的總代價W(T)≤α1和直徑diam(T)≤Δ1(4≤Δ1≤n-1)，其中α1，Δ1∈Z+.

定義4DCBDMST(D)問題:給定無向網(wǎng)絡(luò)G= (V，E，D，W)，是否存在一棵生成樹T，使得T的總代價W(T)≤α2、直徑diam(T)≤Δ2(4≤Δ2≤n-1)和每個節(jié)點的當(dāng)前度dT(vi)≤dmax(vi)，其中α2，Δ2∈Z+.

定理1DCBDMST問題是NP-完全問題.

證明選取一個已被證明為NP-完全的問題是直徑約束最小生成樹(BDMST)問題，給出DCBDMST問題和BDMST問題的判斷形式.

1)先證DCBDMST(D)問題∈NP問題.

a.任意DCBDMST(D)問題的一個實例I，任取實例I中的生成樹T'=(S'，E')，則T'的字符串輸入長度是多項式時間內(nèi)可計算的;

則DCBDMST(D)問題∈NP問題.

2)再證BDMST(D)問題可多項式變換到DCBDMST(D)問題.

任取BDMST(D)問題的一個實例Ⅱ，Ⅱ是一個無向網(wǎng)絡(luò)G=(V，E，D，W)，是否存在一棵生成樹T，使得T的總代價W(T)≤α1和直徑diam(T)≤Δ1.

構(gòu)造Ⅱ的一個變換f:

令ˉV=V，ˉE=E，ˉW=W;對?vi∈ˉV，賦予度約束值dmax(vi)=n;取α2=α1，Δ2=Δ1.是否存在一棵的生成樹ˉT，使得ˉT的總代價W(ˉT)≤α2、直徑diam(ˉT)≤Δ2和每個節(jié)點的當(dāng)前度dT(vi)≤dmax(vi).

則實例Ⅱ通過變換f得到了DCBDMST(D)問題的一個實例，記為Ⅱ':ˉG=(ˉV，ˉE，ˉD，ˉW)，是否存在總代價、直徑和每個節(jié)點都滿足度約束的生成樹ˉT.

若Ⅱ有解當(dāng)且僅當(dāng)對應(yīng)Ⅱ'有解，即BDMST (D)問題可通過f變換到DCBDMST(D)問題.

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

綜上所述，DCBDMST(D)問題是NP-完全問題，因此DCBDMST問題是NP-完全問題.證畢.

3 啟發(fā)式算法

Prim算法是MST問題高效的多項式時間內(nèi)求解算法，本文在Prim算法基礎(chǔ)上為DCBDMST(D)提出一個啟發(fā)式求解算法.它從網(wǎng)絡(luò)G=(V，E，D，W)任意一個節(jié)點出發(fā)，每次選擇滿足約束條件的邊e，不斷的擴(kuò)展一棵子樹T=(S，E0)，直到S包括原網(wǎng)絡(luò)的全部節(jié)點即

其基本思想是:對V中每個節(jié)點vi，賦予3個數(shù)值(稱為標(biāo)號):①剩余度標(biāo)號re_d(vi)，記錄該節(jié)點此時的剩余度即該節(jié)點還可接納的最大邊數(shù);②距離標(biāo)號u(vi)，設(shè)出發(fā)的節(jié)點為v0，記錄在當(dāng)前生成樹T中v0到該節(jié)點經(jīng)過邊的總數(shù)目，則當(dāng)前樹T的直徑diam(T)為最大的2個距離標(biāo)號之和;③前趨標(biāo)號pred(vi)，記錄從v0到該節(jié)點的路長取到u(vi)，該路中節(jié)點vi前面的那個直接前趨節(jié)點，前趨標(biāo)號用來查找最終的生成樹.從v0出發(fā)，每次選擇割［S，ˉS］中滿足約束的權(quán)值最小的邊，然后修改節(jié)點的標(biāo)號，直到.算法具體步驟如下:

Step 0初始化，任取節(jié)點v0∈V，S={v0}，令剩余度標(biāo)號re_d(v0)=dmax(v0)，距離標(biāo)號u(v0)=0，pred(v0)=0，ˉS=V-S;對ˉS中的節(jié)點令剩余度標(biāo)號re_d(vi)=dmax(vi)，距離標(biāo)號u(vi)=+∞，pred(vi)=0.當(dāng)前生成樹T=(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(v2)＞0和diam(T∪e)≤Δ(Δ為直徑約束值).若S'=?，則查找失敗，結(jié)束.否則轉(zhuǎn)到Step 4;

Step 4選擇選S'中最小邊e*=(v1'，v2')加入到當(dāng)前生產(chǎn)樹T，即S=S∪v2'，E0=E0∪e*.更新節(jié)點v1'和v2'的剩余度標(biāo)號re_d(v1')=re_d(v1')-1和re_d(v2')=re_d(v2')-1，節(jié)點v2'的距離標(biāo)號u(v2')=u(v1')+1，節(jié)點v2'的前趨標(biāo)號pred(v2')= v1'.轉(zhuǎn)到Step 1.

算法時間復(fù)雜度分析:該算法主要計算量在Step 3求集合S'和Step 4查找集合S'中最小邊，求集合S'的時間復(fù)雜度為O(m)，查找S'中最小邊的時間復(fù)雜度為O(m)，則Step 3和Step 4的計算復(fù)雜度為O(m)，因為它們最多執(zhí)行n-1步，所以該算法的時間復(fù)雜度為O(mn).

4 數(shù)值實驗

本節(jié)對算法的性能進(jìn)行分析，用Matlab編程實現(xiàn)本算法，大量實驗結(jié)果表明此算法有較高的效率.下面列舉了部分實驗結(jié)果.

例1對大規(guī)模隨機(jī)數(shù)據(jù)的實例進(jìn)行測試，借鑒文獻(xiàn)［9］生成數(shù)據(jù)的方法，隨機(jī)生成n個節(jié)點的無向完全網(wǎng)絡(luò)G，網(wǎng)絡(luò)中邊的權(quán)值為［1，9］之間的隨機(jī)整數(shù)，節(jié)點的度約束為［1，「n/2?］之間的一個隨機(jī)整數(shù).分別取節(jié)點數(shù)n=50、100、250、500、1 000，直徑約束值分別取Δ=10、15、20、25、30.

分別求得度、直徑約束最小生成樹的總代價W(T)和直徑diam(T)如表1.通過與各實例中求得不含任何約束的最小生成樹進(jìn)行比較，可知此算法有較好的效果.

表1 啟發(fā)式算法求的度、直徑約束最小生成樹

例2選用Beasley’s OR-library(http:// www.people.brunel.ac.uk)提供的例子.Beasley’s OR-library給出不同規(guī)模的度量施泰納樹問題的很多例子，每個規(guī)模提供15個例子.算例說明:n表示規(guī)模即節(jié)點總數(shù)、Number表示對應(yīng)規(guī)模的第幾個例子、節(jié)點的度約束取［1，「n/2?］之間的一個隨機(jī)整數(shù).用本算法求解的結(jié)果如表2.

表2 本啟發(fā)式算法求解例2結(jié)果

5 結(jié)語

DCBDMST問題是異常困難的組合優(yōu)化問題，本文給出的啟發(fā)式算法能在一定程度上較好地求解此問題.下一步的工作將為該問題設(shè)計合適的智能算法如蟻群算法、遺傳算法等，將求解的結(jié)果與本文求解的結(jié)果進(jìn)行比較分析.

［1］AHUJA R K，MAGNANTI T L，ORLIN J B.Network flows:Theory，algorithms，and applications［M］.Beijing: Mechanical-Industry Press，2005.

［2］NARULA S C，HO C A.Degree-constrained minimum spanning tree［J］.Computers and Operations Research，1980，7(4):239-249.

［3］TORKESTANI J A.Degree-constrained minimum spanning tree problem in stochastic graph［J］.Cybernetics and Systems，2012，43(1):1-21.

［4］JULSTROM B A.Greedy heuristics for the bounded diameter minimum spanning tree problem［J］.Journal of Experimental Algorithmics(JEA)，2009，14(1):1-14.

［5］LUCENA A，RIBEIRO C C，SANTOS A C.A hybrid heuristic for the diameter constrained minimum spanning tree problem［J］.Journal of Global Optimization，2010，46 (3):363-381.

［6］GAREY M R，JOHNSON D S.Computers and intractability:A guide to the theory of NP-completeness［M］.San Francisco:WH Freeman＆Co，1979:206-218.

［7］吳家皋.覆蓋多播路由的算法及協(xié)議研究綜述［J］.計算機(jī)科學(xué)，2007，34(6):7-12.

［8］PAPADIMITRIOU C H.Computational complexity［M］. Boston:Addison Wesley，2004.

［9］BINH H T T，HOAI N X，MCKAY R I.A new hybrid genetic algorithm for solving the bounded diameter minimum spanning tree problem［C］//IEEE World Congress on Computational Intelligence.Hong Kong，2008:3128-3134.

(責(zé)任編輯莊紅林)

Degree-Constrained and Diameter-Constrained Minimum Spanning Tree Problem and Its Algorithm

SHI Lei，F(xiàn)ENG Zu-zhen，YANG Jian-qiang
(Department of Mathematics，Honghe University，Mengzi 661100，China)

The degree-constrained and diameter-constrained minimum spanning tree problem was discussed，which proved to be NP-Complete.A mathematical programming model of the problem was proposed.A heuristic algorithm was proposed to solve this problem，whose time complexity was O(mn).The algorithm was proved to be effective through analysis and experiments.

minimum spanning tree;heuristic algorithm;degree-constrained;diameter-constrained

O 157.6

A

1672-8513(2012)04-0295-03

10.3969/j.issn.1672-8513.2012.04.016

2012-03-29.

國家自然科學(xué)基金(11161020);紅河學(xué)院碩博基金(10BSS136).

石磊(1984-)，男，碩士，助教.主要研究方向:網(wǎng)絡(luò)安全、智能算法.