第6章 分支限界法.ppt

第6章分支限界法
2018/5/18
算法设计与分析
2
第6章分支限界法
学****要点
理解分支限界法的剪枝搜索策略
掌握分支限界法的算法框架
队列式(FIFO)分支限界法
优先队列式分支限界法
通过应用范例学****分支限界法的设计策略
0-1背包问题
2018/5/18
算法设计与分析
3
分支限界法的基本思想
分支限界法与回溯法的不同求解目标:
回溯法的求解目标:找出T(解空间状态树)中满足约束条件的所有解;
分支限界法的求解目标:找出满足约束条件的一个解,或是在满足约束条件的解中找出使用某一目标函数值达到极大或极小的解,即在某种意义下的最优解。
2018/5/18
算法设计与分析
4
分支限界法与回溯法的不同搜索方式
回溯法以深度优先的方式搜索解空间树T,而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。
分支限界法的搜索策略:在扩展结点处,先生成其所有的儿子结点(分支),然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点,以加速搜索的进程,在每一活结点处,计算一个函数值(限界),并根据这些已计算出的函数值,从当前活结点表中选择一个最有利的结点作为扩展结点,使搜索朝着解空间树上有最优解的分支推进,以便尽快地找出一个最优解。
2018/5/18
算法设计与分析
5
分支限界法的基本思想
分支限界法通常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。
问题的解空间树是表示问题解空间的一棵有序树,常见的有子集树和排列树。
2018/5/18
算法设计与分析
6
回顾:两种典型的解空间树
子集树(Subset Trees):当所给问题是从n个元素的集合中找出满足某种性质的子集时,相应的解空间树称为子集树。在子集树中,|S0|=|S1|=…=|Sn-1|=c,即每个结点有相同数目的子树,通常情况下c=2,所以,子集树中共有2n个叶子结点,因此,遍历子集树需要O(2n)时间。
排列树(Permutation Trees):当所给问题是确定n个元素满足某种性质的排列时,相应的解空间树称为排列树。在排列树中,通常情况下,|S0|=n,|S1|=n-1,…,|Sn-1|=1,所以,排列树中共有n!个叶子结点,因此,遍历排列树需要O(n!)时间。
2018/5/18
算法设计与分析
7
分支限界法的基本思想
每一个活结点只有一次机会成为扩展结点
活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,那些导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中
从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程
这个过程一直持续到找到所求的解或活结点表为空时为止。
活结点表:具有先进先出的性质,是队列。
2018/5/18
算法设计与分析
8
分支限界法的适用范围
分支限界法类似于回溯法,有一些问题其实无论用回溯法还是分支限界法都可以得到很好的解决,但是另外一些则不然。
下表列出了回溯法和分支限界法的一些区别:
方法
对解空间树的搜索方式
存储结点的常用数据结构
结点存储特性
常用应用
回溯法
深度优先搜索
栈
活结点的所有可行子结点被遍历后才被从栈中弹出
找出满足约束条件的所有解
分支限界法
广度优先或最小消耗优先搜索
队列、优先队列
每个结点只有一次成为扩展结点的机会
找出满足约束条件的一个解或特定意义下的最优解
2018/5/18
算法设计与分析
9
A、适合采用回溯法解决的问题— n后问题
问题定义:在n×n的国际象棋棋盘上摆下n个皇后,使所有的皇后都不能攻击到对方,找出所有符合要求的情况。
分析:
n后问题的解空间树是一棵排列树,解与解之间不存在优劣的分别。直到搜索到叶结点时才能确定出一组解。
采用回溯法可以系统地搜索问题的全部解。
考虑使用分支限界法?
2018/5/18
算法设计与分析
10
B、既可以采用回溯法也可以采用分支限界法解决的问题— 0-1背包问题
问题定义:给定若干物品的重量和价值,以及一个背包的容量上限。求出一种方案使得背包中存放物品的价值最高。
分析:0-1背包问题的解空间树是一棵子集树,所要求的解具有最优性质。