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

• 作者: 宁爱兵 熊小华
• 来源期刊: 上海第二工业大学学报
• 学科: 工学
• 关键词: 竞争决策算法 元胞自动机 度约束最小生成树 降阶
• 年，卷（期）: 2011,（3）
• 所属期刊栏目: 计算机与应用
• 页码范围: 207-213
• 分类号: O223|TP301
• 字数: 5710字
• 语种: 中文
• DOI: 10.3969/j.issn.1001-4543.2011.03.004

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	宁爱兵	上海理工大学管理学院	59	341	11.0	15.0
2	熊小华	上海第二工业大学计算机与信息学院	23	132	7.0	10.0