第6章：分支限界法 (Branch and Bound Method)
第6章：分支限界法 （Branch and Bound Method）
知识要点 理解分支限界法的剪枝搜索策略 掌握分支限界法的算法框架 R 分支限界法的典型例子 Φ单源最短路径问题；装载问题 Φ布线问题；0/1背包问题 Φ最大团问题；旅行商问题 Φ电路板排列问题；批处理作业调度问题
知识要点 理解分支限界法的剪枝搜索策略 掌握分支限界法的算法框架 分支限界法的典型例子 单源最短路径问题；装载问题 布线问题；0/1背包问题 最大团问题；旅行商问题 电路板排列问题；批处理作业调度问题
6.1 分支限界法的基本概念
6.1 分支限界法的基本概念
分支限界法 @R 分支限界法与回溯法的类似之处 基本思路：在问题的解空间树上搜索问题的解 RR 分支限界法与回溯法的区别 Φ求解目标不同 回溯法的求解目标是找出解空间树中满足约束条件的所有解 分支限界法的求解目标则是尽快找出满足约束条件的一个解， 或是在满足约束条件的解中找出在某种意义下的最优解 通常用于解决离散值的最优化问题 搜索方式不同 回溯法以深度优先的方式（遍历结点）搜索解空间树 分支限界法以广度优先或最小耗费优先的方式搜索解空间树
分支限界法 分支限界法与回溯法的类似之处 基本思路：在问题的解空间树上搜索问题的解 分支限界法与回溯法的区别 求解目标不同 • 回溯法的求解目标是找出解空间树中满足约束条件的所有解 • 分支限界法的求解目标则是尽快找出满足约束条件的一个解， 或是在满足约束条件的解中找出在某种意义下的最优解 • 通常用于解决离散值的最优化问题 搜索方式不同 • 回溯法以深度优先的方式（遍历结点）搜索解空间树 • 分支限界法以广度优先或最小耗费优先的方式搜索解空间树
分支限界法 @R 分支限界法与回溯法的区别 Φ对扩展结点的扩展方式不同 分支限界法中，每一个活结点只有一次机会成为扩展结点 活结点一旦成为扩展结点，就一次性产生其所有儿子结点 Φ存储空间的要求不同 分支限界法的存储空间比回溯法大得多 因此当内存容量有限时，回溯法成功的可能性更大 Φ二者区别小结 ,回溯法空间效率高；分支限界法往往更“快” 限界函数常基于问题的目标函数，适用于求解最优化问题
分支限界法 分支限界法与回溯法的区别 对扩展结点的扩展方式不同 • 分支限界法中，每一个活结点只有一次机会成为扩展结点 • 活结点一旦成为扩展结点，就一次性产生其所有儿子结点 存储空间的要求不同 • 分支限界法的存储空间比回溯法大得多 • 因此当内存容量有限时，回溯法成功的可能性更大 二者区别小结 • 回溯法空间效率高；分支限界法往往更“快” • 限界函数常基于问题的目标函数，适用于求解最优化问题