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

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

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

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.