文档介绍：第9章 分支限界法 Branch and Bound Method
算法设计与分析—本科生课程
Design and Analysis of Algorithm
邱钊
海南大学信息科学技术学院
College of Information Science and Technology, Hainan University
qiuzhao73@
2017/8/16
2
教学重点
分支限界法的设计思想,各种经典问题的限界函数
教学难点
各种经典问题的限界函数以及限界算法
教学内容及目标
知识点
教学要求
了解
理解
掌握
熟练掌握
分支限界法的设计思想
√
分支限界法的时空性能
√
TSP问题
√
多段图的最短路径问题
√
0/1背包问题
√
任务分配问题
√
批处理作业调度问题
√
学****目标
Chapter 8 Back Track Method
2017/8/16
Branch and Bound Method
3
第9章分支限界法
概述
图问题中的分支限界法
组合问题中的分支限界法
2017/8/16
Branch and Bound Method
4
回溯法:按深度优先策略遍历问题的解空间树,应用约束条件、目标函数等剪枝函数实行剪枝
分支限界法:按广度优先策略遍历问题的解空间树,在遍历过程中,对已经处理的每一个结点根据限界函数估算目标函数的可能取值,从中选取使目标函数取得极值的结点优先进行广度优先搜索,从而不断调整搜索方向,尽快找到问题的解。
概述
2017/8/16
Branch and Bound Method
5
概述
分支限界法的设计思想
分支限界法的时间性能
2017/8/16
Branch and Bound Method
6
回溯法存在的问题
虽用剪枝减少了搜索空间,但按深度优先策略机械地进行,搜索是盲目的。如0/1背包问题。
首先将目标函数初始化为最大值,目标函数只有在有一个可行解(第一个叶子)后才有意义,此后的搜索相对来说才有方向,所以从搜索的整个过程来看还是盲目的。如TSP问题()。
分支限界法
先确定一个合理的限界函数
由限界函数确定目标函数的界[down, up]
仍以穷举法的解空间树为基础,但以广度优先的原理搜索该结点的所有孩子结点,分别估算这些孩子结点的目标函数的可能取值
分支限界法的设计思想
2017/8/16
Branch and Bound Method
7
如果某孩子结点的目标函数可能取值超出目标函数的界,则将其丢弃,因为从这个结点生成的解不会比目前已经得到的解更好;否则,将其加入待处理结点表(表PT)
依次从表PT中选取使目标函数的值取极值的结点成为当前扩展结点,重复上述过程,直到找到最优解。
目标函数的界[down, up]的确定
对最大化问题
Up由限界函数确定,down由某种启发方式得到,如贪心算法
对最小化问题
down由限界函数确定,up由某种启发方式得到,如贪心算法
分支限界法的设计思想
2017/8/16
Branch and Bound Method
8
例:0/1背包问题。假设有4个物品,其重量分别为(4, 7, 5, 3),价值分别为(40, 42, 25, 12),背包容量W=10。首先,将给定物品按单位重量价值从大到小排序,结果如下:
物品
重量(w)
价值(v)
价值/重量(v/w)
1
4
40
10
2
7
42
6
3
5
25
5
4
3
12
4
分支限界法的设计思想
2017/8/16
Branch and Bound Method
9
确定上下界
down:应用贪心法求得近似解为(1, 0, 1, 0),获得的价值为65,这可以作为0/1背包问题的下界。
up:考虑最好情况,背包中全部装入第1个物品且可以将背包装满,则可得到一个简单上界的计算方法:
up=W×(v1/w1)=10×10=100
则目标函数的界:[65, 100]
限界函数为:
分支限界法的设计思想
2017/8/16
Branch and Bound Method
10
×
w=0, v=0
ub=100
w=4, v=40
ub=76
w=0, v=0
ub=60
w=11
无效解
w=4, v=40
ub=70
w=9, v=65
ub=69
w=4, v=40
ub=64
w=12
无效解
w=9, v=65
ub=65
2
3
4
5
6
7
8
9
×
1
×
×
PT表