度、直径约束最小生成树问题及其算法

石磊，冯祖针，杨建强

(红河学院数学学院，云南蒙自661100)

度、直径约束最小生成树问题及其算法

石磊，冯祖针，杨建强

(红河学院数学学院，云南蒙自661100)

提出了度、直径约束最小生成树问题，证明了该问题是NP-完全的.建立了该问题的数学规划模型.给出了启发式求解算法，其时间复杂性为O(mn).分析和实例实验表明，该算法有良好的效果.

最小生成树;启发式算法;度约束;直径约束

最小生成树(minimum spanning tree，MST)［1］问题是网络中的一个经典问题，被广泛应用于网络优化问题中.MST问题中2个变形问题度约束最小生成树(degree-constrained minimum spanning tree，DCMST)［2-3］问题和直径约束最小生成树(bounded diameter minimum spanning tree，BDMST)［4-5］问题受到普遍的重视和研究.文献［6］证明了DCMST问题和当直径约束值Δ∈［4，n-1)的BDMST问题为NP -完全问题.

DCMST问题和BDMST问题都有着很强的应用背景，如网络通信、资源优化、预测决策等.在某些领域求最小生成树时，其数学模型中节点同时受到度约束和直径约束，如覆盖多播路由［7］.现有研究并未考虑节点需同时满足度约束和直径约束的最小生成树问题，而此问题有一定的应用价值.因此本文提出度、直径约束最小生成树(degree-constrained，radius-constrained minimum spanning tree，DCBDMST)问题，它是一个NP-完全问题，即不存在多项式求解算法，同时给出了DCBDMST问题的启发式求解算法.

1 问题描述和模型

给定无向网络G=(V，E，D，W)，任意节点vi∈V，且|V|=n;任意边e=(vi，vj)∈E，且|E|=m.对∀vi∈V对应一个度约束值dmax(vi)∈N，称为度约束，D={dmax(vi)|vi∈V}.对∀(vi，vj)∈E对应一个非负权值w(vi，vj)，称为长度或代价，W={w(vi，vj) |(vi，vj)∈E}.

定义1［4］给定树T=(¯V，¯E)，树中2个节点的最大距离(所含边的数目)称为树T的直径，简记diam(T).

定义2度、直径约束最小生成树(DCBDMST)问题可以描述为寻找G的一个最小生成树T，满足当前节点的度dT(vi)≤dmax(vi)(∀vi∈T)和树的直径diam(T)≤Δ，且4≤Δ≤n-1.取dmax(vi)和Δ是正整数.

其数学模型为:

式(1)为目标函数，式(2)为约束条件.下节将对DCBDMST问题的计算复杂性进行讨论.

2 DCBDMST计算复杂性证明

研究组合优化问题复杂性通常的方法是研究其对应的判定问题.因此将对DCBDMST问题对应的判定形式(记为DCBDMST(D)［8］)进行研究.要证明DCBDMST(D)问题为NP-完全问题只需证明［8］:①DCBDMST(D)问题∈NP;②一个NP-完全问题能经多项式变换为DCBDMST(D)问题.

定义3BDMST(D)问题:给定无向网络G= (V，E，D，W)，是否存在一棵生成树T，使得T的总代价W(T)≤α1和直径diam(T)≤Δ1(4≤Δ1≤n-1)，其中α1，Δ1∈Z+.

定义4DCBDMST(D)问题:给定无向网络G= (V，E，D，W)，是否存在一棵生成树T，使得T的总代价W(T)≤α2、直径diam(T)≤Δ2(4≤Δ2≤n-1)和每个节点的当前度dT(vi)≤dmax(vi)，其中α2，Δ2∈Z+.

定理1DCBDMST问题是NP-完全问题.

证明选取一个已被证明为NP-完全的问题是直径约束最小生成树(BDMST)问题，给出DCBDMST问题和BDMST问题的判断形式.

1)先证DCBDMST(D)问题∈NP问题.

a.任意DCBDMST(D)问题的一个实例I，任取实例I中的生成树T'=(S'，E')，则T'的字符串输入长度是多项式时间内可计算的;

则DCBDMST(D)问题∈NP问题.

2)再证BDMST(D)问题可多项式变换到DCBDMST(D)问题.

任取BDMST(D)问题的一个实例Ⅱ，Ⅱ是一个无向网络G=(V，E，D，W)，是否存在一棵生成树T，使得T的总代价W(T)≤α1和直径diam(T)≤Δ1.

构造Ⅱ的一个变换f:

令¯V=V，¯E=E，¯W=W;对∀vi∈¯V，赋予度约束值dmax(vi)=n;取α2=α1，Δ2=Δ1.是否存在一棵的生成树¯T，使得¯T的总代价W(¯T)≤α2、直径diam(¯T)≤Δ2和每个节点的当前度dT(vi)≤dmax(vi).

则实例Ⅱ通过变换f得到了DCBDMST(D)问题的一个实例，记为Ⅱ':¯G=(¯V，¯E，¯D，¯W)，是否存在总代价、直径和每个节点都满足度约束的生成树¯T.

若Ⅱ有解当且仅当对应Ⅱ'有解，即BDMST (D)问题可通过f变换到DCBDMST(D)问题.

变换f中构造都是多项式时间内可完成的，则f为多项式时间变换，即BDMST(D)问题可多项式变换到DCBDMST(D)问题.

综上所述，DCBDMST(D)问题是NP-完全问题，因此DCBDMST问题是NP-完全问题.证毕.

3 启发式算法

Prim算法是MST问题高效的多项式时间内求解算法，本文在Prim算法基础上为DCBDMST(D)提出一个启发式求解算法.它从网络G=(V，E，D，W)任意一个节点出发，每次选择满足约束条件的边e，不断的扩展一棵子树T=(S，E0)，直到S包括原网络的全部节点即

其基本思想是:对V中每个节点vi，赋予3个数值(称为标号):①剩余度标号re_d(vi)，记录该节点此时的剩余度即该节点还可接纳的最大边数;②距离标号u(vi)，设出发的节点为v0，记录在当前生成树T中v0到该节点经过边的总数目，则当前树T的直径diam(T)为最大的2个距离标号之和;③前趋标号pred(vi)，记录从v0到该节点的路长取到u(vi)，该路中节点vi前面的那个直接前趋节点，前趋标号用来查找最终的生成树.从v0出发，每次选择割［S，¯S］中满足约束的权值最小的边，然后修改节点的标号，直到.算法具体步骤如下:

Step 0初始化，任取节点v0∈V，S={v0}，令剩余度标号re_d(v0)=dmax(v0)，距离标号u(v0)=0，pred(v0)=0，¯S=V-S;对¯S中的节点令剩余度标号re_d(vi)=dmax(vi)，距离标号u(vi)=+∞，pred(vi)=0.当前生成树T=(S，E0)，E0=∅;

Step 1若S=V，则根据节点的前趋标号输出生成树T，结束.否则转到Step 2;

Step 2若割［S，¯S］=∅，则G不连通，结束.否则转到Step 3;

Step 3将割［S，¯S］中端点和权值都满足约束的边e加入到集合S'，即S'中任意的边e=(v1，v2) (v1∈S，v2∈¯S)，都有re_d(v1)＞0、re_d(v2)＞0和diam(T∪e)≤Δ(Δ为直径约束值).若S'=∅，则查找失败，结束.否则转到Step 4;

Step 4选择选S'中最小边e*=(v1'，v2')加入到当前生产树T，即S=S∪v2'，E0=E0∪e*.更新节点v1'和v2'的剩余度标号re_d(v1')=re_d(v1')-1和re_d(v2')=re_d(v2')-1，节点v2'的距离标号u(v2')=u(v1')+1，节点v2'的前趋标号pred(v2')= v1'.转到Step 1.

算法时间复杂度分析:该算法主要计算量在Step 3求集合S'和Step 4查找集合S'中最小边，求集合S'的时间复杂度为O(m)，查找S'中最小边的时间复杂度为O(m)，则Step 3和Step 4的计算复杂度为O(m)，因为它们最多执行n-1步，所以该算法的时间复杂度为O(mn).

4 数值实验

本节对算法的性能进行分析，用Matlab编程实现本算法，大量实验结果表明此算法有较高的效率.下面列举了部分实验结果.

例1对大规模随机数据的实例进行测试，借鉴文献［9］生成数据的方法，随机生成n个节点的无向完全网络G，网络中边的权值为［1，9］之间的随机整数，节点的度约束为［1，「n/2⌉］之间的一个随机整数.分别取节点数n=50、100、250、500、1 000，直径约束值分别取Δ=10、15、20、25、30.

分别求得度、直径约束最小生成树的总代价W(T)和直径diam(T)如表1.通过与各实例中求得不含任何约束的最小生成树进行比较，可知此算法有较好的效果.

表1 启发式算法求的度、直径约束最小生成树

例2选用Beasley’s OR-library(http:// www.people.brunel.ac.uk)提供的例子.Beasley’s OR-library给出不同规模的度量施泰纳树问题的很多例子，每个规模提供15个例子.算例说明:n表示规模即节点总数、Number表示对应规模的第几个例子、节点的度约束取［1，「n/2⌉］之间的一个随机整数.用本算法求解的结果如表2.

表2 本启发式算法求解例2结果

5 结语

DCBDMST问题是异常困难的组合优化问题，本文给出的启发式算法能在一定程度上较好地求解此问题.下一步的工作将为该问题设计合适的智能算法如蚁群算法、遗传算法等，将求解的结果与本文求解的结果进行比较分析.

［1］AHUJA R K，MAGNANTI T L，ORLIN J B.Network flows:Theory，algorithms，and applications［M］.Beijing: Mechanical-Industry Press，2005.

［2］NARULA S C，HO C A.Degree-constrained minimum spanning tree［J］.Computers and Operations Research，1980，7(4):239-249.

［3］TORKESTANI J A.Degree-constrained minimum spanning tree problem in stochastic graph［J］.Cybernetics and Systems，2012，43(1):1-21.

［4］JULSTROM B A.Greedy heuristics for the bounded diameter minimum spanning tree problem［J］.Journal of Experimental Algorithmics(JEA)，2009，14(1):1-14.

［5］LUCENA A，RIBEIRO C C，SANTOS A C.A hybrid heuristic for the diameter constrained minimum spanning tree problem［J］.Journal of Global Optimization，2010，46 (3):363-381.

［6］GAREY M R，JOHNSON D S.Computers and intractability:A guide to the theory of NP-completeness［M］.San Francisco:WH Freeman＆Co，1979:206-218.

［7］吴家皋.覆盖多播路由的算法及协议研究综述［J］.计算机科学，2007，34(6):7-12.

［8］PAPADIMITRIOU C H.Computational complexity［M］. Boston:Addison Wesley，2004.

［9］BINH H T T，HOAI N X，MCKAY R I.A new hybrid genetic algorithm for solving the bounded diameter minimum spanning tree problem［C］//IEEE World Congress on Computational Intelligence.Hong Kong，2008:3128-3134.

(责任编辑庄红林)

Degree-Constrained and Diameter-Constrained Minimum Spanning Tree Problem and Its Algorithm

SHI Lei，FENG Zu-zhen，YANG Jian-qiang
(Department of Mathematics，Honghe University，Mengzi 661100，China)

The degree-constrained and diameter-constrained minimum spanning tree problem was discussed，which proved to be NP-Complete.A mathematical programming model of the problem was proposed.A heuristic algorithm was proposed to solve this problem，whose time complexity was O(mn).The algorithm was proved to be effective through analysis and experiments.

minimum spanning tree;heuristic algorithm;degree-constrained;diameter-constrained

O 157.6

A

1672-8513(2012)04-0295-03

10.3969/j.issn.1672-8513.2012.04.016

2012-03-29.

国家自然科学基金(11161020);红河学院硕博基金(10BSS136).

石磊(1984-)，男，硕士，助教.主要研究方向:网络安全、智能算法.