直徑限制最小生成樹問題研究

直徑限制最小生成樹問題研究

姜娜

(內(nèi)蒙古大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，內(nèi)蒙古 呼和浩特 010021)

摘要：直徑限制最小生成樹問題是一個(gè)經(jīng)典的網(wǎng)絡(luò)優(yōu)化問題。本文對(duì)直徑限制最小生成樹問題進(jìn)行了綜述，介紹了該問題的研究背景、數(shù)學(xué)模型以及相關(guān)的概念，并對(duì)問題的求解方法進(jìn)行了歸納總結(jié)。

關(guān)鍵詞：直徑限制；最小生成樹；非完全圖；BDMST

收稿日期：*2015-04-27

作者簡(jiǎn)介：姜娜(1988- )，女， 蒙古族，內(nèi)蒙古通遼市人，碩士研究生,研究方向：算法分析與設(shè)計(jì)。

中圖分類號(hào)：O221.7文獻(xiàn)標(biāo)識(shí)碼：A

0引言

最小生成樹[1](Minimum Spanning Tree 簡(jiǎn)稱MST)是圖論、最優(yōu)化理論、算法分析與設(shè)計(jì)等諸多領(lǐng)域研究的重要課題，在實(shí)際問題中應(yīng)用廣泛，如網(wǎng)絡(luò)設(shè)計(jì)、公交車線路設(shè)計(jì)、排水系統(tǒng)設(shè)計(jì)等問題；通常情況下，這些問題可轉(zhuǎn)化為最小生成樹問題求解。不過，單純的生成樹問題是一個(gè)理想狀態(tài)，在現(xiàn)實(shí)應(yīng)用中，隨著信息技術(shù)不斷提高，大數(shù)據(jù)量、高傳輸速度、高清晰度要求現(xiàn)代網(wǎng)絡(luò)不再是簡(jiǎn)單地連通，而是要高質(zhì)量的傳遞信息，這就要求控制成本的同時(shí)網(wǎng)絡(luò)的連通直徑也不能沒有限制。為了解決這類問題，便引出了直徑限制最小生成樹[2](Bounded-Diameter Minimum Spanning Tree,簡(jiǎn)稱BDMST)問題。

直徑限制最小生成樹問題在資源優(yōu)化問題中應(yīng)用廣泛，比如網(wǎng)絡(luò)設(shè)計(jì)中的網(wǎng)絡(luò)直徑選擇，將直接影響著網(wǎng)絡(luò)的傳輸速度、網(wǎng)絡(luò)能耗以及信號(hào)傳遞的快慢等，在路由優(yōu)化中，直徑的限制，也便于設(shè)備部署的設(shè)計(jì)和維護(hù)。因此，直徑限制最小生成樹問題的研究，有著重要的理論和應(yīng)用價(jià)值。

1BDMST問題相關(guān)概念介紹

定義1.2任意兩結(jié)點(diǎn)之間都有一條邊直接相連的圖稱為完全圖，否則，稱為非完全圖。

定義1.3如果V1?V,E1?E，那么圖H=(V1,E1)稱為G=(V,E)的子圖，記作H?G.如果H是G的子圖，且V(H)=F(G)，E(H)?E(G)，則稱H是G的生成子圖或支撐子圖。

定義1.4結(jié)點(diǎn)與邊交替出現(xiàn)的序列v0e1v1e2，…，v1，稱為結(jié)點(diǎn)v0到v1的鏈。其中，結(jié)點(diǎn)vi-1和vi是邊ei的兩個(gè)端點(diǎn)(i=1,2,…,l)。稱結(jié)點(diǎn)v0為鏈的始點(diǎn)，結(jié)點(diǎn)v1為鏈的終點(diǎn)。鏈中邊的條數(shù)稱為鏈長(zhǎng)度。

若鏈中邊各異，則稱為跡；若鏈中結(jié)點(diǎn)各異，則稱為路。若v0=vl稱為閉的，否則稱為開的。閉的路徑稱為圈。

定義1.5如果圖G中每一對(duì)結(jié)點(diǎn)之間都有一條路連接，則稱圖G是連通圖，否則，稱G是非連通圖。

定義1.6若圖G中存在從結(jié)點(diǎn)u到結(jié)點(diǎn)v的路徑，其中路徑長(zhǎng)度最小的那條稱為u到v的最短路徑，其長(zhǎng)度稱為u到v的距離，記作dG(u,v) 。

定義1.8設(shè)圖G是連通圖，對(duì)它的每條邊都賦予一個(gè)數(shù)值，稱之為邊的權(quán)值，邊e1的權(quán)值記為wi=w(ei),i=1,2,…,m，全部邊的權(quán)值w={w1,w2,…,wm}，賦予權(quán)值的圖稱為賦權(quán)圖或網(wǎng)絡(luò)。

定義1.9對(duì)于圖G的任一子圖H，圖H的權(quán)值w(H)定義為其邊的權(quán)值和，設(shè)T是圖G的生成樹，且權(quán)值在G的所有生成樹中最小，則T稱為圖G的最小生成樹。

定義1.10設(shè)T是圖G的生成樹，D是直徑限制，若樹T的直徑DT滿足要求的直徑限制(DT≤D)，則稱T為圖G滿足直徑限制的生成樹，若T還是所有滿足直徑限制的生成樹中具有最小權(quán)的樹，則T稱為圖G的直徑限制最小生成樹。

2BDMST問題的數(shù)學(xué)模型

給定連通的賦權(quán)無(wú)向圖G=(V,E,W)，其中V表示圖的頂點(diǎn)集，E表示圖的邊集，W是圖的邊的權(quán)值。設(shè)S為G的所有生成樹的集合，T是G的一個(gè)生成樹，DT是樹T的直徑.設(shè)D是G的生成樹的直徑限制，因此，BDMST問題的數(shù)學(xué)模型[3]為：

s.t.DT≤D

顯然，BDMST問題就是要從集合中找到滿足直徑限制且權(quán)值最小的生成樹。

3求解BDMST問題算法

直徑限制最小生成樹問題是派生出來一個(gè)組合優(yōu)化問題，相比求解度約束最小生成樹問題 (Degree Constrained Minimum Spanning Tree Problem，DCMST)的算法，求解BDMST問題算法要少的多，當(dāng)直徑限制D=2、D=3時(shí)，是簡(jiǎn)單問題，通過逐點(diǎn)的多項(xiàng)式的時(shí)間里就可以得到最優(yōu)解。當(dāng)直徑限制D≥n-1時(shí)，這個(gè)限制沒有實(shí)際約束力，因?yàn)閚個(gè)結(jié)點(diǎn)的樹，直徑不會(huì)大于n-1，所以就是標(biāo)準(zhǔn)的最小生成樹問題。而當(dāng)直徑限制D∈[4,N-1)時(shí)，BDMST問題是一個(gè)NP難問題[4]。求解BDMST問題的算法可以歸為三大類：精確算法，快速算法以及現(xiàn)代優(yōu)化算法。

3.1求解BDMST問題的精確算法

對(duì)于求解BDMST問題的精確算法，有依據(jù)線性整數(shù)規(guī)劃[5,6]求解直徑限制最小生成樹問題的方法，以及Gruber和Raidl提出來了一種基于0-1整數(shù)規(guī)劃的分支定界算法[7]，對(duì)于這些精確算法，常常適應(yīng)于求解小規(guī)模的問題，而對(duì)于一些規(guī)模較大的問題則會(huì)失效。

3.2求解BDMST問題的啟發(fā)式算法

啟發(fā)式算法是一種適合較大規(guī)模問題的快速算法，應(yīng)用非常廣泛。求解BDMST問題比較常見的啟發(fā)式算法有：2000年Deo和Abdalla[8]提出的一次性構(gòu)造生成樹算法(簡(jiǎn)稱OTTC算法)，此算法和Prim算法很相似，在每次迭代過程中，選擇那些未連接的距離最近的點(diǎn)，在不違背直徑的基礎(chǔ)上將其連接到樹中；而在對(duì)OTTC算法改進(jìn)的基礎(chǔ)上，2003年由Raidl和Julstromy[9]提出了一個(gè)隨機(jī)貪心算法(Random Greedy Heuristic Algorithm，簡(jiǎn)稱RGH算法)，此方法從隨機(jī)選擇一點(diǎn)作為中心點(diǎn)開始，然后從剩余的頂點(diǎn)中隨機(jī)地選擇，并通過權(quán)值小的邊連接進(jìn)入，這樣就從中心拓展了生成樹；2004年，Julstromy[10]又對(duì)RGH算法進(jìn)行了改進(jìn)，提出了以中心為基礎(chǔ)的樹的結(jié)構(gòu)算法(Centre-based tree construction,簡(jiǎn)稱CBTC)，它也使用了中心的概念，不過在每次迭代過程中，它選擇那些未連入的且距離最近的點(diǎn)，這些被選取的點(diǎn)保證在部分結(jié)構(gòu)樹中的直徑限制。上述幾種啟發(fā)式算法，在文獻(xiàn)[10]中對(duì)它們進(jìn)行了驗(yàn)證，結(jié)果顯示：在歐式空間，RGH要比OTTC、CBTC得到的結(jié)果好一些，而在歐式空間以外的空間，結(jié)果則剛好相反。

3.3求解BDMST問題的現(xiàn)代優(yōu)化算法

現(xiàn)代優(yōu)化算法，與啟發(fā)式算法類似，可以求出其近似解，并接近于其準(zhǔn)確解， 在現(xiàn)代優(yōu)化算法中，比較經(jīng)典的當(dāng)屬遺傳算法，對(duì)于求解BDMST問題的遺傳算法而言，比較典型的有：2003年由Raidl和Julstromy提出的基于邊集編碼的遺傳算法[11](Edge-coded Genetic Evolutionary Algorithm,簡(jiǎn)稱JR-ESEA)和基于序列編碼的遺傳算法[12](Permutation-coded Evolutionary Algorithm，簡(jiǎn)稱JR-PEA)，一般來說，JR-PEA得到的結(jié)果要比JR-ESEA得到的結(jié)果好，不過它耗時(shí)相對(duì)有點(diǎn)長(zhǎng)。此外還有利用隨機(jī)鍵去表示[13]的遺傳算法，此算法與JR-PEA有許多的相似之處。在文獻(xiàn)[14]中Gruber提出了四種鄰近搜索，2006年Raidl和Julstromy將這些鄰近搜索應(yīng)用于螞蟻算法(Ant Colony Optimization,簡(jiǎn)稱ACO)[14,15]。2008年Binh,Nguyen以及McKay[15]提出了一種新的混合遺傳算法(New Hybrid Genetic Algorithm,簡(jiǎn)稱HGA)，其主要的思想是：多個(gè)種群進(jìn)行交配，對(duì)每個(gè)種群利用經(jīng)典的啟發(fā)式算法進(jìn)行初始化，并利用邊集進(jìn)行編碼。

對(duì)于求解BDMST問題除了上述算法還有許多算法，比如基于中心的聚類算法(Center-Based Recursive Clustering,簡(jiǎn)稱CBRC)[16]以及對(duì)RGH、OTTC的改進(jìn)算法[17]等。

4總結(jié)和展望

直徑限制最小生成樹問題是NP-Hard問題，尋找有效的算法是研究的核心問題。對(duì)于大規(guī)模問題，目前已有的方法，大多是采用啟發(fā)式算法或遺傳算法等現(xiàn)代優(yōu)化方法求解，且基本是以完全連通圖為前提，但在實(shí)際應(yīng)用中還是以非完全圖居多，研究非完全圖下BDMST問題的算法更有實(shí)用價(jià)值。

參考文獻(xiàn)〔〕

[1]Gary.Chartrand,Ping Zhang(著).范益政,汪毅,龔世才等(譯).圖論導(dǎo)引[M].北京:人民郵電出版社,2007.81-86.

[2]石磊,馮祖針,楊建強(qiáng).度、直徑約束最小生成樹問題及其算法[J].云南民族大學(xué)學(xué)報(bào)(自然科學(xué)版),2012,21(4):295-297.

[3]Binh.H.T.T,McKay.R.I,Nghia.N.D ,etc.New Heuristic and Hybrid Genetic Algorithm for Solving the Bounded Diameter Minimum Spanning Tree Problem,in Proceedings of Annual Conference on Genetic and Evolutionary Computation [J].Montréal,2009,25(5):373 -380.

[4]Garey M.R,Johnson D.S.Computers and Intractability: a Guide to the Theory of NP-Completeness[J].SIAM Review,1982,24(1): 90-91.

[5]Achuthan.N.R,Caccetta L,Caccetta P,etc.Computational Methods for the Diamter Restricted Minimum Weight Spanning Tree Problem[J].Australian Journal of Combinatorics,1994,10(2):379-384.

[6]Gouveia.L,Magnanti T.L,Requejo C.A2-Path Approach for Odd Diameter Constrained Minimum Spanning and Steiner Trees[J].Networks,2004,44(4):254-265.

[7]Gruber.M ,Raidl G.R.A new 0-1 ILP Approach for the Bounded Diameter Minimum Spanning Tree Problem,in Proceedings of the Second International Network Optimization Conference [J].Vienna,2005,15(3):1-8.

[8]Deo.N,abdalla.A.Computing a Diameter-constrained Minimum Spanning Tree in Parallel[J].Lecture Notes in Computer Science,2000,15(4):17-31.

[9]Julstrom B A.Greedy Heuristic for the Diameter-Constrained Minimum Spanning Tree Problem[J].Journal of Mathemation Sciences,2009,161(6): 930-943.

[10]Alok Singh·Ashok K.Gupta.Improved Heuristics for the Bounded-diameter Minimum Spanning Tree Problem[J].Soft Computer,2007,11(10): 911-921.

[11]Raidl G.R,Julstrom B.A.Greedy Heuristics and an Evolutionary Algorithm for the Bounded-Diameter Minimum Spanning Tree Problem[J].Proceeding of the 2003 ACM Symposium on Applied Computing,2003,102(5):747-752.

[12]Julstrom.B.A,Raidl G.R.A Permutation Coded Evolutionary Algorithm for the Bounded Diameter Minimum Spanning Tree Problem[J].Proceedsing of the Genetic and Evolutionary Computation Conference,2003:2-7.

[13]Julstrom B.A.Encoding Bounded-diameter Spanning Trees with Permutations and with Random Keys[J].Lecture Notes in Computer Science,2004:3102,1272-1281.

[14]Martin Gruber,Jano van Hemert,Güntheer r.Raidl.Neighbourhood Searches for the Bounded Diameter Minimum Spanning Tree Problem Embedded in a VNS,EA and ACO.USA Copyright[J].Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation,2006:1187-1194.

[15]石磊,馮祖針,楊建強(qiáng).蟻群算法求解直徑約束最小生成樹問題[J].紅河學(xué)院學(xué)報(bào),2012,10(4):16-18.

[16]Huynh Thi Thanh Binh,Nguyen Xuan Hoai,R.I.McKay.A New Hybrid Genetic Algorithm for Solving the Bounded Diameter Minimum Spanning Tree Problem[J].Proceedings of IEEE World Congress on Evolutionary Compution,2008,24(5):3128-3134.

[17]玄光男,程潤(rùn)偉(著).于歆杰,周根貴(譯).遺傳算法與工程優(yōu)化[M].北京:清華大學(xué)出版社.2003.1-10.

[18]熊小華,寧愛兵,馬良.基于降階的最小生成樹快速算法[J].計(jì)算機(jī)應(yīng)用研究,2010,27(6):2051-2053.

Overview of Bounded-diameter Minimum Spanning Tree Problem

JIANG Na

(Faculty of Mathematical Sciences,Inner Mongolia University; Hohhot 010021 )

Abstract:Bounded-diameter minimum spanning tree problem is a classic combinatorial optimization problem.This paper reviewed the bounded diameter minimum spanning tree problem,at the same time,it introduced the research background mathematical models and concepts and summarized this problem solving algorithm.

Key words:Bounded-diameter;Minimum spanning tree ;Non-complete graph；BDMST