第六章分支限界法 埋解分支限界法的剪枝搜索策略。 ■掌握分支限界法的算法框架 队列式(FFO分支限界法 优先队列式分支限界法
1 第六章 分支限界法 ◼ 理解分支限界法的剪枝搜索策略。 ◼ 掌握分支限界法的算法框架 ◼ 队列式(FIFO)分支限界法 ◼ 优先队列式分支限界法
第五章分支限界法 通过应用范例学习分支限界法的设计策略 单源最短路径问题 装载问题 布线问题 0-1背包问题 最大团问题 旅行售货员问题 电路板排列问题 批处理作业调度问题
2 第五章 分支限界法 ◼ 通过应用范例学习分支限界法的设计策略。 ◼ 单源最短路径问题 ◼ 装载问题； ◼ 布线问题 ◼ 0-1背包问题； ◼ 最大团问题； ◼ 旅行售货员问题 ◼ 电路板排列问题 ◼ 批处理作业调度问题
分支限界法的基本思想 分支限界法与回溯法 (1)求解目标:回溯法的求解目标是找出解空间 树中满足约束条件的所有解,而分支限界法的求解 目标则是找出满足约束条件的一个解,或是在满足 约束条件的解中找出在某种意义下的最优解。 (2)搜索方式的不同: 回溯法以深度优先的方式搜索解空间树; 而分支限界法则以广度优先或以最小耗费优先的方 式搜索解空间树
3 分支限界法的基本思想 分支限界法与回溯法 （1）求解目标：回溯法的求解目标是找出解空间 树中满足约束条件的所有解，而分支限界法的求解 目标则是找出满足约束条件的一个解，或是在满足 约束条件的解中找出在某种意义下的最优解。 （2）搜索方式的不同： 回溯法以深度优先的方式搜索解空间树; 而分支限界法则以广度优先或以最小耗费优先的方 式搜索解空间树
分支限界法的基本思想 分支限界法常以广度优先或以最小耗费 最大效益)优先的方式搜索问题的解空间 树。对已处理的各结点根据限界函数估算目 标函数的可能取值,从中选取使目标函数取 得极值(极大/极小)的结点优先进行广度优 先搜索→不断调整搜索方向,尽快找到解。 特点:限界函数常基于问题的目标函数,适 用于求解最优化问题
4 分支限界法的基本思想 分支限界法常以广度优先或以最小耗费 （最大效益）优先的方式搜索问题的解空间 树。对已处理的各结点根据限界函数估算目 标函数的可能取值，从中选取使目标函数取 得极值（极大/极小）的结点优先进行广度优 先搜索→不断调整搜索方向，尽快找到解。 特点：限界函数常基于问题的目标函数，适 用于求解最优化问题
分支限界法的基本思想 在分支限界法中,每一个活结点只有一次机会成 为扩展结点。活结点一旦成为扩展结点,就一次性 产生其所有儿子结点。在这些儿子结点中,导致不 可行解或导致非最优解的儿子结点被舍弃,其余儿 子结点被加入活结点表中 此后,从活结点表中取下一结点成为当前扩展结 点,并重复上述结点扩展过程。这个过程一直持续 到找到所需的解或活结点表为空时为止
5 分支限界法的基本思想 此后，从活结点表中取下一结点成为当前扩展结 点，并重复上述结点扩展过程。这个过程一直持续 到找到所需的解或活结点表为空时为止。 在分支限界法中，每一个活结点只有一次机会成 为扩展结点。活结点一旦成为扩展结点，就一次性 产生其所有儿子结点。在这些儿子结点中，导致不 可行解或导致非最优解的儿子结点被舍弃，其余儿 子结点被加入活结点表中
分支限界法的基本思想 常见的两种分支限界法 (1)队列式(FIFO)分支限界法 按照队列先进先出(FIFO)原则选取下一个结 点为扩展结点。 (2)优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高 的结点成为当前扩展结点
6 分支限界法的基本思想 常见的两种分支限界法 （1）队列式(FIFO)分支限界法 按照队列先进先出（FIFO）原则选取下一个结 点为扩展结点。 （2）优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高 的结点成为当前扩展结点
解空间树的动态搜索 (1)回溯求解0/1背包问题,虽剪枝减少了搜索 空间,但整个搜索按深度优先机械进行,是盲目 搜索(不可预测本结点以下的结点进行的如何) (2)回溯求解TSP也是盲目的(虽有目标函数, 也只有找到一个可行解后才有意义)
7 解空间树的动态搜索 （1）回溯求解0/1背包问题，虽剪枝减少了搜索 空间，但整个搜索按深度优先机械进行，是盲目 搜索（不可预测本结点以下的结点进行的如何）。 （2）回溯求解TSP也是盲目的（虽有目标函数， 也只有找到一个可行解后才有意义）
解空间树的动态搜索 分支限界法首先确定一个合理的限界函数,并根据限 界函数确定目标函数的界[dow,up 然后按照广度优先策略遍历问题的解空间树,在某· 分支上,依次搜索该结点的所有孩子结点,分别估算 这些孩子结点的目标函数的可能取值(对最小化问题, 估算结点的down,对最大化问题,估算结点的u)。 如果某孩子结点的目标函数值超出目标函数的界,则 将其丢弃(从此结点生成的解不会比目前已得的更 好),否则入待处理表
8 解空间树的动态搜索 分支限界法首先确定一个合理的限界函数，并根据限 界函数确定目标函数的界[down, up]； 然后按照广度优先策略遍历问题的解空间树，在某一 分支上，依次搜索该结点的所有孩子结点，分别估算 这些孩子结点的目标函数的可能取值（对最小化问题， 估算结点的down，对最大化问题，估算结点的up）。 如果某孩子结点的目标函数值超出目标函数的界，则 将其丢弃（从此结点生成的解不会比目前已得的更 好），否则入待处理表
0/1背包的分支限界法过程 向题描述 容量v=10 物品重()价(价重(vn) 4 40 10 25 4 12 贪心法的解(1,0,0.0),价值为40,可作为01背包的下界
9 0/1背包的分支限界法过程 1. 问题描述 物品 重(w) 价(v) 价/重(v/w) 1 4 40 10 2 7 42 6 3 5 25 5 4 3 12 4 容量w=10 贪心法的解(1,0,0,0)，价值为40，可作为0/1背包的下界
0/1背包的分支限界法过程 2.求解过程 上界υb可用最好情况来代替ub=w*(v∧w1)10*10=100 目标函数的界40,100,一般解空间树中第的各结 点,代表对物1~的选择,可这样定限界函数 ub=V+(W-w) *(vi+/wi+D) 已装入价值剩余容量剩下物品最大单位价值v1/w1 的积 可参考板书视图
10 0/1背包的分支限界法过程 2. 求解过程 上界ub可用最好情况来代替ub=w*(v1/w1)=10*10=100 目标函数的界[40, 100]，一般解空间树中第i层的各结 点，代表对物1~i的选择，可这样定限界函数： ub=V+(W-w)*(vi+1/wi+1) 可参考板书视图 已装入价值 剩余容量 剩下物品最大单位价值vi+1/wi+1 的积