度约束最小生成树问题概述*

郭 仁 杰

（内蒙古大学数学科学学院，内蒙古呼和浩特 010021）

度约束最小生成树问题概述*

郭 仁 杰＊＊

（内蒙古大学数学科学学院，内蒙古呼和浩特 010021）

度约束最小生成树问题是经典的组合优化难题。本文对度约束最小生成树问题进行了综述，介绍了研究背景、数学模型及相关概念，并对该问题的求解算法进行了分类总结。

最小生成树;约束;遗传算法

1 引言

树是图论的重要概念之一，也是图论中结构简单、用途广泛的一种连通图。如通信网络设计、最短路连接及排水系统设计等，通常都可以转化为求最小生成树（Minimum Spanning Tree，简称MST）问题，MST问题是组合优化中的一个常见问题，该问题历史悠久，最早是由Bor¨uvka于1926年提出的。在理论上生成树的结构可以不受任何约束条件的限制，但在实际应用中，生成树的某些节点的度数往往会受到一些因素的影响，使这些节点的度数不能随意取值，比如通信网络中为了防止节点故障带来的脆弱性，对节点的度要有一定的限制。为了解决这些类似问题，便引出了度约束最小生成树［1］（Degree Constrained Minimum Spanning Tree ，简称 DCMST）问题，即对最小生成树中每个节点都给定一个最大的度约束，使得所有节点都满足这个度约束。

DCMST问题是由Narula和HO于上世纪八十年代初提出的［1］。该问题是许多实际优化问题的基础，在信息网络的设计与优化中也有重要的应用背景。而且在现实生活中，DCMST问题与人们的生产生活密切相关，找到解决DCMST问题的有效算法可以节省资源，提高生产效率，对人们的生产生活产生重大影响。同时研究度约束最小生成树问题也有着重要的理论意义和应用价值。

2 DCMST的基本概念

图可以简洁形象直观地描述各种复杂的数据对象，目前图的应用已渗透到语言学、逻辑学、遗传学、通信等诸多领域。树是一类极其重要的数据结构，它能反映出数据之间的层次关系和分支关系。树在计算机科学、电子线路设计、组合优化等领域得到了广泛的应用。

定义2.1:一个图是二元组（V，E），其中V是一个非空的节点集合，E是边的集合。

定义2.2:如果图G中每一对结点都属于某一条路径，则称图G是连通图;否则，称图G是非连通图。

定义2.3:设图G是无向连通，图H是一棵树，图H满足V（H）=V（G），E（H）⊆E（G），且H中边的端点的分配和G中的一样，则称图H为图G的生成树或者支撑树。

定义2.4:如果节点v是边e的端点，则称v和e是关联的。节点v的度是其关联边的条数，记作bv。图G的度是指其所有结点的度的最大值，记为bG。孤立结点的度数为零。

定义2.5:设图G是连通图，并且对它的每条边都分配一个数值，该数值称为边的成本（cost）或权值（weight）。图G的边e的权值记为w（e），把这样的图称为赋权图或网络。

定义2.7:称对图G中每个节点的度值大小的限制为度约束，设树T为图G=（V，E，W）的生成树，如果树T的任意节点都满足度约束，则称T为图G满足度约束的生成树，称所有满足度约束的生成树中具有最小权的树为图G的度约束最小生成树。

显然当图G所有节点的度约束都大于等于|V|－1时，度约束的生成树问题等价于无度约束的生成树问题;而当图G所有节点的度约束都等于2时，度约束的生成树问题等价于旅行商问题。

定义2.8:任意两点之间都有一条直接边相连的图叫做完全图。

3 DCMST的数学模型

设图G=（V，E，W）是连通赋权无向图，其中V={v1，v2...vn}表示顶点集合，E= {e1，e2...em}表示边集合，W=（wij）n×n表示权矩阵，规定 wij=wji，wii= ∞ ，i，j=1，2，…，n;若 （vi，vj）∈ E（G），则 wij=W（vi，vj）;若 （vi，vj）∉E（G），则 wij= ∞ 。设 xij（i，j=1，2…m）是0 －1型决策变量，若xij=1，表示边（vi，vj）被选中;若xij=0，表示边（vi，vj）未被选中。设各顶点的度约束为 bi（i=1，2，…，n），则 DCMST问题的数学模型［2］为:

模型中的条件（3.2）保证在最后的子图中共有n－1条边;条件（3.3）保证在求解最小生成树的过程中不成圈，即这两个约束条件保证最后得到的子图为图G的一个生成树;条件（3.4）限制与第i个节点相连接的边的条数，即保证度约束这个限制条件。

4 DCMST问题的算法概述

近年来DCMST在计算机网络、通信网络、运输网络设计等领域得到了广泛的应用，并陆续提出了若干求解方法。DCMST问题属于NP难问题，所以若得到问题的精确解很困难。一般地，度约束最小生成树问题的求解方法分为两类［3］:一类可以把问题转化为0－1整数规划模型，利用0－1整数规划模型的求解方法来求解，此法很少被采用;另一类为构造型的求解方法，构造型的求解方法又可以分为古典型构造求解方法和智能型的构造求解方法。

4.1 求解DCMST的古典型构造求解方法

例如Boruvka设计的贪婪启发式算法和分支限界算法，Savelsbeg和Vofgenani提出的基于拉格朗日松弛的分支限界算法都属于古典构造求解方法。

对于古典型构造方法很多研究者根据贪心思想设计出了求解DCMST的快速算法。如1998年马良等提出了求解DCMST的快速算法;2006年宋海洲提出了求解DCMST问题的启发式近似算法;2008年焦森林也提出了一种快速近似算法求解DCMST算法;2009年王立东基于启发式思想提出了求解DCMST的新的快速算法。1989年顾立尧提出了带有度约束的最小耗费生成树的分支限界算法［4］，该算法是一类精确算法。2005年宁爱兵等提出了关于DCMST的竞争决策算法［5］。该算法模拟了竞争决策算法的通用模型。2011年熊小华等提出了度约束最小生成树的元胞竞争决策算法［6］，该算法提高了度约束最小生成树问题的求解精度。

4.2 求解DCMST的智能型构造求解方法

古典型的构造方法一般时间复杂度较高，因此很少被采用，而智能型的构造方法近些年被广泛地采用。智能型的构造方法主要通过智能优化算法来实现，如遗传算法、蚁群算法等。遗传算法作为一种启发式搜索优化算法，它为求解DCMST问题提供了一个有效的途径。本文主要介绍了应用遗传算法求解DCMST问题的算法，应用遗传算法对树的编码方式一般有四种形式［23］:边编码、点编码、边和点编码和边集合编码。

4.2.1 基于遗传算法求解DCMST问题

日本学者zhou和Gen首次提出利用遗传算法求解度约束最小生成树问题［7］，并且运用Pr¨ufer编码方式对生成树编码，对度约束最小生成树问题的研究做出了重大的突破和推进。

2003年王励成、孙麟平提出求解DCMST问题的启发式遗传搜索算法［8］。该算法带有边权矩阵及度限制向量的遗传信息。采用关于节点的编码方式，设计了翻转变异算子，通过添加虚拟节点将带有度的约束问题转化为无约束问题。

2005年韩丽霞提出解两类组合优化问题的遗传算法［44］。其中提到了求解DCMST问题的新的遗传算法。该算法采用边的信息进行编码，运用改进的Dijkstra算法生成初始种群。设计了两种进化算子，提高了算法的搜索能力。

2007年牧云志提出基于遗传算法的网络拓扑结构的优化研究［10］。该算法将无度约束的最小树问题的解作为DCMST问题的下界，并运用利Prim算法得到这个下界，同时采用改进的Prim算法获得DCMST问题的上界。该论文设计了两种遗传算法基于Pr¨ufer数的遗传算法和基于度的排列的遗传算法。

2008年尉春杰提出度约束最小生成树WCJ遗传算法［3］。该算法采用了Prüfer编码策略，设计了一种特殊的初始种群生成方法，避免了产生不可行解，并设计了打乱式变异算子，补充变异算子和两点逆转变异算子。

2010年帅训波等提出基于分段编码遗传算法求解DCMST问题的算法［11］。分段编码是指将染色体分成两段，每段元素分别为各序偶的第一元素集合和第二元素集合。这样的编码方式缺陷在于遗传操作过程中会生成很多不可行解，例如形成回路，超出度约束限制等非法解。

2010年朱晓虹提出基于量子遗传算法求解DCMST问题算法［12］。该算法采用量子比特编码表示染色体，利用量子门更新策略来完成遗传搜索，具有种群规模小而不影响算法性能，同时具有全局寻优能力强，收敛速度快的特点。

2010年王竹荣等提出了一种求解DCMST问题的优化算法［13］。此算法是以基本遗传算子为基础，带有加速和调节算子作为激励的遗传算法。以节点度的排列为编码方法，通过利用度维关系和待考察节点的关联节点以及构成边的权重信息，设计出从正反两方面出发的加速搜索过程。

4.2.2 其他智能型构造求解方法

其他的方法如蚁群算法、粒子流算法等，均从不同方面对DCMST的研究取得了一定成效。马良等提出了求解度限制最小树的蚁群算法［14］。该算法适用于度限制苛刻且网络呈稀疏状态的度约束最小生成树问题。

5 总结和展望

度约束最小生成树问题属于NP难问题，问题求解的难度与节点的度约束以及图的连接状态有关。由于DCMST是许多实际优化问题的基础，所以研究DCMST有着重要的理论意义和应用价值。目前提高计算效率仍然是求解度约束最小生成树问题的关键，因此，设计精确且高效的算法仍是一个值得研究的方向。多数算法都是在完全图下求解的DCMST问题，但实际运用中很多图的模型并不是完全图，在今后的工作中可对非完全图的DCMST问题进行研究。

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

［2］王立东.约束最小生成树算法的研究［D］.西安电子科技大学，2009.

［3］尉春杰.度约束最小生成树WCJ遗传算法［D］.东北大学，2008.

［4］顾立尧.带有度约束的最小耗费生成树的分支限界算法［J］.计算机应用与软件，1989，6:49 －54.

［5］宁爱兵，马良.度约束最小生成树（DCMST）的竞争决策算法［J］.系统工程学报，2005，20（6）:631 －634.

［6］熊小华，宁爱兵.度约束最小生成树的元胞竞争决策算法［J］.上海第二工业大学学报，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］王励成，孙麟平.求解度限制最小生成树问题的启发式遗传搜索算法［J］.系统工理论与实践，2003，103 －112.

［9］韩丽霞.解两类组合优化问题的遗传算法［D］.西安电子科技大学，2005.

［10］牡云志.基于遗传算法的网络拓扑结构的优化研究［D］.浙江工业大学，2007.

［11］帅训波，马书南.一种基于遗传算法的度约束最小生成树求解方法［J］.曲阜师范大学学报，2010，55 －58.

［12］朱晓虹.量子遗传算法求解度约束最小生成树［J］.巢湖学院学报，2010，38 －42.

［13］王竹荣，张九龙，崔杜武.一种求解度约束最小生成树问题的优化算法［J］.软件学报，2010，68 －82.

［14］马良，蒋馥.度限制最小树的蚂蚁算法［J］.系统工程学报，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－），女，内蒙古赤峰人，2011级硕士研究生，研究方向:算法分析与设计。