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

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

姜娜

(內蒙古大學 數學科學學院，內蒙古 呼和浩特 010021)

摘要：直徑限制最小生成樹問題是一個經典的網絡優化問題。本文對直徑限制最小生成樹問題進行了綜述，介紹了該問題的研究背景、數學模型以及相關的概念，并對問題的求解方法進行了歸納總結。

關鍵詞：直徑限制；最小生成樹；非完全圖；BDMST

收稿日期：*2015-04-27

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

中圖分類號：O221.7文獻標識碼：A

0引言

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

直徑限制最小生成樹問題在資源優化問題中應用廣泛，比如網絡設計中的網絡直徑選擇，將直接影響著網絡的傳輸速度、網絡能耗以及信號傳遞的快慢等，在路由優化中，直徑的限制，也便于設備部署的設計和維護。因此，直徑限制最小生成樹問題的研究，有著重要的理論和應用價值。

1BDMST問題相關概念介紹

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

定義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結點與邊交替出現的序列v0e1v1e2，…，v1，稱為結點v0到v1的鏈。其中，結點vi-1和vi是邊ei的兩個端點(i=1,2,…,l)。稱結點v0為鏈的始點，結點v1為鏈的終點。鏈中邊的條數稱為鏈長度。

若鏈中邊各異，則稱為跡；若鏈中結點各異，則稱為路。若v0=vl稱為閉的，否則稱為開的。閉的路徑稱為圈。

定義1.5如果圖G中每一對結點之間都有一條路連接，則稱圖G是連通圖，否則，稱G是非連通圖。

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

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

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

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

2BDMST問題的數學模型

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

s.t.DT≤D

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

3求解BDMST問題算法

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

3.1求解BDMST問題的精確算法

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

3.2求解BDMST問題的啟發式算法

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

3.3求解BDMST問題的現代優化算法

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

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

4總結和展望

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

參考文獻〔〕

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

[2]石磊,馮祖針,楊建強.度、直徑約束最小生成樹問題及其算法[J].云南民族大學學報(自然科學版),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]石磊,馮祖針,楊建強.蟻群算法求解直徑約束最小生成樹問題[J].紅河學院學報,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]玄光男,程潤偉(著).于歆杰,周根貴(譯).遺傳算法與工程優化[M].北京:清華大學出版社.2003.1-10.

[18]熊小華,寧愛兵,馬良.基于降階的最小生成樹快速算法[J].計算機應用研究,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