算法导论-课件PPT（演示稿）.ppt

University of Science and Technology of China主讲人:吕敏Email: { ******@ustc. }Spring 2011,USTC算法基础University of Science and Technology of China2016-11-192第十二讲分支限界法内容提要:?理解分支限界法的剪枝搜索策略?掌握分支限界法的算法框架(1)队列式(FIFO)分支限界法(2)优先队列式分支限界法?通过应用范例学习分支限界法的设计策略University of Science and Technology of China方法概述与回溯法区别:?求解目标不同:一般而言,回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分支限界法的求解目标则是尽快地找出满足约束条件的一个解;?搜索方法不同:回溯法使用深度优先方法搜索,而分支限界一般用宽度优先或最佳优先方法来搜索;?对扩展结点的扩展方式不同:分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点;?存储空间的要求不同分支限界法的存储空间比回溯法大得多,因此当内存容量有限时,回溯法成功的可能性更大。2016-11-193University of Science and Technology of China方法概述基本思想:?分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。对已处理的各结点根据限界函数估算目标函数的可能取值,从中选取是目标函数取得极大(小)值的结点优先进行广度优先搜索?不断调整搜索方向,尽快找到解,裁剪那些不能得到最优解的子树以提高搜索效率。?特点:限界函数常基于问题的目标函数,适用于求解最优化问题。2016-11-194University of Science and Technology of China方法概述?搜索策略是:在扩展结点处,先生成其所有的儿子结点(分支),然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一个扩展结点,以加速搜索的进程,在每一活结点处,计算一个函数值(优先值),并根据这些已计算出的函数值,从当前活结点表中选择一个最有利的结点作为扩展结点,使搜索朝着解空间树上有最优解的分支推进,以便尽快地找出一个最优解。University of Science and Technology of China方法概述?求解步骤:①定义解空间(对解编码);②确定解空间的树结构;③按BFS等方式搜索:a. 每个活结点仅有一次机会变成扩展结点;b. 由扩展结点生成一步可达的新结点;c. 在新结点中,删除不可能导出最优解的结点;//限界策略d. 将剩余的新结点加入活动表(队列)中;e. 从活动表中选择结点再扩展;//分支策略f. 直至活动表为空;2016-11-196University of Science and Technology of China方法概述常见的两种分支限界法:?队列式(FIFO)分支限界法:从活结点表中取出结点的顺序与加入结点的顺序相同,因此活结点表的性质与队列相同;?优先队列(代价最小或效益最大)分支限界法:每个结点都有一个对应的耗费或收益,以此决定结点的优先级:—如果查找一个具有最小耗费的解,则活结点可用小根堆来建立,下一个扩展结点就是具有最小耗费的活结点;—如果希望搜索一个具有最大收益的解,则可用大根堆来构造活结点表,下一个扩展结点是具有最大收益的活结点。2016-11-197University of Science and Technology of China解空间树的动态搜索(1)回溯求解0/1背包问题,虽剪枝减少了搜索空间,但整个搜索按深度优先机械进行,是盲目搜索(不可预测本结点以下的结点进行的如何)。(2)回溯求解TSP也是盲目的(虽有目标函数,也只有找到一个可行解后才有意义)University of Science and Technology of China解空间树的动态搜索分支限界法首先确定一个合理的限界函数,并根据限界函数确定目标函数的界[down, up];然后按照广度优先策略遍历问题的解空间树,在某一分支上,依次搜索该结点的所有孩子结点,分别估算这些孩子结点的目标函数的可能取值(对最小化问题,估算结点的down,对最大化问题,估算结点的up)。如果某孩子结点的目标函数值超出目标函数的界,则将其丢弃(从此结点生成的解不会比目前已得的更好),否则入待处理表。University of Science and Technology of China0-1背包问题?物品数量n=3,重量w=(20,15,15),价值v=(40,2