分支限界法与回溯法的区别1.求解目标不同 1.回溯法的求解目标是找出解空间树中满足约束条件的所有解 2.分支限界法的求解目标则是尽快找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解 3.分支限界法通常用于解决离散值的最优化问题2.搜索方式不同 1.回溯法以深度优先的方式（遍历结点）搜索解空间树 2.分支限界法以广度优先或最小耗费优先的方式搜索解空间树3.对扩展结点的扩展方式不同 1.分支限界法中，每一个活结点只有一次机会成为扩展结点 2.活结点一旦成为扩展结点，就一次性产生其所有儿子结点4.存储空间的要求不同 1.分支限界法的存储空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大
分支限界算法可以用来寻找最优解，在平均情况下不必穷尽搜索
分支限界算法的搜索类似于最佳优先算法并做了一些改进（比如剪枝）
两个要点：
如何产生分支
如何产生界限
基本思想：
用一种方法分开解空间
用一种方法预测一系列解的最小界（lower bound），用一种方法预测最优解的最大界（upper bound）
如果一个解的最小界超出了整个解空间的最大界，那么这个解不可能是最优的，我们就可以提前终止此分支
分支界限适合最小化问题
平均情况下，许多分支能较早被终止，但许多NP难问题在最坏情况下仍是指数级的
