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

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

作　　者：熊小华[1] 宁爱兵[2] 

机构地区：[1]上海第二工业大学计算机与信息学院,上海201209 [2]上海理工大学管理学院,上海200093

出　　处：《上海第二工业大学学报》2011年第3期207-213,共7页Journal of Shanghai Polytechnic University

基　　金：国家自然科学基金项目(No.70871081);上海市重点学科建设基金项目(No.S30504)

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

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

分 类 号：O224[理学—运筹学与控制论] TP301.6[理学—数学]