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

• 作者: 刘旭东 李娴 林学练 韩军
• 来源期刊: 哈尔滨工程大学学报
• 学科: 工学
• 关键词: 最小生成树 分支定界 搜索树 剪枝
• 年，卷（期）: 2007,（12）
• 页码范围: 1371-1376
• 页数: 6页
• 分类号: TP301.6
• 字数: 5127字
• 语种: 中文
• DOI: 10.3969/j.issn.1006-7043.2007.12.015

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	韩军	北京航空航天大学计算机学院	15	237	8.0	15.0
2	刘旭东	北京航空航天大学计算机学院	42	483	11.0	21.0
3	林学练	北京航空航天大学计算机学院	19	106	6.0	10.0
4	李娴	北京航空航天大学计算机学院	4	5	2.0	2.0