第八章分支限界法 §1算法基本思想 本章叙述中为了区别图中的顶点和解空间树中的顶点,凡是在解 空间树中出线队顶点一律称为结点。 分支限界法同回溯法类似,它也是在解空间中搜索问题的可行解 或最优解,但搜索的方式不同。回溯法采用深度优先的方式,朝纵深 方向搜索,直至达到问题的一个可行解,或经判断沿此路径不会达到 问题的可行解或最优解时,停止向前搜索,并沿原路返回到该路径上 最后一个还可扩展的结点。从该结点出发朝新的方向纵深搜索。分支 定界法则采用宽度优先的方式搜索解空间树,它将活结点存放在一个 特殊的表中。其策略是:在扩展结点处,先生成其所有的儿子结点, 将那些导致不可行解或导致非最优解的儿子舍弃,其余儿子加入活结 点表中。此后,从活结点表中取出一个结点作为当前扩展结点。并重 复上述结点扩展过程。所以,分支限界法与回溯法的本质区别在于搜 索方式的不同。回溯法更适于处理那些求所有可行解的问题,而分支 限界法更适于处理那些只确定一个可行解,特别是最优化问题。 从活结点表中选择下一扩展结点的不同方式导致不同的分支限 界法。最常见的有以下两种方式: 1).队列式(FIF0)分支限界法:将活结点表组织成一个队列, 并按队列的先进先出原则选取下一个结点作为当前扩展结点。 2).优先队列式分支限界法:将活结点表组织成一个优先队列, 并按优先队列给结点规定的优先级选取优先级最高的下一个结点作第八章 分支限界法 §1 算法基本思想 本章叙述中为了区别图中的顶点和解空间树中的顶点，凡是在解 空间树中出线队顶点一律称为结点。 分支限界法同回溯法类似，它也是在解空间中搜索问题的可行解 或最优解，但搜索的方式不同。回溯法采用深度优先的方式，朝纵深 方向搜索，直至达到问题的一个可行解，或经判断沿此路径不会达到 问题的可行解或最优解时，停止向前搜索，并沿原路返回到该路径上 最后一个还可扩展的结点。从该结点出发朝新的方向纵深搜索。分支 定界法则采用宽度优先的方式搜索解空间树，它将活结点存放在一个 特殊的表中。其策略是：在扩展结点处，先生成其所有的儿子结点, 将那些导致不可行解或导致非最优解的儿子舍弃，其余儿子加入活结 点表中。此后，从活结点表中取出一个结点作为当前扩展结点。并重 复上述结点扩展过程。所以，分支限界法与回溯法的本质区别在于搜 索方式的不同。回溯法更适于处理那些求所有可行解的问题，而分支 限界法更适于处理那些只确定一个可行解，特别是最优化问题。 从活结点表中选择下一扩展结点的不同方式导致不同的分支限 界法。最常见的有以下两种方式： 1).队列式（FIFO）分支限界法：将活结点表组织成一个队列， 并按队列的先进先出原则选取下一个结点作为当前扩展结点。 2).优先队列式分支限界法： 将活结点表组织成一个优先队列， 并按优先队列给结点规定的优先级选取优先级最高的下一个结点作