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