算法分析与设计 分支限界法.ppt

第6章 分支限界法 6.1 分支限界法的基本思想 6.2 单源最短路径问题 6.3 0-1背包问题 本章主要知识点： 6.1 分支限界法的基本思想 （1）求解目标：回溯法的求解目标是找出解空间树中满 足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 1. 分支限界法与回溯法的不同 （2）有哪些信誉好的足球投注网站方式的不同：回溯法以深度优先的方式有哪些信誉好的足球投注网站解 空间树，而分支限界法则以广度优先或以最小耗费优 先的方式有哪些信誉好的足球投注网站解空间树。 6.1 分支限界法的基本思想 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式有哪些信誉好的足球投注网站问题的解空间树。 2. 分支限界法基本思想 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点， 并重复上述结点扩展过程。这个过程一直持续到找到 所需的解或活结点表为空时为止。 6.1 分支限界法的基本思想 3. 常见的两种分支限界法 （1）队列式(FIFO)分支限界法 按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 （2）优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 例如：考虑n=3时0-1背包问题，其中w=[16,15,15], p=[45,25,25],c=30。 6.1 分支限界法的基本思想 解空间 队列分支限界法 6.2 单源最短路径问题 从根结点A开始。初始时活结点队列为空，结点A是当前 的扩展结点。 结点A的2个儿子结点B和C均为可行结点，故将这两个儿子结点按从左到右的顺序加入到活结点队列，并舍弃当前的扩展结点A。 以先进先出的原则，下一个扩展结点是活结点队列的队首结点B。扩展结点B得到其儿子结点D和E。由于D是不可行结点，故被舍弃。E是可行结点，被加入活结点队列。 接下来，C成为当前的扩展结点，它的2个儿子结点F和G 均为可行结点，因此被加入到活结点队列中。 6.2 单源最短路径问题 扩展下一个结点E得到J和K。J是不可行结点，因而被舍弃。 K是可行叶结点，表示问题所求问题的一个可行解，其价值 为45. 当前的活结点队列的首结点F成为下一个扩展结点。它的2 个儿子结点L和M均为叶结点。L表示获得的价值为50的可行解， M表示获得价值为25的可行解。G是最后一个扩展结点，其儿子 结点N和O均为可行叶结点。最后活结点队列已空，算法终止。 算法有哪些信誉好的足球投注网站到的最优值为50. 从根结点A开始。用一个极大堆表示活结点表的优先队列。 6.2 单源最短路径问题 优先队列式分支限界法 初始堆为空，扩展结点A得到它的2个儿子结点B和C。这 2个结点均为可行结点，因此被加入到堆中，结点A被舍弃。 结点B获得的当前价值为40，而结点C的当前价值为0.由于 B的价值大于C的价值，所以B是堆中的最大元素，从而成为 下一个扩展结点。 扩展结点B得到结点D和E。D是不可行结点，因而被舍弃。E 是可行结点被加入到堆中，E的价值为40，成为当前堆中的 最大元素，从而成为下一个扩展结点。 扩展结点E得到2个叶结点J和K。J是不可行结点被舍弃。 K是一个可行叶结点，表示问题的一个可行解，其价值为45. 此时堆中仅剩下一个活结点C，它成为当前的扩展结点。它 的2个儿子结点F和G均为可行结点，因此被插入到当前堆中。 6.2 单源最短路径问题 结点F的价值为25，是堆中最大元素，成为下一个扩展结 点。F的2个儿子结点L和M均为叶结点。叶结点L相应于价值 为50的可行解。叶结点M相应于价值为25的可行解。叶结点 L所相应的解成为最优解。最后，结点G成为扩展结点，其儿子结点N和O均为叶结点，它们的价值分别为25和0. 接下来，存储活结点的堆已空，算法终止。算法有哪些信誉好的足球投注网站到的 最优值为50. 第6章 分支限界法 6.1 分支限界法的基本思想 6.2 单源最短路径问题 6.3 0-1背包问题 本章主要知识点： 6.1 分支限界法的基本思想 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式有哪些信誉好的足球投注网站问题的解空间树。 2. 分支限界法基本思想 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点， 并重复上述结点扩展过程。这个过程一直持续到找到 所需的解或活结点表为空时为止。 6.1 分支限界法