第六章分支限界法 埋解分支限界法的剪枝搜索策略。 ■掌握分支限界法的算法框架 队列式(FFO分支限界法 优先队列式分支限界法
1 第六章 分支限界法 ◼ 理解分支限界法的剪枝搜索策略。 ◼ 掌握分支限界法的算法框架 ◼ 队列式(FIFO)分支限界法 ◼ 优先队列式分支限界法
第五章分支限界法 通过应用范例学习分支限界法的设计策略 单源最短路径问题 装载问题 布线问题 0-1背包问题 最大团问题 旅行售货员问题 电路板排列问题 批处理作业调度问题
2 第五章 分支限界法 ◼ 通过应用范例学习分支限界法的设计策略。 ◼ 单源最短路径问题 ◼ 装载问题； ◼ 布线问题 ◼ 0-1背包问题； ◼ 最大团问题； ◼ 旅行售货员问题 ◼ 电路板排列问题 ◼ 批处理作业调度问题
分支限界法的基本思想 分支限界法与回溯法 (1)求解目标:回溯法的求解目标是找出解空间 树中满足约束条件的所有解,而分支限界法的求解 目标则是找出满足约束条件的一个解,或是在满足 约束条件的解中找出在某种意义下的最优解。 (2)搜索方式的不同: 回溯法以深度优先的方式搜索解空间树; 而分支限界法则以广度优先或以最小耗费优先的方 式搜索解空间树
3 分支限界法的基本思想 分支限界法与回溯法 （1）求解目标：回溯法的求解目标是找出解空间 树中满足约束条件的所有解，而分支限界法的求解 目标则是找出满足约束条件的一个解，或是在满足 约束条件的解中找出在某种意义下的最优解。 （2）搜索方式的不同： 回溯法以深度优先的方式搜索解空间树; 而分支限界法则以广度优先或以最小耗费优先的方 式搜索解空间树
分支限界法的基本思想 分支限界法常以广度优先或以最小耗费 最大效益)优先的方式搜索问题的解空间 树。对已处理的各结点根据限界函数估算目 标函数的可能取值,从中选取使目标函数取 得极值(极大/极小)的结点优先进行广度优 先搜索→不断调整搜索方向,尽快找到解。 特点:限界函数常基于问题的目标函数,适 用于求解最优化问题
4 分支限界法的基本思想 分支限界法常以广度优先或以最小耗费 （最大效益）优先的方式搜索问题的解空间 树。对已处理的各结点根据限界函数估算目 标函数的可能取值，从中选取使目标函数取 得极值（极大/极小）的结点优先进行广度优 先搜索→不断调整搜索方向，尽快找到解。 特点：限界函数常基于问题的目标函数，适 用于求解最优化问题
分支限界法的基本思想 在分支限界法中,每一个活结点只有一次机会成 为扩展结点。活结点一旦成为扩展结点,就一次性 产生其所有儿子结点。在这些儿子结点中,导致不 可行解或导致非最优解的儿子结点被舍弃,其余儿 子结点被加入活结点表中 此后,从活结点表中取下一结点成为当前扩展结 点,并重复上述结点扩展过程。这个过程一直持续 到找到所需的解或活结点表为空时为止
5 分支限界法的基本思想 此后，从活结点表中取下一结点成为当前扩展结 点，并重复上述结点扩展过程。这个过程一直持续 到找到所需的解或活结点表为空时为止。 在分支限界法中，每一个活结点只有一次机会成 为扩展结点。活结点一旦成为扩展结点，就一次性 产生其所有儿子结点。在这些儿子结点中，导致不 可行解或导致非最优解的儿子结点被舍弃，其余儿 子结点被加入活结点表中