分支限界法.ppt

主讲人: 吕敏
Email: { ******@ustc. }
Spring 2012,USTC
算法基础
2017/12/14
2
第十二讲分支限界法
内容提要:
理解分支限界法的剪枝搜索策略
掌握分支限界法的算法框架
(1)队列式(FIFO)分支限界法
(2)优先队列式分支限界法
通过应用范例学****分支限界法的设计策略
方法概述
与回溯法区别:
求解目标不同:
一般而言,回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分支限界法的求解目标则是尽快地找出满足约束条件的一个解;
搜索方法不同:
回溯法使用深度优先方法搜索,而分支限界一般用宽度优先或最佳优先方法来搜索;
对扩展结点的扩展方式不同:
分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点;
存储空间的要求不同
分支限界法的存储空间比回溯法大得多,因此当内存容量有限时,回溯法成功的可能性更大。
2017/12/14
3
方法概述
基本思想:
分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。对已处理的各结点根据限界函数估算目标函数的可能取值,从中选取是目标函数取得极大(小)值的结点优先进行广度优先搜索不断调整搜索方向,尽快找到解,裁剪那些不能得到最优解的子树以提高搜索效率。
特点:限界函数常基于问题的目标函数,适用于求解最优化问题。
2017/12/14
4
方法概述
搜索策略是:在扩展结点处,先生成其所有的儿子结点(分支),然后再从当前的活结点表中选择下一个扩展结点。
为了有效地选择下一个扩展结点,以加速搜索的进程,在每一活结点处,计算一个函数值(优先值),并根据这些已计算出的函数值,从当前活结点表中选择一个最有利的结点作为扩展结点,使搜索朝着解空间树上有最优解的分支推进,以便尽快地找出一个最优解。
方法概述
求解步骤:
定义解空间(对解编码);
确定解空间的树结构;
按BFS等方式搜索:
a. 每个活结点仅有一次机会变成扩展结点;
b. 由扩展结点生成一步可达的新结点;
c. 在新结点中,删除不可能导出最优解的结点;//限界策略
d. 将剩余的新结点加入活动表(队列)中;
e. 从活动表中选择结点再扩展; //分支策略
f. 直至活动表为空;
2017/12/14
6
方法概述
常见的两种分支限界法:
队列式(FIFO)分支限界法:从活结点表中取出结点的顺序与加入结点的顺序相同,因此活结点表的性质与队列相同;
优先队列(代价最小或效益最大)分支限界法:每个结点都有一个对应的耗费或收益,以此决定结点的优先级:
—如果查找一个具有最小耗费的解,则活结点可用小根堆来建立,下一个扩展结点就是具有最小耗费的活结点;
—如果希望搜索一个具有最大收益的解,则可用大根堆来构造活结点表,下一个扩展结点是具有最大收益的活结点。
2017/12/14
7
解空间树的动态搜索
(1)回溯求解0/1背包问题,虽剪枝减少了搜索空间,但整个搜索按深度优先机械进行,是盲目搜索(不可预测本结点以下的结点进行的如何)。
(2)回溯求解TSP也是盲目的(虽有目标函数,也只有找到一个可行解后才有意义)
解空间树的动态搜索
分支限界法首先确定一个合理的限界函数,并根据限界函数确定目标函数的界[down, up];
然后按照广度优先策略遍历问题的解空间树,在某一分支上,依次搜索该结点的所有孩子结点,分别估算这些孩子结点的目标函数的可能取值(对最小化问题,估算结点的down,对最大化问题,估算结点的up)。
如果某孩子结点的目标函数值超出目标函数的界,则将其丢弃(从此结点生成的解不会比目前已得的更好),否则入待处理表。
0-1背包问题
物品数量n=3,重量w=(20,15,15),价值v=(40,25,25),背包容量c=30,试装入价值和最大的物品?
FIFO队列分支限界法求解:
解空间:{(0,0,0),(0,0,1),…,(1,1,1)}
解空间树:
2017/12/14
10