电子科技大学：《算法设计与分析 Algorithms Design and Analysis》课程教学资源（课件讲稿）第六章 分支限界法（Branch and Bound Method）

第6章：分支限界法 (Branch and Bound Method)

第6章：分支限界法 （Branch and Bound Method）

知识要点 理解分支限界法的剪枝搜索策略 掌握分支限界法的算法框架 R 分支限界法的典型例子 Φ单源最短路径问题；装载问题 Φ布线问题；0/1背包问题 Φ最大团问题；旅行商问题 Φ电路板排列问题；批处理作业调度问题

知识要点  理解分支限界法的剪枝搜索策略  掌握分支限界法的算法框架  分支限界法的典型例子  单源最短路径问题；装载问题  布线问题；0/1背包问题  最大团问题；旅行商问题  电路板排列问题；批处理作业调度问题

6.1 分支限界法的基本概念

6.1 分支限界法的基本概念

分支限界法 @R 分支限界法与回溯法的类似之处 基本思路：在问题的解空间树上搜索问题的解 RR 分支限界法与回溯法的区别 Φ求解目标不同 回溯法的求解目标是找出解空间树中满足约束条件的所有解 分支限界法的求解目标则是尽快找出满足约束条件的一个解， 或是在满足约束条件的解中找出在某种意义下的最优解 通常用于解决离散值的最优化问题 搜索方式不同 回溯法以深度优先的方式（遍历结点）搜索解空间树 分支限界法以广度优先或最小耗费优先的方式搜索解空间树

分支限界法  分支限界法与回溯法的类似之处  基本思路：在问题的解空间树上搜索问题的解  分支限界法与回溯法的区别  求解目标不同 • 回溯法的求解目标是找出解空间树中满足约束条件的所有解 • 分支限界法的求解目标则是尽快找出满足约束条件的一个解， 或是在满足约束条件的解中找出在某种意义下的最优解 • 通常用于解决离散值的最优化问题  搜索方式不同 • 回溯法以深度优先的方式（遍历结点）搜索解空间树 • 分支限界法以广度优先或最小耗费优先的方式搜索解空间树

分支限界法 @R 分支限界法与回溯法的区别 Φ对扩展结点的扩展方式不同 分支限界法中，每一个活结点只有一次机会成为扩展结点 活结点一旦成为扩展结点，就一次性产生其所有儿子结点 Φ存储空间的要求不同 分支限界法的存储空间比回溯法大得多 因此当内存容量有限时，回溯法成功的可能性更大 Φ二者区别小结 ,回溯法空间效率高；分支限界法往往更“快” 限界函数常基于问题的目标函数，适用于求解最优化问题

分支限界法  分支限界法与回溯法的区别  对扩展结点的扩展方式不同 • 分支限界法中，每一个活结点只有一次机会成为扩展结点 • 活结点一旦成为扩展结点，就一次性产生其所有儿子结点  存储空间的要求不同 • 分支限界法的存储空间比回溯法大得多 • 因此当内存容量有限时，回溯法成功的可能性更大  二者区别小结 • 回溯法空间效率高；分支限界法往往更“快” • 限界函数常基于问题的目标函数，适用于求解最优化问题

分支限界法 @R 分支限界法的基本思想：以广度优先或以最小耗费（最大效益） 优先的方式搜索问题的解空间树 Φ分支限界法中，每一个活结点只有一次机会成为扩展结点 Φ 活结点一旦成为扩展结点，就一次性产生其所有儿子结点 其中导致不可行解或导致非最优解的儿子结点被舍弃 其余儿子结点被加入活结点表PT中 含义：根据限界函数估算目标函数的可能取值 选取可能使目标函数取得极值的结点优先进行搜索 然后从活结点表中取下一结点成为当前扩展结点 重复上述结点扩展过程 直至到找到所需的解或活结点表为空时为止

分支限界法  分支限界法的基本思想：以广度优先或以最小耗费（最大效益） 优先的方式搜索问题的解空间树  分支限界法中，每一个活结点只有一次机会成为扩展结点  活结点一旦成为扩展结点，就一次性产生其所有儿子结点 • 其中导致不可行解或导致非最优解的儿子结点被舍弃 • 其余儿子结点被加入活结点表PT中 • 含义：根据限界函数估算目标函数的可能取值 • 选取可能使目标函数取得极值的结点优先进行搜索  然后从活结点表中取下一结点成为当前扩展结点  重复上述结点扩展过程 • 直至到找到所需的解或活结点表为空时为止

分支限界法的求解步骤 1. 定义解空间（对解编码） 2.确定解空间的树结构 3. 按BFS等方式搜索 ① 每个活结点仅有一次机会变成扩展结点 由扩展结点生成一步可达的新结点 3 在新结点中，删除不可能导出最优解的结点（限界策略） 将剩余的新结点加入活动表（队列）中 从活动表中选择结点再扩展（分支策略） 直至活动表为空

分支限界法的求解步骤 1. 定义解空间（对解编码） 2. 确定解空间的树结构 3. 按BFS等方式搜索 ① 每个活结点仅有一次机会变成扩展结点 ② 由扩展结点生成一步可达的新结点 ③ 在新结点中，删除不可能导出最优解的结点（限界策略） ④ 将剩余的新结点加入活动表（队列）中 ⑤ 从活动表中选择结点再扩展（分支策略） ⑥ 直至活动表为空

两种常见的分支限界法 3 队列式分支限界法 Φ按照队列先进先出(IFO)原则选取下一个结点为扩展结点 Φ从活结点表中取出结点的顺序与加入结点的顺序相同 因此活结点表的性质与队列相同 R 优先队列分支限界法（代价最小或效益最大） Φ每个结点都有一个对应的耗费或收益，以此决定结点的优先级 Φ从优先队列中选取优先级最高的结点成为当前扩展结点 如果查找一个具有最小耗费的解 则活结点表可用小顶堆来建立 下一个扩展结点就是具有最小耗费的活结点 如果希望搜索一个具有最大收益的解 则可用大顶堆来构造活结点表 下一个扩展结点是具有最大收益的活结点

两种常见的分支限界法  队列式分支限界法  按照队列先进先出（FIFO）原则选取下一个结点为扩展结点  从活结点表中取出结点的顺序与加入结点的顺序相同  因此活结点表的性质与队列相同  优先队列分支限界法（代价最小或效益最大）  每个结点都有一个对应的耗费或收益，以此决定结点的优先级  从优先队列中选取优先级最高的结点成为当前扩展结点 • 如果查找一个具有最小耗费的解 – 则活结点表可用小顶堆来建立 – 下一个扩展结点就是具有最小耗费的活结点 • 如果希望搜索一个具有最大收益的解 – 则可用大顶堆来构造活结点表 – 下一个扩展结点是具有最大收益的活结点

6.20-1背包问题

6.2 0-1背包问题

解空间树的动态搜索 R 回溯求解0/1背包问题，虽剪枝减少了搜索空间，但整个搜 索按深度优先机械进行，是盲目搜索（不可预测本结点以 下的结点进行的如何)。 CR 回溯求解TSP也是盲目的（虽有目标函数，也只有找到一 个可行解后才有意义)

解空间树的动态搜索  回溯求解0/1背包问题，虽剪枝减少了搜索空间，但整个搜 索按深度优先机械进行，是盲目搜索（不可预测本结点以 下的结点进行的如何）。  回溯求解TSP也是盲目的（虽有目标函数，也只有找到一 个可行解后才有意义）