分支界限法分析.ppt

第6章分支限界法
广州大学华软软件学院
第1页
算法分析与设计
学****要点
·理解分支限界法的剪枝搜索策略。
·掌握分支限界法的算法框架
·(1)队列式(FFO)分支限界法
(2)优先队列式分支限界法
广州大学华软软件学院
第2页
算法分析与设计
学****要点
通过应用范例学****分支限界法的设计策略。
(1)单源最短路径问题
(2)装载问题
(3)布线问题
(4)0-1背包问题;
·(5)最大团问题;
(6)旅行售货员问题
(7)电路板排列问题
·(8)批处理作业调度问题
广州大学华软软件学院
第3页
算法分析与设计
61分支限界法的基本思想
分支限界法与回溯法
(1)求解目标:回溯法的求解目标是找出解空间
树中满足约束条件的所有解,而分支限界法的求解
目标则是找出满足约束条件的一个解,或是在满足
约束条件的解中找出在某种意义下的最优解
(2)搜索方式的不同:回溯法以深度优先的方式
搜索解空间树,而分支限界法则以广度优先或以最
小耗费优先的方式搜索解空间树。
广州大学华软软件学院
第4页
算法分析与设计
61分支限界法的基本思想
分支限界法常以广度优先或以最小耗费(最大
效益)优先的方式搜索问题的解空间树。
在分支限界法中,每一个活结点只有一次机会成
为扩展结点。活结点一旦成为扩展结点,就一次性产
生其所有儿子结点。在这些儿子结点中,导致不可行
解或导致非最优解的儿子结点被舍弃,其余儿子结点
被加入活结点表中。
此后,从活结点表中取下一结点成为当前扩展
结点,并重复上述结点扩展过程。这个过程一直持
续到找到所需的解或活结点表为空时为止。
广州大学华软软件学院
第5页
算法分析与设计
61分支限界法的基本思想
常见的两种分支限界法
(1)队列式(FIFO)分支限界法
按照队列先进先出(FIFO)原则选取下
个节点为扩展节点。
(2)优先队列式分支限界法
按照优先队列中规定的优先级选取优先级
最高的节点成为当前扩展节点。
广州大学华软软件学院
第6页
算法分析与设计


下面以一个例子来说明单源最短路径问题:在
下图所给的有向图G中,每一边都有一个非负边权。
要求图G的从源顶点s到目标顶点t之间的最短路径。
f
广州大学华软软件学院
第7页
算法分析与设计


下图是用优先队列式分支限界法解有向图G的单
源最短路径问题产生的解空间树。其中,每一个结点
旁边的数字表示该结点所对应的当前路长。
4
4
○12
○6
g
705,
14
108
广州大学华软软件学院
第8页
算法分析与设计

解单源最短路径问题的优先队列式分支限界法用
极小堆来存储活结点表。其优先级是结点所对应的
当前路长。
算法从图G的源顶点s和空优先队列开始。结点s被扩
展后,它的儿子结点被依次插入堆中。此后,算法从堆
中取出具有最小当前路长的结点作为当前扩展结点,并
依次检查与当前扩展结点相邻的所有顶点。如果从当前
扩展结点到顶点有边可达,且从源出发,途经顶点i再
到顶点j所相应的路径的长度小于当前最优路径长度,
则将该顶点作为活结点插入到活结点优先队列中。这个
结点的扩展过程一直继续到活结点优先队列为空时为止。
广州大学华软软件学院
第9页
算法分析与设计

在算法扩展结点的过程中,一旦发现一个结点的
下界不小于当前找到的最短路长,则算法剪去以该结
点为根的子树。
在算法中,利用结点间的控制关系进行剪枝。从
源顶点s出发,2条不同路径到达图G的同一顶点。由于
两条路径的路长不同,因此可以将路长长的路径所对
应的树中的结点为根的子树剪去。
广州大学华软软件学院
第10页
算法分析与设