分支限界法 @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也是盲目的（虽有目标函数，也只有找到一 个可行解后才有意义）