回溯法是一种深度优先策略来遍历问题的解空间树。分支限界法则是一种广度优先策略来搜索问题的解空间树。在确定解空间树的遍历策略后，分支限界根据限界函数来估算目标函数的可能取值，从而选取使目标函数取得极值的节点进行搜索，尽快找到问题的解。
1. 概述
分支限界法首先确定一个合理的限界函数，根据这个限界函数确定目标函数的界。然后，按照广度优先策略遍历问题的解空间树，在分支节点上，一次搜索该节点的所有孩子节点，分别估算这些孩子节点的目标函数的可能取值。如果某孩子节点的目标函数可能取得的值超出目标函数的界，则将其丢弃；否则，将其加入待处理节点表（简称为PT）中。然后，从PT中选取使目标函数值取得极值的节点，成为当前的扩展节点，重复上述过程，直到找到最优解。
使用分支限界法求解0/1问题
按照物品单位重量价值从大到小排序
目标函数：ub=v+(W−w)∗(vi+1/wi+1)，代表价值的上限。从物品1开始，不断选择物品放入背包，需要检查空间是否合适。如果空间合适，计算目标函数和节点一同放入PT中。然后从PT中选择目标函数最大的节点，继续选择物品，直到计算出结果。
1. 分支限界法的设计思想
假设求解最大化问题，问题的解向量为X=(x1,x2,…xn)，其中xi的取值范围为某个有穷集合Si，|Si|=ri(1
这个设计思想讲述了分支限界法的本质。应用分支限界法的关键问题是如何确定合适的限界函数、如何待处理节点表以及如何确定最优解中的各个分量。
2. 图问题中的分支限界法
TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次，然后回到出发城市，并要求所走的路程最短。对于一个正在生成的路径，假设已确定的顶点集合U=(r1,r2,…rk)，即路径上已确定了k个顶点，此时该部分解的目标函数值的计算方法为：lb的下限为((1+3)+(3+6)+(1+2)+(3+4)+(2+3))/2=14。上限使用贪心法计算出的数值为16，所以限界函数的界为[14, 16]。限界函数的设计有其特定的原因：容易计算、可以计算出下限等。解题过程中通常使用广度优先遍历，并没有使用到限界函数。类似的还有多段图的最短路径问题、任务分配问题等。在这些问题中，都需要先确定上下界和合理的限界函数，然后使用广度优先搜索进行求解。在实际项目中，类似于公交路线等问题也可以借鉴分支限界法进行求解。具体地可以参考代码实现进行学习理解。总结来说分支限界法是有套路可循的先确认上下界然后找出合理的限界函数最后使用广度优先遍历按照限界函数计算出的数值进行排序每次选取最小或最大值进行下一次的广度优先遍历乐扣里的题目很少有需要使用到限界函数的不过有一些题需要更多的技巧大家如果喜欢我的文章可以关注我的公众号程序员麻辣烫我的个人博客为shidawuhen.github.io往期文章回顾算法算习计划蛮力法分治法减治法动态
