郭 仁 杰

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

度約束最小生成樹(shù)問(wèn)題概述*

郭 仁 杰＊＊

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

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

最小生成樹(shù);約束;遺傳算法

1 引言

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

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

2 DCMST的基本概念

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

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

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

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

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

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

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

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

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

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

設(shè)圖G=（V，E，W）是連通賦權(quán)無(wú)向圖，其中V={v1，v2...vn}表示頂點(diǎn)集合，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è)各頂點(diǎn)的度約束為 bi（i=1，2，…，n），則 DCMST問(wèn)題的數(shù)學(xué)模型［2］為:

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

4 DCMST問(wèn)題的算法概述

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

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

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

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

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

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

4.2.1 基于遺傳算法求解DCMST問(wèn)題

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

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

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

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

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

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

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

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

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

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

5 總結(jié)和展望

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

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

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

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

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

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

［6］熊小華，寧愛(ài)兵.度約束最小生成樹(shù)的元胞競(jìng)爭(zhēng)決策算法［J］.上海第二工業(yè)大學(xué)學(xué)報(bào)，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］王勵(lì)成，孫麟平.求解度限制最小生成樹(shù)問(wèn)題的啟發(fā)式遺傳搜索算法［J］.系統(tǒng)工理論與實(shí)踐，2003，103 －112.

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

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

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

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

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

［14］馬良，蔣馥.度限制最小樹(shù)的螞蟻算法［J］.系統(tǒng)工程學(xué)報(bào)，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級(jí)碩士研究生，研究方向:算法分析與設(shè)計(jì)。