白本程子太￥ ANDONG UNIVERSITY OF TECINOLOO 计算机算法设计与分析 Design and Analysis of Computer Algorithms 第六章分支限界法 Branch-and Bound Algorithm 王红霞 理学院
计算机算法设计与分析 Design and Analysis of Computer Algorithms 第六章 分支限界法 Branch-and-Bound Algorithm 王红霞 理学院
归东理子太军 学习要点 SHANDONG UNIVERSITY OF TECHNOLOGY 华器会空空合安会空会的会 >理解分支限界法的剪枝搜索策略。 >掌握分支限界法的算法框架 1.队列式(FFO)分支限界法 2.优先队列式分支限界法 ♪ 通过应用范例学习分支限界法的设计策略。 1.单源最短路径问题 2.装载问题； 3.布线问题 4.0-1背包问题； 5.最大团问题； 6.旅行售货员问题 7.电路板排列问题 8. 批处理作业调度问题 2025年4月3日 2
2025年4月3日 2 ➢ 理解分支限界法的剪枝搜索策略。 ➢ 掌握分支限界法的算法框架 1. 队列式(FIFO)分支限界法 2. 优先队列式分支限界法 ➢ 通过应用范例学习分支限界法的设计策略。 1. 单源最短路径问题 2. 装载问题； 3. 布线问题 4. 0-1背包问题； 5. 最大团问题； 6. 旅行售货员问题 7. 电路板排列问题 8. 批处理作业调度问题 学习要点
归东程子太军 提纲 SHANDONG UNIVERSITY OF TECINOLOGY 一、分支限界法的基本思想 二、单源最短路径问题 三、装载问题 四、0-1背包问题 五、最大团问题 六、旅行售货员问题 2025年4月3日 3
2025年4月3日 3 提纲 一、分支限界法的基本思想 二、单源最短路径问题 三、装载问题 四、0-1背包问题 五、最大团问题 六、旅行售货员问题
归东露子太军 提纲 SHANDONG UNIVERSITY OF TECHNOLOGY 一、分支限界法的基本思想 二、单源最短路径问题 三、装载问题 四、0-1背包问题 五、最大团问题 六、旅行售货员问题 2025年4月3日
2025年4月3日 4 提纲 一、分支限界法的基本思想 二、单源最短路径问题 三、装载问题 四、0-1背包问题 五、最大团问题 六、旅行售货员问题
白东程子太军 HANDONG UNIVERSITY OF TECHNOLOOY 华容约深完是红器分深是容 分支限界法同回溯法类似，它也是在解空间中搜索问题的可 行解或最优解，但搜索的方式不同。回溯法采用深度优先的 方式，朝纵深方向搜索，直至达到问题的一个可行解，或经 判断沿此路径不会达到问题的可行解或最优解时，停止向前 搜索，并沿原路返回到该路径上最后一个还可扩展的结点。 从该结点出发朝新的方向纵深搜索。分支定界法则采用宽度 优先的方式搜索解空间树，它将活结点存放在一个特殊的表 中。其策略是：在扩展结点处，先生成其所有的儿子结点， 将那些导致不可行解或导致非最优解的儿子舍弃，其余儿子 加入活结点表中。此后，从活结点表中取出一个结点作为当 前扩展结点。并重复上述结点扩展过程。所以，分支限界法 与回溯法的本质区别在于搜索方式的不同。回溯法更适于处 理那些求所有可行解的问题，而分支限界法更适于处理那些 只确定一个可行解，特别是最优化问题。 2025年4月3日
2025年4月3日 5 分支限界法同回溯法类似，它也是在解空间中搜索问题的可 行解或最优解，但搜索的方式不同。回溯法采用深度优先的 方式，朝纵深方向搜索，直至达到问题的一个可行解，或经 判断沿此路径不会达到问题的可行解或最优解时，停止向前 搜索，并沿原路返回到该路径上最后一个还可扩展的结点。 从该结点出发朝新的方向纵深搜索。分支定界法则采用宽度 优先的方式搜索解空间树，它将活结点存放在一个特殊的表 中。其策略是：在扩展结点处，先生成其所有的儿子结点, 将那些导致不可行解或导致非最优解的儿子舍弃，其余儿子 加入活结点表中。此后，从活结点表中取出一个结点作为当 前扩展结点。并重复上述结点扩展过程。所以，分支限界法 与回溯法的本质区别在于搜索方式的不同。回溯法更适于处 理那些求所有可行解的问题，而分支限界法更适于处理那些 只确定一个可行解，特别是最优化问题
白本程子太军 HANDONG UNIVERSITY OF TECINOLOGY 在算法空间上比较回溯法和分支限界法 (1)回溯法占用内存： O(解空间的最大路径长度) >对子集问题，需要0()的内存空间 >对排列问题，需要0()的内存空间 (2)分支限界法占用内存： (解空间大小) >对子集问题，需要0(2)的内存空间 >对排列问题，需要0()的内存空间 6
6 在算法空间上比较回溯法和分支限界法 （1）回溯法占用内存： O(解空间的最大路径长度) ➢对子集问题，需要O(n)的内存空间 ➢对排列问题，需要O(n)的内存空间 （2）分支限界法占用内存： O(解空间大小) ➢对子集问题，需要O(2n )的内存空间 ➢对排列问题，需要O(n!)的内存空间
归本程子末军 1.1分支限界法与回溯法的比较 HANDONG UNIVERSITY OF TECINOLOGY 会是33☆ ●分支限界法类似于回溯法，也是一种在问题的 解空间树T中搜索问题解的算法。 ●空间消耗不同 ●求解目标（适用范围）不同： ■回溯法适用于找出满足约束条件的所有解的情况； ■分支限界法发誓找出满足条件的一个解，或某种 意义下的最优解。 ●搜索方式不同 ■回溯法：深度优先 ■分支限界法：广度优先 2025年4月3日
2025年4月3日 7 1.1 分支限界法与回溯法的比较 ⚫ 分支限界法类似于回溯法，也是一种在问题的 解空间树T中搜索问题解的算法。 ⚫ 空间消耗不同 ⚫ 求解目标（适用范围）不同： ◼回溯法适用于找出满足约束条件的所有解的情况； ◼分支限界法发誓找出满足条件的一个解，或某种 意义下的最优解。 ⚫ 搜索方式不同 ◼回溯法：深度优先 ◼分支限界法：广度优先
归东理子太军 12分支限界法的基本思想 SHANDONG UNIVERSITY OF TECHNOLOGY 会会是会会8会 ●分支限界法常以广度优先或以最小耗费（最大 效益)优先的方式搜索问题的解空间树。 ●在分支限界法中，每一个活结点只有一次机会 成为扩展结点。活结点一旦成为扩展结点，就 一次性产生其所有儿子结点。在这些儿子结，点 中，导致不可行解或导致非最优解的儿子结点 被舍弃，其余儿子结，点被加入活结，点表中。 ●此后，从活结点表中取下一结点成为当前扩展 结，点，并重复上述结，点扩展过程。这个过程一 直持续到找到所需的解或活结，点表为空时为止。 2025年4月3日
2025年4月3日 8 1.2 分支限界法的基本思想 ⚫ 分支限界法常以广度优先或以最小耗费（最大 效益）优先的方式搜索问题的解空间树。 ⚫ 在分支限界法中，每一个活结点只有一次机会 成为扩展结点。活结点一旦成为扩展结点，就 一次性产生其所有儿子结点。在这些儿子结点 中，导致不可行解或导致非最优解的儿子结点 被舍弃，其余儿子结点被加入活结点表中。 ⚫ 此后，从活结点表中取下一结点成为当前扩展 结点，并重复上述结点扩展过程。这个过程一 直持续到找到所需的解或活结点表为空时为止
白东程子太军 13常见的两种分支限界法 HANDONG UNIVERSITY OF TECINOLOGY 3会会品分空3品会品 ● 从活结，点表中选择下一扩展结点的不同方 式导致不同的分支限界法： ■队列式FFO)分支限界法：将活结，点表组织成一 个队列，按照队列先进先出(FFO)原则选取下 一个节点为扩展节，点。 ■优先队列式分支限界法：将活结点表组织成一个 优先队列，按照优先队列中规定的优先级选取优 先级最高的节点成为当前扩展节，点。 ◆最大优先队列：使用最大堆，体现最大效益优先 ◆最小优先队列：使用最小堆，体现最小费用优先 2025年4月3日 9
2025年4月3日 9 1.3 常见的两种分支限界法 ⚫从活结点表中选择下一扩展结点的不同方 式导致不同的分支限界法： ◼队列式(FIFO)分支限界法：将活结点表组织成一 个队列，按照队列先进先出（FIFO）原则选取下 一个节点为扩展节点。 ◼优先队列式分支限界法：将活结点表组织成一个 优先队列，按照优先队列中规定的优先级选取优 先级最高的节点成为当前扩展节点。 ◆最大优先队列：使用最大堆，体现最大效益优先 ◆最小优先队列：使用最小堆，体现最小费用优先
归本程子太军 SHANDONG UNIVERSITY OF TECINOLOGY 华器会空空合安会空会的会 队列式分支限界法的搜索解空间树的方式类 似于解空间树的宽度优先搜索，不同的是队列式 分支限界法不搜索以不可行结点（已经被判定不 能导致可行解或不能导致最优解的结点)为根的 子树。这是因为，按照规则，这样的结点未被列 入活结点表。 2025年4月3日 10
2025年4月3日 10 队列式分支限界法的搜索解空间树的方式类 似于解空间树的宽度优先搜索，不同的是队列式 分支限界法不搜索以不可行结点（已经被判定不 能导致可行解或不能导致最优解的结点）为根的 子树。这是因为，按照规则，这样的结点未被列 入活结点表