白本程子太军 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 队列式分支限界法的搜索解空间树的方式类 似于解空间树的宽度优先搜索，不同的是队列式 分支限界法不搜索以不可行结点（已经被判定不 能导致可行解或不能导致最优解的结点）为根的 子树。这是因为，按照规则，这样的结点未被列 入活结点表