度约束最小生成树的元胞竞争决策算法

熊小华，宁爱兵

（1. 上海第二工业大学计算机与信息学院, 上海 201209；2. 上海理工大学管理学院, 上海 200093）

度约束最小生成树的元胞竞争决策算法

熊小华1，宁爱兵2

（1. 上海第二工业大学计算机与信息学院, 上海 201209；2. 上海理工大学管理学院, 上海 200093）

度约束最小生成树(Degree-Constrained Minimum Spanning Tree, 简记DCMST)是网络设计和优化中的一个经典的组合优化难题。竞争决策算法是一种特别适合于求解组合优化难题的新型算法。为了提高求解DCMST问题的求解精度，将元胞自动机的邻居演化原理和竞争决策算法相结合——元胞竞争决策算法来求解DCMST；为了提高算法的效率，分析了度约束最小生成树问题的数学性质并利用这些性质对问题实现降阶。降阶过程会有效降低问题处理的规模。为了验证算法的性能，采用Delphi 7.0实现算法，经过数据测试和验证，并与其他算法的结果进行比较，证明了算法的有效性。

竞争决策算法；元胞自动机；度约束最小生成树；降阶

0 引言

最小生成树(Minimum Spanning Tree，简记MST)[1-2]问题是一个经典的组合优化问题，许多工程问题如管道铺设、电路设计、交通网络等，通常都可转化为最小生成树问题。最小生成树是构造一个带权图的最小代价生成树，可使用避圈法、破圈法等成熟的方法求解[3]。但如果对树的各顶点度数加以限制，即不超过预先给定的数值，则问题的性质变得截然不同，这就是所谓的度约束最小生成树(Degree-Constrained Minimum Spanning Tree, 简记DCMST)，其组合含义就是从所有的生成树中(数目可达nn-2)找出所有顶点符合约束且权值最小的生成树。现实世界中有许多这样的例子，如管道铺设、电路设计等，为了可靠性而要求顶点度数符合一定的规定。

DCMST问题的求解难度随各顶点度约束的不同而不同。设各个顶点的度约束为bi(i=1,2,…,n)。当bi至少为n-1时，即为无限制情况下的一般的MST问题；而当bi都为2时，则是著名的TSP问题，TSP问题是NP难题，是否存在有效算法尚不可知。当所有顶点的度约束值相同且都为一常数c时，度约束最小生成树问题又称为d-MST问题。因此，就一般情形而言，DCMST问题是一个难解难题。曾经有一些学者采用精确算法(如分支定界法、隐枚举法等)都是指数级别运行时间，无法求解中型以上规模的实际问题。本文利用元胞竞争决策算法，给出求解DCMST问题的一种新思路，经过大量的算例测试，效果优于目前的常见算法，体现了算法的优越性。

1 竞争决策算法简介

竞争决策算法(Competitive Decision Algorithm，简记CDA)是近几年来提出的一种求解组合优化难题的新算法[4-10]。通过观察自然界中的竞争和决策发现，它们都是在一定竞争规则下，在竞争者的实力、竞争者和环境间的关系、多个竞争者实力的差距和初始竞争状态等多种因素的共同作用下，经过多次竞争和决策后，使不同的竞争者分别占有一定的资源而达到一种新的竞争状态。只要新的竞争状态优于初始竞争状态，算法就会达到优化的目的。算法吸收了达尔文“优胜劣汰”的进化思想以及演化博弈论中有限理性竞争者的思想，通过构造一个或多个具有有限理性的竞争者参与到对一个或多个资源的竞争过程中，通过优胜劣

2 元胞自动机简介

元胞自动机最早由冯·诺依曼提出。沃尔夫勒姆等[10-11]将动力系统方法、计算理论及形式化语言方法引入元胞自动机的研究中，促进其广泛应用。

元胞自动机是一个时间和空间都离散的动力学系统，由元胞、状态、邻居和规则四部分组成。用数学符号表示，标准的元胞自动机是一个四元组： A=(Ld, S, N, f), 其中A代表一个元胞自动机系统；L代表元胞空间，d表示元胞空间的维数；S表示元胞有限的、离散的状态集合；N表示所有领域内元胞的组合，记为N=(S1,S2,…,Sn), n是元胞邻居的个数。每个元胞至少要有一个邻居，在一个固定距离的范围内，邻居可以直接访问它，而在范围之外，对它没有直接的影响。元胞邻居的定义有多种方法，如冯·诺依曼(Von Neumann)型、摩尔(Moore)型、扩展的摩尔(Moore)型等。f是一个局部转换函数，转换规则定义了系统的动力学行为。

元胞空间内的每个元胞遵循相同的演化规则，而大量的元胞通过简单的相互作用而构成动态系统的演化。元胞在元胞空间里，按照演化规则有很多种变化。若元胞的状态有k种，状态的更新由自身及邻居n个元胞的状态共同决定，则可能有的状态有种，元胞的邻域能产生很多变化，这将增加群体的多样性，提高进化的收敛速度，也能更加自然地模拟自然进化智能。元胞自动机具有重复简单的演化规则导致复杂的系统行为的能力，通过局部的变化可以实现全局计算。这也是拟将元胞自动机引入竞争决策算法的原因所在。

3 DCMST的元胞竞争决策算法

3.1 问题介绍

考虑一个连通的无向简单图[12-13](无环无多重边的图即为简单图) G=(V,E,W)，其中V={1,2,…,n}为顶点集， E={e1, e2,…,em}为边集，若边ek的的顶点为i和j，则边ek可记为(i, j)。各顶点间的权值wij已知(wij＞0, wii=∞, i, j∈V)，各顶点的度限制为bi(i =1,2,…,n)。

设

则度约束最小生成树问题的数学模型可以写成：

这里|S|为集合S中所含图G的顶点个数。前两个约束保证所得到的是一棵树，第三个约束为顶点度约束。

3.2 DCMST性质的分析

不同于其他启发式算法，竞争决策算法具有便于结合问题本身性质的特性，这将加快问题的求解速度。为了降低问题的求解难度，在讨论DCMST问题的元胞竞争决策算法之前，先讨论问题本身的性质。

定理1 图G中所有的悬挂点(即度为1的顶点) 所关联的边一定在度约束最小生成树上T*。

证明 因为度约束最小生成树T*是连通的，因此，若存在度约束最小生成树，则悬挂点所关联的边一定在度约束最小生成树中。否则，T*必定不是连通的。

由定理1可知，可利用定理1对问题进行降阶处理。在算法最开始，将所有悬挂点及其关联边从图中移除，此时可能产生新的悬挂点，可以继续应用定理1降阶，直到不存在悬挂点为止。

证明 使用反证法。

假设有一条E1中的边(vi, vj)在度约束最小生成树T*上。由于vi, vj都是度限制为1的顶点，故这两个顶点都不能与顶点集V中其他的顶点有边相连，此时，与T*是度约束最小生成树相矛盾。所以假设错误，E1中所有的边一定不在度约束最小生成树上T*。

应用定理2可以快速排除一定不在度约束最小生成树上的边。对于关联的两个顶点都是度限制为1的边，由定理2可知，可以快速排除一定不在度约束最小生成树上，将这些边从原图上移除，这将进一步降低问题求解的规模。

定理3 若vk是图G中的一个度为2的结点，且结点vi, vj是与之相邻的两个结点，若vi, vj相连的所有路径都必须通过结点vk，则边(vi, vk)和(vk, vj)一定在度约束最小生成树上T*。

证明 使用反证法。

假设边 (vi, vk)和 (vk, vj)不在T*上。由于不存在一条将vi、vj相连的路径不经过结点vk，而由假设知道(vi, vk)和(vk, vj)不在T*上，因此，T*此时一定不连通，这与T*是度约束最小生成树相矛盾。假设错误，边(vi, vk)和 (vk, vj)一定在度约束最小生成树上T*。

应用定理3可以用来快速判断一定在度约束最小生成树上的边。对于度为2的顶点vk，若其关联的两个顶点在与vk断开的情况下不可达的话，则可以判断vk关联的两条边一定在度约束最小生成树上。这又将降低问题求解的规模与难度。

3.3 算法原理

n个顶点的度约束最小生成树共有n-1条边，只有一个连通分支，且不存在回路，因此可以把求解度约束最小生成树问题看作是按照竞争力和决策原则把n-1条边依次加入到初始无边且包含n个顶点的图中。在边加入的过程中必须保证不形成任何子回路且不超过顶点的度限制值。本算法只有一个非虚拟竞争者A，即初始无边且包含n个顶点的图，被竞争的资源为所有边资源，初始格局是竞争者没有占有边资源，为虚拟竞争者N所占用，竞争结束时竞争者A应占有n-1条边。

3.4 基本符号及含义

为了方便描述，本文采用如下符号来表示。

n: DCMST问题的顶点个数；

w[i, j]: 权值矩阵，表明顶点i与j连线的的权值；

b[i]: 第i个顶点的度数约束；

dot_num[i]: 第i个顶点当前的度数；

cur_b[i]: 第i个顶点当前可连的边数，cur_b[i]= b[i]- dot_num[i]；

arrive_w[i, j]: 邻接矩阵，表明顶点i与j是否直接相邻;

t_arrive_w[i, j]: arrive_w[ ]的传递对称闭包[12]，表明顶点i与j是否能够到达(包含通过其它结点中转到达);

All_line[i]：这是一个边的集合，即图中所有与顶点i关联的边;

Line[i]：All_line[i]的子集，边的一个顶点为i，设边的另一个顶点编号为k，则满足t_arrive_w[i,k]=0，即结点k在当前图中不能到达(含传递到达)顶点i;

dw[i,k]: Line[i]中权值第k小边的权值(其中1≤k≤2);

dw_j [i,k]：Line[i]中权值第k小边的另一个顶点的编号(一个顶点编号为i，其中1≤k≤2);

power[i]：图对顶点i的竞争力函数值，即把边（i, dw_j [i,1]）加入到图中的能力；

max_power_id：当前决策函数选中顶点的编号，即按照当前竞争力和决策函数，下一次加入到图中的边为（max_power_id, dw_j [max_power_id, 1]）；

3.5 初始状态、竞争力函数、决策函数和元胞及元胞演化规则

(1) 初始状态

反复应用定理1、定理2和定理3后，在原图上存在的是无法确定是否在度约束最小生成树上的边资源。初始状态只有一个。虚拟竞争者N占有所有未确定边资源。竞争者A占有确定一定在度约束最小生成树上的边资源。

(2) 竞争力函数

本算法所采用的竞争力函数的基本思想可描述如下：DCMST中与每一顶点相连的边至少有一条在树中，因此，把权值为dw[i,1]的边称为基本边，而把权值为dw[i, 2]称为候补边。为了取得好的效果，应该在满足度约束的条件下，把候补边与基本边差距最大的边优先加入到图中以减少因为基本边不能加入到图中而造成较大的损失。

本算法采用以下三个竞争力函数：

(i) power[i]=1/ dw[i, 1]，满足条件的边中权值最小的竞争力最大；

(ii) power[i]= dw[i, 2] - dw[i, 1]，候选边与基本边权值差距最大的边竞争力最大；

(iii) power[i]=( dw[i, 2] - dw[i, 1])-( dw[i, 1]- dw[k, 1]) (k= dw_j [i, 1])，它在竞争力函数(ii)的基础上，考虑边(i, k)加入到图中对顶点k的基本边造成的损失值(dw[i,1]- dw[k,1])。

(3) 决策函数

决策函数分两种情况来介绍：

(i) 当竞争者占有的资源(即边的条数)小于n-2

在满足条件的顶点中选择power[i]值最大的。若两个顶点的power[i]值相同时，则选择编号小的顶点。(ii) 当竞争者占有的资源(即边的条数)等于n-2(即此时仅剩最后一条边)

当目前竞争者手头已经找到了n-2条边，此时只剩下一条边就找到了DCMST的所有边，因此，从所有能加入到DCMST中且权值最小的边给竞争者。

(4) 元胞、邻居定义及元胞演化规则

定义2 元胞邻居采用扩展Moore邻居类型，

其中diff(CellY−CellX)≤r 为两个组合取值的差异，若无差异为0，有差异时，最小为2。r为差异的程度，本文中r为2。

定义3 元胞演化规则：依据元胞邻居的定义计算其邻居（与中心元胞相差一条边的生成树）的目标解，比较中心元胞和其邻居的差异，选择最好的目标解。

定义4 元胞自动机边界条件，为了更好的模拟无限空间，采用周期型空间定义。

3.6 算法流程

步骤1 重复剔除整体上的劣质资源或重复固定整体上的优秀资源

按照定理1，2，3确定一定在与一定不在度约束最小生成树上的边资源；

设ini_line_count为固定下来的边资源；

步骤2 初始化

最大的竞争步数=n；

p_count=3; d_count=1; la_count=1 //此三项分别为竞争力函数、决策函数和初始格局的个数

步骤3 竞争、决策及资源交换

for p=1 to p_count //竞争力函数个数循环

for d=1 to d_count //决策函数个数循环

for la =1 to la_count //初始格局个数循环

arrive_w和t_arrive_w矩阵全为0；

计算每个顶点的dw[i, 1], dw_j[i, 1], dw [i, 2], dw_j[i, 2]；

根据第p个竞争力函数计算power[i]；

根据power[i]计算max_power_id ； （这里的 1≤i≤n）

竞争步数=0; line_count=ini_line_count； //图中边的个数

每个顶点的cur_b[i]=b[i]-在优质边资源上的度消耗；

步骤3.1 本轮竞争阶段1: 资源分配和争夺阶段

repeat

dot_1=max_power_id; //要加入边的一个顶点编号

dot_2= dw _j[dot_1,1]; //要加入边的另一个顶点编号

竞争步数=竞争步数+1;

line_count= line_count+1;

cur_b[i]= cur_b[i]-1;

arrive_w[dot_1, dot_2]= true; arrive_w[dot_2, dot_1]= true;

for i=1 to n //当在图上添加一条边(dot_1,dot_2)时更新t_arrive_w[ ]矩阵

if (t_arrive_w[i,dot_1]=true) or(i=dot_1) then //与结点dot_1关连的点i,

for j=1 to n

if (t_arrive_w[j, dot_2]=true) or(j=dot_2) then //与结点dot_2关连的点j,

if (i＜＞j) then

{t_arrive_w[i, j]=true; t_arrive_w[j, i]=true}

重新计算一部分结点的dw [i, k], dw_j[i, k]（这里只重新计算因为边(dot_1, dot_2)加入到图中而发生变化的点，其中1≤k≤2）;

根据第p个竞争力函数重新计算一部分由于边(dot_1, dot_2)加入到图中而发生变化点的power[i] ;

根据决策函数计算max_power_id;

until (line_count=n-1 or竞争步数＞=最大的竞争步数)

根据矩阵arrive_w和矩阵w得到度约束最小生成树的路径和总权值。

将本轮竞争取得的结果与保存的最优解比较其占优情况，若优于保存的最优解，则替换之。

步骤3.2 本轮竞争阶段2：元胞演化

按元胞邻居的定义，以当前求得目标最好的解为中心元胞，寻找所有的邻居。在邻居范围内演化，按照定义的演化规则，若邻居的解优于目前最好解，并替换最好解。

步骤4 输出竞争决策得到的结果解。

4 数值算例

为了验证算法的有效性，在Windows XP下用Delphi 7.0实现了该算法，并用来求解了大量的度约束最小生成树问题，算法求解的效果良好。限于篇幅，这里给出一个小规模算例的计算结果及边资源情况。

算例n=9，度约束b={2, 1, 4, 2, 3, 2, 1, 5, 1}，给定图的权值矩阵如下：

解

竞争决策算法的求解结果为2 900。

由定理2降阶可知：(2,7), (2,9), (7,9)必定不在度约束最小生成树上。

用元胞竞争决策算法程序求解得：生成树权值为2 890，连线T= {(1,3), (1,6), (2,3), (3,5), (4,6), (4,8), (7,8), (8,9)}。

5 结束语

竞争决策算法是一种能广泛应用于求解各类组合优化难题的新型寻优算法，其通用性和实用性都比较强，在离散空间问题求解中，表现出其优越性。将元胞自动机理论局部更新引起全局计算的特性与竞争决策算法原理相结合用来求解度约束最小生成树问题，进一步丰富了竞争决策算法的理论基础。整个算法操作简单，具有较好的通用性。试验结果表明，算法具有较好的效果。

[1] AHUJA R K, MAGNANTI T L, ORLIN J B. Network Flows: Theory, Algorithms, and Applications (English Version) [M]. Beijing: Mechanical Industry Press, 2005.

[2] SYSLO M M, DEO N, KOWALIK J S. Discrete Optimization Algorithms [M]. Englewood Cliffs, New Jersey: Prentice-Hall, Inc., 1983:370-373.

[3] 马良, 朱刚, 宁爱兵. 蚁群优化算法[M]. 北京: 科学出版社, 2008.

[4] 宁爱兵, 马良. 竞争决策算法及其在车辆路径问题中的应用[J]. 管理科学学报, 2005, 8(6):10-18.

[5] 宁爱兵, 马良. 度约束最小生成树(DCMST)的竞争决策算法[J]. 系统工程学报, 2005, 20(6): 630-634.

[6] 宁爱兵, 马良, 熊小华. 竞争决策算法原理及其应用[J]. 上海理工大学学报, 2008, 30(4): 369-373.

[7] 宁爱兵, 马良. 大规模旅行商问题(TSP)的竞争决策算法[J]. 计算机工程, 2005, 31(9): 23-26.

[8] 宁爱兵,马良. 0-1背包问题竞争决策算法[J]. 计算机工程与应用, 2008, 44(3): 14-16,38.

[9] 熊小华, 宁爱兵, 马良. 基于多交换邻域搜索的多维0/1背包问题竞争决策算法[J]. 系统工程理论与实践, 2010, 30(8): 1448-1456.

[10] WOLFRAM S. Theory and pplication of Cellular Automata[M]. Singapore: The World Scientific Publishing Company Limitd, 1986.

[11] WOLFRAM S. Computation theory of cellular automata[J]. Communications in Mathematical Physics, 1984, 96(1): 15-57.

[12] 左孝凌, 李为监, 刘永才. 离散数学[M]. 上海: 上海科学技术文献出版社, 1982.

[13] 卢开澄. 计算机算法导引[M]. 北京: 清华大学出版社, 1996.

Cellular Competitive Decision Algorithm for Degree-Constrained Minimum Spanning tree Problem

XIONG Xiao-Hua1, NING Ai-Bing2
(1. College of Computer and Information, Shanghai Second Polytechnic University, Shanghai 201209, P. R. China; 2. School of Management, University of Shanghai for Science and Technology, Shanghai 200093, P. R. China)

Finding the Degree-Constrained Minimum Spanning Tree (DCMST for short) of a graph is a classical combinatorial optimization hard problem in network-designing and optimization. Competitive decision algorithm (CDA for short) is a new type algorithm especially suitable for solving combinatorial optimization problems. Cellular competitive decision algorithm for DCMST is presented here to improve the accuracy of the solution, which introduced the neighborhood evolution of cellular automata into CDA. To speed up the algorithm, the mathematical properties of DMST are used to reduce the scale of instances. To verify the effectiveness of the algorithm, it is being coded in Delphi 7.0 and series of instances are tested here.

competitive decision algorithm; cellular automata; degree-constrained minimum spanning tree; reduction

O223, TP301

A

2011-02-20;

2011-08-04

熊小华（1978－），女，江西南昌人，博士，讲师，研究方向为算法设计、系统工程，电子邮箱xiong_xiao_hua@163.com。

国家自然科学基金项目（No. 70871081），上海市重点学科建设基金项目（No. S30504）汰的原则使一部分竞争者获得资源而增加实力，一部分竞争者失去资源削弱实力甚至消亡。当算法通过竞争不能获得更优的结果时，通过资源交换使算法进入下一轮的竞争。在理论方面，现在已给出了竞争决策算法的通用流程、特点、分类、主要概念及其数学描述、常用的竞争力函数、常用的决策函数、常用的初始状态以及常用的资源交换规则等。在应用方面，已利用其通用流程实现了车辆路径问题[4]、度约束最小生成树[5]、旅行商问题[7]、背包问题[8-9]等NP难题的算法并编程实现。

1001-4543(2011)03-0207-07