2015分支限界法经典案例算法分析.ppt

第6章 分支限界法 学习要点 理解分支限界法的剪枝搜索策略。 掌握分支限界法的算法框架 （1）队列式(FIFO)分支限界法 （2）优先队列式分支限界法 通过应用范例学习分支限界法的设计策略。 （1）单源最短路径问题； （2）装载问题； （3）布线问题； （4）0-1背包问题； （5）最大团问题； （6）旅行售货员问题； 6.1 分支限界法的基本思想 6.1 分支限界法的基本思想 6.1 分支限界法的基本思想 6.2 单源最短路径问题 6.2 单源最短路径问题 6.2 单源最短路径问题 6.2 单源最短路径问题 6.2 单源最短路径问题 6.3 装载问题 6.3 装载问题 6.3 装载问题 6.3 装载问题 6.3 装载问题 6.3 装载问题 6.3 装载问题 6.3 装载问题 6.3 装载问题 6.4 布线问题 6.4 布线问题 6.4 布线问题 6.5 0-1背包问题 6.5 0-1背包问题 6.5 0-1背包问题 6.6 最大团问题 问题描述 给定无向图G=(V，E)。如果U?V，且对任意u，v?U有(u，v)?E，则称U是G的完全子图。G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。 下图G中，子集{1，2}是G的大小为2的完全子图。这个完全子图不是团，因为它被G的更大的完全子图{1，2，5}包含。{1，2，5}是G的最大团。{1，4，5}和{2，3，5}也是G的最大团。 6.6 最大团问题 2. 上界函数 用变量cliqueSize表示与该结点相应的团的顶点数；level表示结点在子集空间树中所处的层次；用cliqueSize +n-level+1作为顶点数上界upperSize的值。 在此优先队列式分支限界法中，upperSize实际上也是优先队列中元素的优先级。算法总是从活结点优先队列中抽取具有最大upperSize值的元素作为下一个扩展元素。 6.6 最大团问题 3. 算法思想 子集树的根结点是初始扩展结点，对于这个特殊的扩展结点，其cliqueSize的值为0。 算法在扩展内部结点时，首先考察其左儿子结点。在左儿子结点处，将顶点i加入到当前团中，并检查该顶点与当前团中其他顶点之间是否有边相连。当顶点i与当前团中所有顶点之间都有边相连，则相应的左儿子结点是可行结点，将它加入到子集树中并插入活结点优先队列，否则就不是可行结点。 接着继续考察当前扩展结点的右儿子结点。当upperSizebestn时，右子树中可能含有最优解，此时将右儿子结点加入到子集树中并插入到活结点优先队列中。 6.6 最大团问题 算法的while循环的终止条件是遇到子集树中的一个叶结点(即n+1层结点)成为当前扩展结点。 对于子集树中的叶结点，有upperSize＝cliqueSize。此时活结点优先队列中剩余结点的upperSize值均不超过当前扩展结点的upperSize值，从而进一步搜索不可能得到更大的团，此时算法已找到一个最优解。 6.7 旅行售货员问题 6.7 旅行售货员问题 6.7 旅行售货员问题 6.7 旅行售货员问题 练习 习题 6-1 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 1 4 2 3 6 4 5 20 10 30 旅行售货员问题就是在图中找到一个权最小的周游路线 解空间：排列树 回溯法剪枝策略： 当前路径的权重＋下一个路径的权重当前的最小权重，则搜索该路径 6.7 旅行售货员问题 4 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 1. 问题描述 某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。 路线是一个带权图。图中各边的费用（权）为正数。图的一条周游路线是包括V中的每个顶点