度约束最小生成树(DCMST)的竞争决策算法  

Competitive decision algorithm for the degree-constrained minimum spanning tree

作　　者：宁爱兵[1] 马良[1] 

机构地区：[1]上海理工大学管理学院,上海200093

出　　处：《系统工程学报》2005年第6期630-634,共5页Journal of Systems Engineering

基　　金：国家自然科学基金资助项目(70471065)

摘　　要：度约束最小生成树是网络设计和优化中的一个NP难题,介绍了一种基于竞争造就优化和决策左右结果的新型算法———竞争决策算法,利用竞争决策算法的通用模型,给出了一种基于竞争决策思想求解度约束最小生成树的快速求解方法,经过数据测试和验证,并与其它算法的结果进行了比较,得到了较好的结果.Finding the degree-constrained minimum spanning tree （DCMST） of a graph is a NP-hard problem which is important in the network design and optimization. A competitive decision algorithm is introduced , which is a new optimization idea based on the characteristics that competition builds optimisation and the result of competition hinges on decision. According to the general model of competitive decision algorithm, a competitive decision algorithm for DCMST is proposed. Series of numerical examples of DCMST are tested and the computational performances of the algorithm are compared those of some other algorithms in the literatures.

关 键 词：度约束最小生成树 竞争决策算法 竞争力函数 决策函数 

分 类 号：O223[理学—运筹学与控制论]