分支定界求解TSP问题

上传者: db10jiao | 上传时间: 2022-04-12 17:04:34 | 文件大小: 1.11MB | 文件类型: RAR
支限界法类又称为剪枝限界法或分支定界法,它类似于回溯法,也是一种在问题的解空间树T上搜索问题解的算法。它与回溯法有两点不同:①回溯法只通过约束条件剪去非可行解,而分支限界法不仅通过约束条件,而且通过目标函数的限界来减少无效搜索,也就是剪掉了某些不包含最优解的可行解。②在解空间树上的搜索方式也不相同。回溯法以深度优先的方式搜索解空间树,而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。分支限界法的搜索策略是:在扩展结点处,先生成其所有的儿子结点(分支),然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点,以加速搜索的进程, 在每一活结点处,计算一个函数值(限界),并根据这些已计算出的函数值,从当前活结点表中选择一个最有利的结点作为扩展结点,使搜索朝着解空间树上有最优解的分支推进,以便尽快地找出一个最优解。 从活结点表中选择下一扩展结点的不同方式导致不同的分支限界法。最常见的有以下两种方式: ①队列式(FIFO)分支限界法:队列式分支限界法将活结点表组织成一个队列,并按队列的先进先出原则选取下一个结点为当前扩展结点。 ②优先队列式分支限界法:优先队列式分支限界法将活结点表按照某个估值函数C(x)的值组织成一个优先队列,并按优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。 影响分支限界法搜索效率的有两个主要因素:一是优先队列Q的优先级由C(x)确定,它能否保证在尽可能早的情况下找到最优解,如果一开始找到的就是最优解,那么搜索的空间就能降低到最小。二是限界函数u(x),它越严格就越可能多地剪去分支,从而减少搜索空间。 在用分支限界法解决TSP问题时,有不少很好的限界函数和估值函数已经构造出来出了(限于篇幅,这里不做详细介绍), 使得分支限界法在大多数情况下的搜索效率大大高于回溯法。但是,在最坏情况下,该算法的时间复杂度仍然是O(n!),而且有可能所有的(n-1)!个结点都要存储在队列中。 近似算法是指不能肯定找到最优解的算法,但通常找到的也是比较好的解,或称近似最优解。[20]一般而言,近似算法的时间复杂度较低,通常都是多项式时间内的。由于近似算法的时间效率高,所以在实际应用中,主要是使用近似算法,这一类算法也一直是研究的主要对象。传统的近似算法以采用贪心策略和局部搜索为主,而几十年来,随着以遗传算法为代表的新型启发式搜索算法的逐步完善,在解决TSP问题上获得了巨大的成功。遗传算法、模拟退火算法、蚁群算法等已经成为公认的好算法。在本节中,将介绍传统的近似算法。

文件下载

资源详情

[{"title":"( 7 个子文件 1.11MB ) 分支定界求解TSP问题","children":[{"title":"分支定界求解TSP问题","children":[{"title":"0_1背包问题算法分析与研究.pdf <span style='color:#111;'> 326.63KB </span>","children":null,"spread":false},{"title":"求解TSP算法.pdf <span style='color:#111;'> 199.63KB </span>","children":null,"spread":false},{"title":"货郎担问题的指派解法.pdf <span style='color:#111;'> 222.47KB </span>","children":null,"spread":false},{"title":"分支限界法求解实际TSP问题.pdf <span style='color:#111;'> 233.75KB </span>","children":null,"spread":false},{"title":"用分支定界算法求解旅行商问题.pdf <span style='color:#111;'> 396.94KB </span>","children":null,"spread":false},{"title":"分支限界法.doc <span style='color:#111;'> 11.00KB </span>","children":null,"spread":false},{"title":"分支定界算法的MATLAB实现.pdf <span style='color:#111;'> 173.77KB </span>","children":null,"spread":false}],"spread":true}],"spread":true}]

评论信息

  • qq_35925465 :
    居然没有程序,你这个骗子
    2016-08-26
  • lj1056982248 :
    可以学习一下分支界定法。
    2016-04-25
  • tying_oey :
    只是一些理论性的文章,有一点点帮助吧
    2016-04-12
  • qq_16378589 :
    没有代码,坑爹啊!
    2015-09-02
  • celinecccoding :
    没代码诶,差评
    2014-12-27

免责申明

【只为小站】的资源来自网友分享,仅供学习研究,请务必在下载后24小时内给予删除,不得用于其他任何用途,否则后果自负。基于互联网的特殊性,【只为小站】 无法对用户传输的作品、信息、内容的权属或合法性、合规性、真实性、科学性、完整权、有效性等进行实质审查;无论 【只为小站】 经营者是否已进行审查,用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。
本站所有资源不代表本站的观点或立场,基于网友分享,根据中国法律《信息网络传播权保护条例》第二十二条之规定,若资源存在侵权或相关问题请联系本站客服人员,zhiweidada#qq.com,请把#换成@,本站将给予最大的支持与配合,做到及时反馈和处理。关于更多版权及免责申明参见 版权及免责申明