学习要点：

　　1、分支限界法与回溯法

　　2、分支限界法的剪枝搜索策略

　　3、分支限界法的算法框架：

　　　　（1）队列式(FIFO)分支限界法

　　　　（2）优先队列式分支限界法

　　4、应用范例：

　　　　（1）单源最短路径问题

　　　　（2）装置问题

　　　　（3）布线问题

　　　　（4）0-1背包问题

　　　　（5）最大团问题

　　　　（6）旅行售货员问题

　　　　（7）电路板排列问题

　　　　（8）批处理作业调度问题

1、分支限界法与回溯法的关系：

　　分支限界法类似于回溯法，也是在问题的解空间树上搜索问题解的算法。

　　分支限界法与回溯法的区别：

　　　　1、求解目标不同：回溯法的求解目标是找出解空间中满足约束条件的所有解；而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到　　极大或极小的解，即在某种意义下的最优解。

　　　　2、对解空间的搜索方式不同：回溯法以深度优先的方式搜索解空间；而分支限界法以广度优先或以最小耗费优先的方式搜索解空间。

　　　　主要区别就在于它们对当前扩展结点所采用的扩展方式不同，在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子　　结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入到活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找　　到所需的解或者活结点表为空时为止。

2、分支限界法的搜索策略：

　　在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一个扩展结点，加入搜索的进程，在每一个活结点处，计算一个函数值（限界），并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，比便尽快地找出一个最优解。

　　注：可以用剪枝函数加速搜索，该函数给出每一个可行结点相应的子树可能获得的最大价值的上界。如果这个上界不会比当前最优值更大，则说明相应的子树中不含问题的最优解，因而可以剪去。另一方面，也可以将上界函数确定的每个结点的上界作为优先级，以该优先级的非增序抽取当前扩展结点。这种策略有时可以更迅速地找到最优解。

　　基本思想：

　　　　分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。在搜索问题的解空间树时，分　　支限界法与回溯法的主要区别在于它们对当前扩展结点所采用的扩展方式不同。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结　　　点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入到活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过　　程一直持续到找到所需的解或活结点表为空时为止。

3、两种不同的分支限界法（算法框架）——从活结点表中选择下一个扩展结点的不同方式所导致

　　（1）队列式(FIFO)分支限界法：将活结点表组织成一个队列，并按照队列先进先出的原则选取下一个结点作为当前扩展结点。

　　（2）优先队列式分支限界法：将活结点表组织成一个优先队列，并按照优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。

 4、应用范例：

0-1背包问题：