1、概念：
分支定界算法(Branch and bound，简称为 BB、B&B, or BnB)始终围绕着一颗搜索树进行的，我们将原问题看作搜索树的根节点，从这里出发，分支的含义就是将大的问题分割成小的问题。大问题可以看成是搜索树的父节点，那么从大问题分割出来的小问题就是父节点的子节点了。分支的过程就是不断给树增加子节点的过程。而定界就是在分支的过程中检查子问题的上下界，如果子问题不能产生一比当前最优解还要优的解，那么砍掉这一支。直到所有子问题都不能产生一个更优的解时，算法结束。
2、例子：
用BB算法求解下面的整数规划模型
因为求解的是最大化问题，我们不妨设当前的最优解BestV为-INF，表示负无穷。
- 首先从主问题分出两支子问题：
通过线性松弛求得两个子问题的upper bound为Z_LP1 = 12.75，Z_LP2 = 12.2。由于Z_LP1 和Z_LP2都大于BestV=-INF，说明这两支有搞头，继续往下。 - 从节点1和节点2两个子问题再次分支，得到如下结果：
子问题3已经不可行，无需再理。子问题4通过线性松弛得到最优解为10，刚好也符合原问题0的所有约束，在该支找到一个可行解，更新BestV = 10。
子问题5通过线性松弛得到upper bound为11.87>当前的BestV = 10，因此子问题5还有戏，待下一次分支。而子问题6得到upper bound为9
<当前的bestv =="" 10，那么从该支下去找到的解也不会变得更好，所以剪掉！<="" p="">
- 对节点5进行分支，得到：
子问题7不可行，无需再理。子问题8得到一个满足原问题0所有约束的解，但是目标值为4
<当前的bestv=10，所以不更新bestv，同时该支下去也不能得到更好的解了。< p="">
- 此时，所有的分支遍历都完成，我们最终找到了最优解。
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存入队列。
其实代码该过程描述也很明了了。第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来实现。
注：本文转载自
https://mp.weixin..com/s?__biz=MzI3NTkyODIzNg==&mid=&idx=1&sn=d420a9ab0a7c07aeb&chksm=eb7c0063dc0b8975d64931b5b35e971f6cf78972fbdc7705bb2f16ebba39a2402f2025eff8c9&mpshare=1&scene=1&srcid=&sharer_sharetime=45&sharer_shareid=0de8e83807&key=5c697a296e1d5a5c0aba9025fae36affa28405e30ce73943ae79c9507ddefec2f7f4109c201f2611d1e2f31645c71b84a0e797baf3f823a74aa6a2be0758d93c87f32996af02f012ee77ae1a2&ascene=1&uin=MjYzMDA1MzAyMQ%3D%3D&devicetype=Windows+10&version=&lang=zh_CN&pass_ticket=x2YOENqmw1WX%2BbY2oMQM2%2FvgZw9bCyJdvL36g%2Fad0MnNoTVOTcP2gVVONuueS7VV
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/216770.html原文链接：https://javaforall.net
