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

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

度、直徑約束最小生成樹(shù)問(wèn)題及其算法

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

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

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

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

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

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

1 問(wèn)題描述和模型

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

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

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

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

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

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

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

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

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

定理1DCBDMST問(wèn)題是NP-完全問(wèn)題.

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

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

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

則DCBDMST(D)問(wèn)題∈NP問(wèn)題.

2)再證BDMST(D)問(wèn)題可多項(xiàng)式變換到DCBDMST(D)問(wèn)題.

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

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

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

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

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

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

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

3 啟發(fā)式算法

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

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

Step 0初始化，任取節(jié)點(diǎn)v0∈V，S={v0}，令剩余度標(biāo)號(hào)re_d(v0)=dmax(v0)，距離標(biāo)號(hào)u(v0)=0，pred(v0)=0，ˉS=V-S;對(duì)ˉS中的節(jié)點(diǎn)令剩余度標(biāo)號(hào)re_d(vi)=dmax(vi)，距離標(biāo)號(hào)u(vi)=+∞，pred(vi)=0.當(dāng)前生成樹(shù)T=(S，E0)，E0=?;

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

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

Step 3將割［S，ˉS］中端點(diǎn)和權(quán)值都滿(mǎ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)樹(shù)T，即S=S∪v2'，E0=E0∪e*.更新節(jié)點(diǎn)v1'和v2'的剩余度標(biāo)號(hào)re_d(v1')=re_d(v1')-1和re_d(v2')=re_d(v2')-1，節(jié)點(diǎn)v2'的距離標(biāo)號(hào)u(v2')=u(v1')+1，節(jié)點(diǎn)v2'的前趨標(biāo)號(hào)pred(v2')= v1'.轉(zhuǎn)到Step 1.

算法時(shí)間復(fù)雜度分析:該算法主要計(jì)算量在Step 3求集合S'和Step 4查找集合S'中最小邊，求集合S'的時(shí)間復(fù)雜度為O(m)，查找S'中最小邊的時(shí)間復(fù)雜度為O(m)，則Step 3和Step 4的計(jì)算復(fù)雜度為O(m)，因?yàn)樗鼈冏疃鄨?zhí)行n-1步，所以該算法的時(shí)間復(fù)雜度為O(mn).

4 數(shù)值實(shí)驗(yàn)

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

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

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

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

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

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

5 結(jié)語(yǔ)

DCBDMST問(wèn)題是異常困難的組合優(yōu)化問(wèn)題，本文給出的啟發(fā)式算法能在一定程度上較好地求解此問(wèn)題.下一步的工作將為該問(wèn)題設(shè)計(jì)合適的智能算法如蟻群算法、遺傳算法等，將求解的結(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ì)算機(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.

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

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