王春梅

摘 要：分支限界算法是一种在问题的解空间树上搜索问题的解的方法，主要采用广度优先或最小耗费优先的方法搜索解空间树，其核心思想就是“剪枝”。首先提出了分支限界算法的一般策略与实施步骤，然后以电路板布线问题为实例，设计并实现该问题的算法，经过实验数据验证了其性能，进而反映了分支限界算法的高效性。

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

中图分类号：TN911-34文献标识码：A

文章编号：1004-373X(2011)09-0121-03

Research and Implementation of Branch and Bound Algorithm

WANG Chun-mei

(Department of Computer, Xian Institute of Posts and Telecommunications, Xian 710121, China)

Abstract： 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.

Keywords： branch and bound; tree of solution space; live node; extension node

0 引 言

分支限界算法原在运筹学中用于求解整数规划(或者混合整数规划)问题，是过程系统综合的一类方法。将该方法原理用于过程系统综合可大大减少需要计算的方案数目。现如今，分支限界类算法应用极为广泛，如市场分析，方案选择，信号传输，人工智能等方面。因而，分支限界类算法具有较高的研究价值。本文首先提出了分支限界算法的一般策略与实施步骤；其次，设计并实现了电路板布线问题。

1 分支限界算法

分支限界算法又称为分支定界搜索法，分支是将一组解分为几组子解，限界是建立这些子组解的目标函数的边界。它是一种在问题的解空间树上搜索问题的解的方法，主要采用广度优先或最小耗费优先的方法搜索解空间树，并且在分支定界算法中，每一个活结点只有一次机会成为扩展结点在问题的解空间树上搜索问题的解的方法。

1.1 分支限界算法策略

对问题的解空间树进行搜索的策略为：