分支限界算法的研究与实现  

Research and Implementation of Branch and Bound Algorithm

作　　者：王春梅[1] 

机构地区：[1]西安邮电学院计算机学院,陕西西安710121

出　　处：《现代电子技术》2011年第9期121-123,共3页Modern Electronics Technique

摘　　要：分支限界算法是一种在问题的解空间树上搜索问题的解的方法,主要采用广度优先或最小耗费优先的方法搜索解空间树,其核心思想就是"剪枝"。首先提出了分支限界算法的一般策略与实施步骤,然后以电路板布线问题为实例,设计并实现该问题的算法,经过实验数据验证了其性能,进而反映了分支限界算法的高效性。The algorithm of branch and bound is a solution to search problems in the tree of solution space,whose main solution is breadth-first search（BFS） or the least cost first,and the central idea is ＂pruning＂.The general strategy and implementation steps of the branch and bound algorithm are proposed.Taking the wiring problem of circuit board as an example,whose algorithm is designed and implemented.The efficiency of the branch and bound algorithm is verified through experimental data,and its high performance is showed.

关 键 词：分支限界 解空间树 活结点 扩展结点 

分 类 号：TN911-34[电子电信—通信与信息系统]