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

熊小华，宁爱兵

（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)找出所有顶点符合约束且权值最小的生成树。……