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

作     者：熊小华 宁爱兵 

作者机构：上海第二工业大学计算机与信息学院上海201209 上海理工大学管理学院上海200093 

出 版 物：《上海第二工业大学学报》 (Journal of Shanghai Polytechnic University)

年 卷 期：2011年第28卷第3期

页      面：207-213页

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 08[工学] 070105[理学-运筹学与控制论] 0701[理学-数学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

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

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

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