CMST问题的高效分支定界算法研究

作     者：李娴 韩军 林学练 刘旭东 LI Xian;HAN Jun;LIN Xue-lian;LIU Xu-dong

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

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

出 版 物：《哈尔滨工程大学学报》 (Journal of Harbin Engineering University)

年 卷 期：2007年第28卷第12期

页      码：1371-1376页

摘      要：针对网络优化设计中一类基本的、具有重要研究价值的问题——具有流量约束的最小生成树(CMST)问题进行了研究,提出了一种联合启发式搜索和分支定界方法的混合优化算法.通过应用邻域搜索策略,初始解有了极大的改进.提出的高效算法提高了遍历搜索树的效率,加快剪枝,并通过实验验证了该算法的性能.在阐述搜索最优解的过程中说明了该算法的优势.计算结果表明,新提出的高效分支定界算法极大地改进了原有的基于边的分支定界算法的效率.

主 题 词：最小生成树 分支定界 搜索树 剪枝 

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

核心收录：

D　O　I：10.3969/j.issn.1006-7043.2007.12.015

馆 藏 号：203855713...