郭 仁 杰

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

度約束最小生成樹問題概述*

郭 仁 杰＊＊

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

度約束最小生成樹問題是經(jīng)典的組合優(yōu)化難題。本文對度約束最小生成樹問題進行了綜述，介紹了研究背景、數(shù)學(xué)模型及相關(guān)概念，并對該問題的求解算法進行了分類總結(jié)。

最小生成樹;約束;遺傳算法

1 引言

樹是圖論的重要概念之一，也是圖論中結(jié)構(gòu)簡單、用途廣泛的一種連通圖。如通信網(wǎng)絡(luò)設(shè)計、最短路連接及排水系統(tǒng)設(shè)計等，通常都可以轉(zhuǎn)化為求最小生成樹（Minimum Spanning Tree，簡稱MST）問題，MST問題是組合優(yōu)化中的一個常見問題，該問題歷史悠久，最早是由Bor¨uvka于1926年提出的。在理論上生成樹的結(jié)構(gòu)可以不受任何約束條件的限制，但在實際應(yīng)用中，生成樹的某些節(jié)點的度數(shù)往往會受到一些因素的影響，使這些節(jié)點的度數(shù)不能隨意取值，比如通信網(wǎng)絡(luò)中為了防止節(jié)點故障帶來的脆弱性，對節(jié)點的度要有一定的限制。為了解決這些類似問題，便引出了度約束最小生成樹［1］（Degree Constrained Minimum Spanning Tree ，簡稱 DCMST）問題，即對最小生成樹中每個節(jié)點都給定一個最大的度約束，使得所有節(jié)點都滿足這個度約束。

DCMST問題是由Narula和HO于上世紀(jì)八十年代初提出的［1］。該問題是許多實際優(yōu)化問題的基礎(chǔ)，在信息網(wǎng)絡(luò)的設(shè)計與優(yōu)化中也有重要的應(yīng)用背景。而且在現(xiàn)實生活中，DCMST問題與人們的生產(chǎn)生活密切相關(guān)，找到解決DCMST問題的有效算法可以節(jié)省資源，提高生產(chǎn)效率，對人們的生產(chǎn)生活產(chǎn)生重大影響。同時研究度約束最小生成樹問題也有著重要的理論意義和應(yīng)用價值。

2 DCMST的基本概念

圖可以簡潔形象直觀地描述各種復(fù)雜的數(shù)據(jù)對象，目前圖的應(yīng)用已滲透到語言學(xué)、邏輯學(xué)、遺傳學(xué)、通信等諸多領(lǐng)域。樹是一類極其重要的數(shù)據(jù)結(jié)構(gòu)，它能反映出數(shù)據(jù)之間的層次關(guān)系和分支關(guān)系。樹在計算機科學(xué)、電子線路設(shè)計、組合優(yōu)化等領(lǐng)域得到了廣泛的應(yīng)用。

定義2.1:一個圖是二元組（V，E），其中V是一個非空的節(jié)點集合，E是邊的集合。

定義2.2:如果圖G中每一對結(jié)點都屬于某一條路徑，則稱圖G是連通圖;否則，稱圖G是非連通圖。

定義2.3:設(shè)圖G是無向連通，圖H是一棵樹，圖H滿足V（H）=V（G），E（H）?E（G），且H中邊的端點的分配和G中的一樣，則稱圖H為圖G的生成樹或者支撐樹。

定義2.4:如果節(jié)點v是邊e的端點，則稱v和e是關(guān)聯(lián)的。節(jié)點v的度是其關(guān)聯(lián)邊的條數(shù)，記作bv。圖G的度是指其所有結(jié)點的度的最大值，記為bG。孤立結(jié)點的度數(shù)為零。

定義2.5:設(shè)圖G是連通圖，并且對它的每條邊都分配一個數(shù)值，該數(shù)值稱為邊的成本（cost）或權(quán)值（weight）。圖G的邊e的權(quán)值記為w（e），把這樣的圖稱為賦權(quán)圖或網(wǎng)絡(luò)。

定義2.7:稱對圖G中每個節(jié)點的度值大小的限制為度約束，設(shè)樹T為圖G=（V，E，W）的生成樹，如果樹T的任意節(jié)點都滿足度約束，則稱T為圖G滿足度約束的生成樹，稱所有滿足度約束的生成樹中具有最小權(quán)的樹為圖G的度約束最小生成樹。

顯然當(dāng)圖G所有節(jié)點的度約束都大于等于|V|－1時，度約束的生成樹問題等價于無度約束的生成樹問題;而當(dāng)圖G所有節(jié)點的度約束都等于2時，度約束的生成樹問題等價于旅行商問題。

定義2.8:任意兩點之間都有一條直接邊相連的圖叫做完全圖。

3 DCMST的數(shù)學(xué)模型

設(shè)圖G=（V，E，W）是連通賦權(quán)無向圖，其中V={v1，v2...vn}表示頂點集合，E= {e1，e2...em}表示邊集合，W=（wij）n×n表示權(quán)矩陣，規(guī)定 wij=wji，wii= ∞ ，i，j=1，2，…，n;若 （vi，vj）∈ E（G），則 wij=W（vi，vj）;若 （vi，vj）?E（G），則 wij= ∞ 。設(shè) xij（i，j=1，2…m）是0 －1型決策變量，若xij=1，表示邊（vi，vj）被選中;若xij=0，表示邊（vi，vj）未被選中。設(shè)各頂點的度約束為 bi（i=1，2，…，n），則 DCMST問題的數(shù)學(xué)模型［2］為:

模型中的條件（3.2）保證在最后的子圖中共有n－1條邊;條件（3.3）保證在求解最小生成樹的過程中不成圈，即這兩個約束條件保證最后得到的子圖為圖G的一個生成樹;條件（3.4）限制與第i個節(jié)點相連接的邊的條數(shù)，即保證度約束這個限制條件。

4 DCMST問題的算法概述

近年來DCMST在計算機網(wǎng)絡(luò)、通信網(wǎng)絡(luò)、運輸網(wǎng)絡(luò)設(shè)計等領(lǐng)域得到了廣泛的應(yīng)用，并陸續(xù)提出了若干求解方法。DCMST問題屬于NP難問題，所以若得到問題的精確解很困難。一般地，度約束最小生成樹問題的求解方法分為兩類［3］:一類可以把問題轉(zhuǎn)化為0－1整數(shù)規(guī)劃模型，利用0－1整數(shù)規(guī)劃模型的求解方法來求解，此法很少被采用;另一類為構(gòu)造型的求解方法，構(gòu)造型的求解方法又可以分為古典型構(gòu)造求解方法和智能型的構(gòu)造求解方法。

4.1 求解DCMST的古典型構(gòu)造求解方法

例如Boruvka設(shè)計的貪婪啟發(fā)式算法和分支限界算法，Savelsbeg和Vofgenani提出的基于拉格朗日松弛的分支限界算法都屬于古典構(gòu)造求解方法。

對于古典型構(gòu)造方法很多研究者根據(jù)貪心思想設(shè)計出了求解DCMST的快速算法。如1998年馬良等提出了求解DCMST的快速算法;2006年宋海洲提出了求解DCMST問題的啟發(fā)式近似算法;2008年焦森林也提出了一種快速近似算法求解DCMST算法;2009年王立東基于啟發(fā)式思想提出了求解DCMST的新的快速算法。1989年顧立堯提出了帶有度約束的最小耗費生成樹的分支限界算法［4］，該算法是一類精確算法。2005年寧愛兵等提出了關(guān)于DCMST的競爭決策算法［5］。該算法模擬了競爭決策算法的通用模型。2011年熊小華等提出了度約束最小生成樹的元胞競爭決策算法［6］，該算法提高了度約束最小生成樹問題的求解精度。

4.2 求解DCMST的智能型構(gòu)造求解方法

古典型的構(gòu)造方法一般時間復(fù)雜度較高，因此很少被采用，而智能型的構(gòu)造方法近些年被廣泛地采用。智能型的構(gòu)造方法主要通過智能優(yōu)化算法來實現(xiàn)，如遺傳算法、蟻群算法等。遺傳算法作為一種啟發(fā)式搜索優(yōu)化算法，它為求解DCMST問題提供了一個有效的途徑。本文主要介紹了應(yīng)用遺傳算法求解DCMST問題的算法，應(yīng)用遺傳算法對樹的編碼方式一般有四種形式［23］:邊編碼、點編碼、邊和點編碼和邊集合編碼。

4.2.1 基于遺傳算法求解DCMST問題

日本學(xué)者zhou和Gen首次提出利用遺傳算法求解度約束最小生成樹問題［7］，并且運用Pr¨ufer編碼方式對生成樹編碼，對度約束最小生成樹問題的研究做出了重大的突破和推進。

2003年王勵成、孫麟平提出求解DCMST問題的啟發(fā)式遺傳搜索算法［8］。該算法帶有邊權(quán)矩陣及度限制向量的遺傳信息。采用關(guān)于節(jié)點的編碼方式，設(shè)計了翻轉(zhuǎn)變異算子，通過添加虛擬節(jié)點將帶有度的約束問題轉(zhuǎn)化為無約束問題。

2005年韓麗霞提出解兩類組合優(yōu)化問題的遺傳算法［44］。其中提到了求解DCMST問題的新的遺傳算法。該算法采用邊的信息進行編碼，運用改進的Dijkstra算法生成初始種群。設(shè)計了兩種進化算子，提高了算法的搜索能力。

2007年牧云志提出基于遺傳算法的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的優(yōu)化研究［10］。該算法將無度約束的最小樹問題的解作為DCMST問題的下界，并運用利Prim算法得到這個下界，同時采用改進的Prim算法獲得DCMST問題的上界。該論文設(shè)計了兩種遺傳算法基于Pr¨ufer數(shù)的遺傳算法和基于度的排列的遺傳算法。

2008年尉春杰提出度約束最小生成樹WCJ遺傳算法［3］。該算法采用了Prüfer編碼策略，設(shè)計了一種特殊的初始種群生成方法，避免了產(chǎn)生不可行解，并設(shè)計了打亂式變異算子，補充變異算子和兩點逆轉(zhuǎn)變異算子。

2010年帥訓(xùn)波等提出基于分段編碼遺傳算法求解DCMST問題的算法［11］。分段編碼是指將染色體分成兩段，每段元素分別為各序偶的第一元素集合和第二元素集合。這樣的編碼方式缺陷在于遺傳操作過程中會生成很多不可行解，例如形成回路，超出度約束限制等非法解。

2010年朱曉虹提出基于量子遺傳算法求解DCMST問題算法［12］。該算法采用量子比特編碼表示染色體，利用量子門更新策略來完成遺傳搜索，具有種群規(guī)模小而不影響算法性能，同時具有全局尋優(yōu)能力強，收斂速度快的特點。

2010年王竹榮等提出了一種求解DCMST問題的優(yōu)化算法［13］。此算法是以基本遺傳算子為基礎(chǔ)，帶有加速和調(diào)節(jié)算子作為激勵的遺傳算法。以節(jié)點度的排列為編碼方法，通過利用度維關(guān)系和待考察節(jié)點的關(guān)聯(lián)節(jié)點以及構(gòu)成邊的權(quán)重信息，設(shè)計出從正反兩方面出發(fā)的加速搜索過程。

4.2.2 其他智能型構(gòu)造求解方法

其他的方法如蟻群算法、粒子流算法等，均從不同方面對DCMST的研究取得了一定成效。馬良等提出了求解度限制最小樹的蟻群算法［14］。該算法適用于度限制苛刻且網(wǎng)絡(luò)呈稀疏狀態(tài)的度約束最小生成樹問題。

5 總結(jié)和展望

度約束最小生成樹問題屬于NP難問題，問題求解的難度與節(jié)點的度約束以及圖的連接狀態(tài)有關(guān)。由于DCMST是許多實際優(yōu)化問題的基礎(chǔ)，所以研究DCMST有著重要的理論意義和應(yīng)用價值。目前提高計算效率仍然是求解度約束最小生成樹問題的關(guān)鍵，因此，設(shè)計精確且高效的算法仍是一個值得研究的方向。多數(shù)算法都是在完全圖下求解的DCMST問題，但實際運用中很多圖的模型并不是完全圖，在今后的工作中可對非完全圖的DCMST問題進行研究。

［1］Narula SC，Ho CA.Degree constrained minimum spanning tree［J］.Computer andOperations Research，1980，7（4）:239－249.

［2］王立東.約束最小生成樹算法的研究［D］.西安電子科技大學(xué)，2009.

［3］尉春杰.度約束最小生成樹WCJ遺傳算法［D］.東北大學(xué)，2008.

［4］顧立堯.帶有度約束的最小耗費生成樹的分支限界算法［J］.計算機應(yīng)用與軟件，1989，6:49 －54.

［5］寧愛兵，馬良.度約束最小生成樹（DCMST）的競爭決策算法［J］.系統(tǒng)工程學(xué)報，2005，20（6）:631 －634.

［6］熊小華，寧愛兵.度約束最小生成樹的元胞競爭決策算法［J］.上海第二工業(yè)大學(xué)學(xué)報，2011，207 －213.

［7］Zhou G，Gen M.Approach to degree－ constrained minimum spanning tree problem using genetic algorithm［J］.Eng Des＆ Automat，1997，3（2）:157 －165.

［8］王勵成，孫麟平.求解度限制最小生成樹問題的啟發(fā)式遺傳搜索算法［J］.系統(tǒng)工理論與實踐，2003，103 －112.

［9］韓麗霞.解兩類組合優(yōu)化問題的遺傳算法［D］.西安電子科技大學(xué)，2005.

［10］牡云志.基于遺傳算法的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的優(yōu)化研究［D］.浙江工業(yè)大學(xué)，2007.

［11］帥訓(xùn)波，馬書南.一種基于遺傳算法的度約束最小生成樹求解方法［J］.曲阜師范大學(xué)學(xué)報，2010，55 －58.

［12］朱曉虹.量子遺傳算法求解度約束最小生成樹［J］.巢湖學(xué)院學(xué)報，2010，38 －42.

［13］王竹榮，張九龍，崔杜武.一種求解度約束最小生成樹問題的優(yōu)化算法［J］.軟件學(xué)報，2010，68 －82.

［14］馬良，蔣馥.度限制最小樹的螞蟻算法［J］.系統(tǒng)工程學(xué)報，1999，14（3）:212 －214.

Overview of Degree Constrained Minimum Spanning Tree Problem

GUO Ren－jie
（School of Mathematical Sciences，Inner Mongolia University;Hohhot 010021）

Degree constrained minimum spanning tree problem is a classic combinatorial optimization problem.this paper reviewed the degree constrained minimum spanning tree problem，introduced the research background，mathematical models and concepts，and summarized this problem solving algorithm.

minimum spanning tree;constrained;genetic algorithm

O223

A

1004－1869（2014）02－0008－03

10.13388/j.cnki.ysajs.2014.02.002

2014－04－12

郭仁杰（1988－），女，內(nèi)蒙古赤峰人，2011級碩士研究生，研究方向:算法分析與設(shè)計。