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

1
第6章分支限界法
2
学习要点
理解分支限界法的剪枝搜索策略。
掌握分支限界法的算法框架
(1)队列式(FIFO)分支限界法
(2)优先队列式分支限界法
通过应用范例学习分支限界法的设计策略。
(1)单源最短路径问题
(2)装载问题
(3)布线问题
(4)0-1背包问题
(5)最大团问题
(6)旅行售货员问题
(7)电路板排列问题
(8)批处理作业调度问题
3
分支限界法的基本思想
基本思想
分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树,裁剪那些不能得到最优解的子树以提高搜索效率。
搜索策略
在扩展结点处,先生成其所有的儿子结点(分支),然后再从当前的活结点表中选择下一个扩展结点。
为了有效地选择下一个扩展结点,以加速搜索的进程,在每一活结点处,根据限界函数估算目标函数的可能取值(优先值),并根据这些已计算出的函数值,从当前活结点表中选择一个最有利的结点(使目标函数取得极值(极大/极小)的结点)作为扩展结点,优先进行广度优先搜索,使搜索朝着解空间树上有最优解的分支推进, 不断调整搜索方向,以便尽快地找出一个最优解。
4
特点
限界函数常基于问题的目标函数,适用于求解最优化问题。
在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中。
此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。
5
分支限界法与回溯法的区别
(1)求解目标不同
回溯法的求解目标是找出解空间树中满足约束条件的所有解
分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解。
(2)搜索方式不同
回溯法以深度优先的方式搜索解空间树
分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树
(3)对扩展结点的扩展方式不同
分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。
(4)存储空间的要求不同
分支限界法的存储空间比回溯法大得多,因此当内存容量有限时,回溯法成功的可能性更大。
6
求解步骤
①定义解空间(对解编码)
②确定解空间的树结构
③按BFS等方式搜索


,删除不可能导出最优解的结点//限界策略
(队列)中
//分支策略

7
常见的两种分支限界法
(1)队列式(FIFO)分支限界法
按队列先进先出(FIFO)原则选取下一个结点为扩展结点。
从活结点表中取出结点的顺序与加入结点的顺序相同,因此活结点表的性质与队列相同。
(2)优先队列式分支限界法
按优先队列中规定的优先级,选取优先级最高的结点成为当前扩展结点。
每个结点都有一个对应的耗费或收益,以此决定结点的优先级。
如果查找一个具有最小耗费的解,则活结点可用小根堆来建立,下一个扩展结点就是具有最小耗费的活结点。
如果搜索一个具有最大收益的解,则可用大根堆来构造活结点表,下一个扩展结点是具有最大收益的活结点。
8
问题的解空间
与回溯法相同,一般用解空间树(Solution Space Tree,也称状态空间树)的方式组织。
例:0-1背包问题
当n=3时
9
对解空间树的动态搜索过程
确定一个合理的限界函数,并根据限界函数确定目标函数的界[down,up]。
按照广度优先策略遍历问题的解空间树,在分支结点上,依次搜索该结点的所有孩子结点,分别估算这些孩子结点的目标函数的可能取值,如果某孩子结点的目标函数可能取得的值超出目标函数的界,则将其丢弃,因为从这个结点生成的解不会比目前已经得到的解更好;否则,将其加入待处理结点表(以下简称活结点表)中。
依次从活结点表中选取使目标函数的值取得极值的结点成为当前扩展结点,重复上述过程,直到找到最优解。
10
随着这个遍历过程的不断深入,活结点表中所估算的目标函数的界越来越接近问题的最优解。
当搜索到一个叶子结点时,如果该结点的目标函数值是活结点表中的极值(对于最小化问题,是极小值;对于最大化问题,是极大值),则该叶子结点对应的解就是问题的最优解;否则,根据这个叶子结点调整目标函数的界(对最小化问题,调整上界;对于最大化问题,调整下界),依次考察活结点表中的结点,将超出目标函数界的结点丢弃,然后从活结点表中选取使目标函数取得极值的结点继续进行扩展。