CMST问题的分支定界算法

作     者：韩军 李娴 Zhaohao Sun 林学练 HAN Jun;LI Xian;Zhaohao Sun;LIN Xue-lian

作者机构：北京航空航天大学计算机学院北京100083 University of WollongongAustralia 

基　　金：国家自然科学基金资助项目(60473010) 国家自然科学基金重大研究计划资助项目(90412011) 

出 版 物：《哈尔滨工业大学学报》 (Journal of Harbin Institute of Technology)

年 卷 期：2007年第39卷第9期

页      码：1478-1482页

摘      要：研究了网络优化设计中具有流量约束的最小生成树(CMST)问题,以是否聚合点对为条件,提出了一类新的基于点集分割思想的分支定界算法,阐述了算法的原理,通过分析搜索最优解的过程说明了算法的优势.计算结果表明,提出的算法相对于原有的基于边的分支定界算法平均减少了约83%的搜索步数,并节约了68%的计算时间.

主 题 词：最小生成树 分支定界 松弛 剪枝 

学科分类：0810[工学-土木类] 08[工学] 0805[工学-能源动力学] 0812[工学-测绘类] 081202[081202] 

核心收录：

D　O　I：10.3321/j.issn:0367-6234.2007.09.032

馆 藏 号：203123978...