概念
分支限界算法类似于回溯算法，也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同。
回溯算法与分支限界法的不同之处
求解目标
- 回溯算法的求解目标：是找出T中满足约束条件的所有解。
- 分支限界算法的求解目标：是找出满足约束条件的一个解，或者是在满足约束条件的解中找出使某一目标函数值达到极大或者极小的解。（即：最优解）
搜索方式：由于求解目标不同，导致分支限界法和回溯法在解空间树T上的搜索方式也不相同。
- 回溯法：以深度优先的方式搜索解空间树T。
- 分支限界法：以广度优先的方式或者以最小耗费优先的方式搜索解空间树T。
基本思想
在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。
此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。
与回溯算法相似，限界函数的设计是分支限界法的一个核心问题。如何设计好限界函数来有效地减少搜索空间是应用分支限界法要考虑的问题。
分支限界法首先确定一个合理的限界函数，并根据限界函数确定目标函数的界[down, up]；然后按照广度优先策略遍历问题的解空间树，在某一分支上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的目标函数的可能取值（对最小化问题，估算结点的down，对最大化问题，估算结点的up）。如果某孩子结点的目标函数值超出目标函数的界，则将其丢弃（从此结点生成的解不会比目前已得的更好），否则入待处理表（活动表）。
根据从活动节点表中选择下一扩展节点的不同方式，可将分支限界法分为2种不同的类型：
队列式(FIFO)分支限界法
按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。
搜索策略
一开始，根结点是唯一的活结点，根结点入队。从活结点队中取出根结点后，作为当前扩展结点。对当前扩展结点，先从左到右地产生它的所有儿子，用约束条件检查，把所有满足约束函数的儿子加入活结点队列中。再从活结点表中取出队首结点（队中最先进来的结点）为当前扩展结点，……，直到找到一个解或活结点队列为空为止。
优先队列式分支限界法
按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。（通常在算法中用一个最大堆来实现最大优先级队列）。
搜索策略
对每一活结点计算一个优先级（某些信息的函数值），并根据这些优先级；从当前活结点表中优先选择一个优先级最高（最有利）的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。再从活结点表中下一个优先级别最高的结点为当前扩展结点，……，直到找到一个解或活结点队列为空为止。
示例
问题：0-1背包问题，当n=3时，w={16,15,15}, p={45,25,25}, c=30
当n=3时候，解空间。1
{{0，0，0}，{0，1，0}，{0，0，1}，{1，0，0}，{0，1，1}，{1，0，1}，{1，1，0}，{1，1，1}}
1：物品需要放到包里
0：物品不需要放到包里
步骤
- 初始化时候活动点队列为空。
- 节点A是当前扩展节点，它的两个儿子节点B和C均为可行节点，将两个儿子节点按照从左到右的顺序加入活节点队列，并且舍弃当前扩展节点A。
- 按照先进先出的原则，下一个扩展节点是活节点队列的队首节点B。扩展节点B得到其儿子节点D和E。由于D是不可行节点，故被舍去。E是可行节点，被加入活节点队列。此时，活节点队列中的元素是C和E。
- C成为当前扩展节点，它的两个儿子节点F和G均为可行节点。因此被加入活节点队列。此时活节点是E、F、G。
- 扩展下一个节点E，得到节点J和K。J是不可行节点，因而被舍去。K是一个可行的叶节点，表示所求问题的一个可行解，其价值为45。此时活动节点队列中的元素是F和G。
- 当前活节点队列的队首节点F成为下一个扩展节点。它的两个儿子节点L和M均为叶节点。L表示获得价值为50的可行解，M表示获得价值为25的可行解。
- G释最后一个扩展节点。其儿子节点N和O均为可行叶节点。最后活节点队列为空。算法终止。
- 算法搜索得到最优解的值是50。对应的可行解为（0，1，1）。
