算法设计与分析第六章分枝限界法.ppt

算法设计与分析第六章分枝限界法 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望第六章 分支限界法学习要点理解分支限界法的剪枝搜索策略。掌握分支限界法的算法框架1.队列式(FIFO)分支限界法2.优先队列式分支限界法 通过应用范例学习分支限界法的设计策略。1.单源最短路径问题;2.装载问题；3.布线问题;4.0-1背包问题；5.最大团问题；6.旅行售货员问题;7.电路板排列问题;8.批处理作业调度问题2 2引言分支限界法类似于回溯法，也是一种在问题的解空间树T中搜索问题解的算法。分支限界法与回溯法的求解目标不同：回溯法是找出满足约束条件的所有解分支限界法是找出满足条件的一个解，或某种意义下的最优解搜索方式不同回溯法：深度优先分支限界法：广度优先或最小耗费优先3 36.1 分支限界法的基本思想一、基本思想二、常见的两种分支限界法三、0-1背包问题四、旅行售货员问题4 4一、基本思想分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。直到找到所需的解或活结点表为空时为止。先进先出5 5二、常见的两种两种分支限界法从活结点表中选择下一扩展结点的不同方式导致不同的分支限界法：队列式(FIFO)分支限界法：按照队列先进先出先进先出原则选取下一个节点为扩展节点。优先队列优先队列优先队列优先队列分支限界法：按照优先级选取优先级优先级优先级优先级最高的节点节点节点节点成为当前扩展节点扩展节点。最大优先队列：使用最大堆，体现最大效益优先最小优先队列：使用最小堆，体现最小费用优先6 6三、0-1背包问题考虑如下0-1背包问题的实例：n=3,c=30,w=16,15,15,p=45,25,25队列式分支限界法：A B,C=B,CB,C D,E=EC,E F,G=F,GE,F,G J,K=K(45)1,0,0F,G L,M=L(50)0,1,1 M(25)G N,0=N(25),O(0)不搜索一不可行结点为根的子树优先队列式分支限界法：A B,C=B(45),C(0)B,C D,E=E(45)E,C J,K=K(45)1,0,0C F,G=F(25),G(0)F,G L,M=L(50),0,1,1 M(25)G N,O=N(25),O(0)可用剪枝函数加速搜索ABCDEFGHIJKLMNO107 7四、旅行售货员问题队列式分支限界法：A B,C,DB,C,D E,FC,D,E,F G,HD,E,F,G,H I,JE,F,G,H,I,J K(59)1,2,3,4F,G,H,I,J L(66)G,H,I,J M(25)1,3,2,4H,I,J 1-3-4(26)I,J O(25)J P(59)优先队列式分支限界法：A B,C,D=B(30),C(6),D(4)D,C,B I,J=I(14),J(24)C,I,J,B G,H=G(11),H(26)G,I,J,B,H M=M(25)1,3,2,4I,J,B,H O=O(25)J,B,H P=P(59)B,H B,H 限界掉1234643020510ABCDEFGHIJKLMNOP8 8复习第一章：算法复杂性分析 第二章：递归、分治法的概念，不考最近点对与循环赛日程表第三章：动态规划的概念、与分治法异同、不考动态规划加速原理、不考凸多边形三角剖分、不考图像压缩。第四章：概念、不考贪心算法的理论基础、Huffman是杨老师讲的为准。第五章：概念、二种模式、01背包、装载、皇后、TSP问题第六章：概念、二种模式、01背包、TSP问题、8个大题：问答、证明、计算(按要求描述计算过程)9 9平时成绩第一：作业分数第二：小班讨论分数 第三：上机实验分数 (杨老师届时公布在课程中心)第四：考勤分数1010