分支限界法ppt.pptVIP

第6章 分支限界法(Branch and Bound)6.1 分支限界法的基本思想 用于求解最优化问题 1、分支限界法与回溯法的不同 分支限界法与回溯法类似，也是在问题的解空间上有哪些信誉好的足球投注网站问题解的算法。其不同点如下： 1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 2）有哪些信誉好的足球投注网站方式的不同：回溯法以深度优先的方式有哪些信誉好的足球投注网站解空间树，而分支限界法则以广度优先或以最小耗费优先的方式有哪些信誉好的足球投注网站解空间树。 2. 分支限界法基本思想 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式有哪些信誉好的足球投注网站问题的解空间树。 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 由此可见，两种算法的最主要区别在于它们对当前扩展节点所采用的扩展方式不同。在分支限界法中，每个或结点只有一次机会成为扩展节点。 3. 常见的两种分支限界法 从活结点表中选择下一扩展结点的不同方式导致不同的分支界限法。最常见的有以下两种方式： （1）队列式(FIFO)分支限界法 按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 （2）优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 优先队列中规定的节点优先级通常用一个与该节点相关的数值p来表示。结点优先级的高低与p值的大小有关。最大优先队列规定p值较大的结点优先级高。在算法实现是通常采用最大堆来实现最大优先队列，用最大堆的Deletemax运算抽取堆中下一结点成为当前扩展节点，体现最大利益优先的原则。类似的，最小优先队列用最小堆实现。 6.3 装载问题 1. 问题描述 这个问题是一个子集选择问题，它的解空间被组织成一个子集树。问题描述及界限函数见5.2节。 利用分支限界法设计算法MaxLoading实施对解空间的分支限界有哪些信誉好的足球投注网站。链表队列Q用于保存活节点，它的值记录着各活节点对应的权值。队列还记录了权值- 1，以标识每一层的活节点的结尾。 函数EnQueue用于增加节点（即把节点对应的权值加入活节点队列） 函数EnQueue用于增加节点（即把节点对应的权值加入活节点队列），该函数首先检验i（当前E-节点在解空间树中的层）是否等于n，如果相等，则已到达了叶节点。叶节点不被加入队列中，因为它们不被展开。有哪些信誉好的足球投注网站中所到达的每个叶节点都对应着一个可行的解，而每个解都会与目前的最优解来比较，以确定最优解。如果i＜n，则节点i 就会被加入队列中 MaxLoading函数首先初始化i = 1（因为当前E-节点是根节点），bestw=0（目前最优解的对应值），此时，活节点队列为空。下一步， 将同层结点尾部标志-1加入队列，表示此时正处在第一层的末尾。Ew存储当前扩展结点所相应的重量。 3. 算法的改进 节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。设bestw是当前最优解；ew是当前扩展结点所相应的重量；r是剩余集装箱的重量。则当ew+r?bestw时，可将其右子树剪去，因为此时若要船装最多集装箱，就应该把此箱装上船。 另外，为了确保右子树成功剪枝，应该在算法每一次进入左子树的时候更新bestw的值。 4. 构造最优解 为了在算法结束后能方便地构造出与最优值相应的最优解，算法必须存储相应子集树中从活结点到根结点的路径。为此目的，可在每个结点处设置指向其父结点的指针，并设置左、右儿子标志。算法实现见P199 private static class QNode { QNode parent; // 父结点 boolean leftChild; // 左儿子标志 int weight; // 结点所相应的载重量 算法EnQueue做如下修改： templateclass T void EnQueue(QueueQNodeT* Q, T wt, int i, int n, T bestw, QNodeT *E,QNodeT *bestE, int bestx[], bool ch) { // 如果不是叶节点，则向队列Q中添加一个i 层、重量为wt的活节点 // 新节点是E的一个孩子。当且仅当新节点是左孩子时，ch为true。 // 若是叶子，则c h取值为b e s t