分支界定算法
5页1、分支定界(branch and bound)算法是一种在问题的解空间树上搜索问题的解的方法。但与回 溯算法不同,分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树,并且,在分 支定界算法中,每一个活结点只有一次机会成为扩展结点。利用分支定界算法对问题的解空间树进行搜索,它的搜索策略是:1 .产生当前扩展结点的所有孩子结点;2 .在产生的孩子结点中,抛弃那些不可能产生可行解(或最优解)的结点;3 .将其余的孩子结点加入活结点表;4 .从活结点表中选择下一个活结点作为新的扩展结点。如此循环,直到找到问题的可行解(最优解)或活结点表为空。从活结点表中选择下一个活结点作为新的扩展结点,根据选择方式的不同,分支定界算 法通常可以分为两种形式:1 . FIFO(First In First Out)分支定界算法:按照先进先出原则选择下一个活结点作为 扩展结点,即从活结点表中取出结点的顺序与加入结点的顺序相同。2 .最小耗费或最大收益分支定界算法:在这种情况下,每个结点都有一个耗费或收益。 如果要查找一个具有最小耗费的解,那么要选择的下一个扩展结点就是活结点表中具有最小 耗费的活结点;如果要查
2、找一个具有最大收益的解,那么要选择的下一个扩展结点就是活结 点表中具有最大收益的活结点。又称分支定界搜索法。过程系统综合的一类方法。该法是将原始问题分解,产生一组子 问题。分支是将一组解分为几组子解,定界是建立这些子组解的目标函数的边界。如果某一 子组的解在这些边界之外,就将这一子组舍弃(剪枝)。分支定界法原为运筹学中求解整数 规划(或混合整数规划)问题的一种方法。用该法寻求整数最优解的效率很高。将该法原理用 于过程系统综合可大大减少需要计算的方案数日。分支定界法的思想是:首先确定目标值的上下界,边搜索边减掉搜索树的某些支,提高 搜索效率。在竞赛中,我们有时会碰到一些题目,它们既不能通过建立数学模型解决,又没有现成 算法可以套用,或者非遍历所有状况才可以得出正确结果。这时,我们就必须采用搜索算法 来解决问题。搜索算法按搜索的方式分有两类,一类是深度优先搜索,一类是广度优先搜索。我们知 道,深度搜索编程简单,程序简洁易懂,空间需求也比较低,但是这种方法的时间复杂度往 往是指数级的,倘若不加优化,其时间效率简直无法忍受;而广度优先搜索虽然时间复杂度 比前者低一些,但其庞大的空间需求量又往往
3、让人望而却步。所以,对程序进行优化,就成为搜索算法编程中最关键的一环。本文所要讨论的便是搜索算法中优化程序的一种基本方法枣“剪枝”。什么是剪枝相信刚开始接触搜索算法的人,都做过类似迷宫这样的题目吧。我们在“走迷宫”的时候, 一般回溯法思路是这样的:1、这个方向有路可走,我没走过2、往这个方向前进3、是死胡同,往回走,回到上一个路口4、重复第一步,直到找着出口这样的思路很好理解,编程起来也比较容易。但是当迷宫的规模很大时,回溯法的缺点 便暴露无遗:搜索耗时极巨,无法忍受。我们可不可以在向某个方向前进时,先一步判断出这样走会不会走到死胡同里呢?这样 一来,搜索的时间不就可以减少了吗?答案是:可以的。剪枝的概念,其实就跟走迷宫避开死胡同差不多。若我们把搜索的过程看成是对一棵树 的遍历,那么剪枝顾名思义,就是将树中的一些“死胡同”,不能到达我们需要的解的枝条“剪” 掉,以减少搜索的时间。搜索算法,绝大部分需要用到剪枝。然而,不是所有的枝条都可以剪掉,这就需要通过 设计出合理的判断方法,以决定某一分支的取舍。在设计判断方法的时候,需要遵循一定的 原则。剪枝的原则1、正确性正如上文所述,枝条不是爱
《分支界定算法》由会员pu****.1分享,可在线阅读,更多相关《分支界定算法》请在金锄头文库上搜索。
人教部编版版小学语文二年级下册-我是一只小虫子-名师教学课件-(2)
社区残联工作年终总结
北京牌照租赁协议实常用版(七篇).doc
2023年学前教育宣传月系列活动总结
生产科安全生产承诺书
【最新资料】辽宁省本溪市中考数学试卷及答案Word解析版
总线型网络结构设备采购方案
小学生养成教育实施方案
铜陵市氢能公司成立策划书模板范本
名师培养工作计划
教师述职报告模板汇编十篇
2023年仓储部年终总结(4篇).doc
校园健康教育工作计划范文(2篇).doc
和好书交朋友遨游知识大海洋讲话
广告位租赁合同精编版(六篇)
劳动保障局社会保险稽核工作总结
医药销售个人工作计划标准样本(三篇).doc
公司节能减排管理办法
草桥中学2011年初三语文二模试卷及答案
输血科工作制度汇编1
2023-06-28 7页
2024-01-31 37页
2022-10-26 5页
2022-10-05 6页
2024-01-19 72页
2024-01-29 51页
2022-09-22 10页
2022-11-10 7页
2023-09-29 7页
2023-12-11 9页