1、概念：
分支定界算法(Branch and bound，简称为BB、B&B, or BnB)始终围绕着一颗搜索树进行的，我们将原问题看作搜索树的根节点，从这里出发，分支的含义就是将大的问题分割成小的问题。大问题可以看成是搜索树的父节点，那么从大问题分割出来的小问题就是父节点的子节点了。分支的过程就是不断给树增加子节点的过程。而定界就是在分支的过程中检查子问题的上下界，如果子问题不能产生一比当前最优解还要优的解，那么砍掉这一支。直到所有子问题都不能产生一个更优的解时，算法结束。
2、例子：
用BB算法求解下面的整数规划模型
因为求解的是最大化问题，我们不妨设当前的最优解BestV为-INF，表示负无穷。
1.
首先从主问题分出两支子问题：
通过线性松弛求得两个子问题的upper bound为Z_LP1 = 12.75，Z_LP2 = 12.2。由于Z_LP1 和Z_LP2都大于BestV=-INF，说明这两支有搞头，继续往下。
2.
3.
从节点1和节点2两个子问题再次分支，得到如下结果：
子问题3已经不可行，无需再理。子问题4通过线性松弛得到最优解为10，刚好也符合原问题0的所有约束，在该支找到一个可行解，更新BestV = 10。
子问题5通过线性松弛得到upper bound为11.87>当前的BestV = 10，因此子问题5还有戏，待下一次分支。而子问题6得到upper bound为9<当前的BestV = 10，那么从该支下去找到的解也不会变得更好，所以剪掉！
4.
对节点5进行分支，得到：
子问题7不可行，无需再理。子问题8得到一个满足原问题0所有约束的解，但是目标值为4<当前的BestV=10，所以不更新BestV，同时该支下去也不能得到更好的解了。
6.
此时，所有的分支遍历都完成，我们最终找到了最优解。
3、算法过程（以最小化问题minimize f(x)为例）
1、使用启发式，找到优化问题的解决方案xh。存储其值，B = f（x_h）。（如果没有启发式可用，则将B设置为无穷大。）B将表示到目前为止找到的最佳解，并将用作候选解的上界。
2、初始化队列以保存部分解决方案，但不分配任何问题变量。
3、循环直到队列为空：
3.1从队列中取出一个节点N.
3.2如果N代表单个候选解x和f（x） 3.3否则，在N上分支以产生新的节点Ni。对于每个新节点： 3.3.1如果下线（N_i）> B，则什么都不做; 由于此节点的下限大于问题的上限，因此它永远不会导致最优解，并且可以被丢弃。 3.3.2否则，将Ni存入队列。 8. 其实代码该过程描述也很明了了。第1步可以用启发式找一个当前最优解B出来，如果不想也可以将B设置为正无穷。对于一个最小化问 题而言，肯定是子问题的lower bound不能超过当前最优解，不然超过了，该子问题就需要剪掉了。 第2第3步主要是用队列取构建一个搜索树进行搜索，具体的搜索方式由queue这个数据结构决定的。 注：B&B是围绕着一颗搜索树进行的，那么对于一棵树而言就有很多种搜索方式 1）Breadth-first search (BFS)：广度优先搜索，就是横向搜索，先搜索同层的节点。再一层一层往下。这种搜索可以用FIFO queue实现。 2）Depth-first search (DFS)：深度优先搜索，就是纵向搜索，先一个分支走到底，再跳到另一个分支走到底。这种搜索可以用LIFO queue也就是栈实现。 3）Best-First Search：最佳优先搜索，最佳优先搜索算法是一种启发式搜索算法（Heuristic Algorithm），其基于广度优先搜索算法，不同点是其依赖于估价函数对将要遍历的节点进行估价，选择代价小的节点进行遍历，直到找到目标点为止。这种搜索可以用优先队列priority queue来实现。
相关主题
文本预览