算法设计与分析_第6章_分支限界法.pdfVIP

算法设计与分析 第6章 分支限界法 1 学习要点 理解分支限界法的剪枝搜索策略 掌握分支限界法的算法框架 队列式(FIFO)分支限界法 优先队列式分支限界法 通过应用范例学习分支限界法的设计策略 单源最短路径问题 装载问题； 0-1背包问题； 最大团问题； 旅行售货员问题 批处理作业调度问题 2 分支限界法的基本思想 分支限界法常以广度优先或以最小耗费 （最大 效益）优先的方式搜索问题的解空间树。 在分支限界法中，每一个活结点只有一次机会 成为扩展结点。 活结点一旦成为扩展结点，就一次性产生其所有儿 子结点。 在这些儿子结点中，导致不可行解或导致非最优解 的儿子结点被舍弃，其余儿子结点被加入活结点表 中。 此后，从活结点表中取下一结点(最有利的)成为当 前扩展结点，并重复上述结点扩展过程。这个过程 一直持续到找到所需的解或活结点表为空时为止。 3 分支限界法的基本思想 分支限界方法找最优解的效率比回溯法 高。 原因在于 采用了最小代价估值函数指导搜索，在活节 点表中，选择有最小代价估值的节点作为扩 展节点。即总是向最有可能获得最优解的子 树上扩展。 并且采用限界函数U杀死活节点表中不可能 成为最优解的节点，提高算法的效率。 4 分支限界法的基本思想 比回溯法多的两个条件 对于一棵解空间树上的每一个节点所代表的部分解, 要计算出通过这个部分解繁衍出的任何解在目标函 数上的最佳值边界 目前求得的最佳解的值 算法会为每一节点x计算一个界,任何可能在以x 为根的子树中生成的结点所给出的解,其值都不 可能超出这个界. 如果边界值不能超越最佳解,这个节点就是一个 没有希望的节点. 这就是分支限界法的主要思 想 5 分支限界法的基本思想 根据从活结点表中获取下 常见的两种分支限界法 一扩展结点的不同方式 （1 ）队列式分支限界法 按照队列先进先出（FIFO ）或者后进先出（LIFO ） 原则选取下一个结点为扩展结点。 不足:对结点的选择规则相当死板，具有一定的 “盲 目”性。这种选择规则不利于快速检索到一个能够到达 答案的结点。 （2 ）优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的结点 成为当前扩展结点。常用方法是LC(Least Cost)方法。 对活结点使用一个“有智能”的排序函数C()来选取下一 个结点，往往可以加快获取答案的速度。 最大优先队列：使用最大堆，体现最大效益优先 最小优先队列：使用最小堆，体现最小费用优先 6 分支限界法的基本思想 实例——8-拼块游戏问题 输入: 具有8 个编号小方块的魔方 输出: 移动系列, 经过这些移动, 魔方达到目标状态 2 8 3