欢迎来到天天文库
浏览记录
ID：75369584
大小：2.22 MB
页数：36页
时间：2021-12-14
《主讲人吕敏Email{lvmin05@ustc.edu.cn}Spring2012,》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、主讲人：吕敏Email:{lvmin05@ustc.edu.cn}Spring2012，USTC算法基础2021/12/112第十二讲分支限界法内容提要：理解分支限界法的剪枝搜索策略掌握分支限界法的算法框架（1）队列式(FIFO)分支限界法（2）优先队列式分支限界法通过应用范例学习分支限界法的设计策略方法概述与回溯法区别：求解目标不同：一般而言，回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是尽快地找出满足约束条件的一个解；搜索方法不同：回溯法使用深度优先方法搜索，而分支限界一般用宽度优先或最佳优先方法来搜索；对扩展结点的扩展方式不同：分支
2、限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点；存储空间的要求不同分支限界法的存储空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大。2021/12/113方法概述基本思想：分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。对已处理的各结点根据限界函数估算目标函数的可能取值，从中选取是目标函数取得极大（小）值的结点优先进行广度优先搜索不断调整搜索方向，尽快找到解，裁剪那些不能得到最优解的子树以提高搜索效率。特点：限界函数常基于问题的目标函数，适用于求解最优化问题。2021/12/
3、114方法概述搜索策略是：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一个扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（优先值），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。方法概述求解步骤：定义解空间（对解编码）；确定解空间的树结构；按BFS等方式搜索：a.每个活结点仅有一次机会变成扩展结点；b.由扩展结点生成一步可达的新结点；c.在新结点中，删除不可能导出最优解的结点；//限界策略d.将剩余的新
4、结点加入活动表（队列）中；e.从活动表中选择结点再扩展；//分支策略f.直至活动表为空；2021/12/116方法概述常见的两种分支限界法：队列式（FIFO）分支限界法：从活结点表中取出结点的顺序与加入结点的顺序相同，因此活结点表的性质与队列相同；优先队列（代价最小或效益最大）分支限界法：每个结点都有一个对应的耗费或收益，以此决定结点的优先级：—如果查找一个具有最小耗费的解，则活结点可用小根堆来建立，下一个扩展结点就是具有最小耗费的活结点；—如果希望搜索一个具有最大收益的解，则可用大根堆来构造活结点表，下一个扩展结点是具有最大收益
此文档下载收益归作者所有
