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

An efficient branch and bound algorithm for CMST problem

作　　者：李娴[1] 韩军[1] 林学练[1] 刘旭东[1] 

机构地区：[1]北京航空航天大学计算机学院,北京100083

出　　处：《哈尔滨工程大学学报》2007年第12期1371-1376,共6页Journal of Harbin Engineering University

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

摘　　要：针对网络优化设计中一类基本的、具有重要研究价值的问题——具有流量约束的最小生成树(CMST)问题进行了研究,提出了一种联合启发式搜索和分支定界方法的混合优化算法.通过应用邻域搜索策略,初始解有了极大的改进.提出的高效算法提高了遍历搜索树的效率,加快剪枝,并通过实验验证了该算法的性能.在阐述搜索最优解的过程中说明了该算法的优势.计算结果表明,新提出的高效分支定界算法极大地改进了原有的基于边的分支定界算法的效率.To resolve a fundamental and significant problem in the optimal design of communication networks-the capacitated minimum spanning tree （CMST） problem, with flow volume constraints we propose a hybrid optimization method in combination with the branch and bound technique and the heuristic search method. By using the neighborhood searching strategy, the initial solution was substantially improved. The proposed algorithm raises the efficiency of ergodic search trees and speeds up pruning. The results were verified with several experiments. The advantages of this algorithm in searching for the optimal solution were demonstrated, showing that the proposed algorithm is more efficient than the previous arc-orientated branch and bound algorithm.

关 键 词：最小生成树 分支定界 搜索树 剪枝 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]