期刊文献+

瓶颈TSP下界快速算法

A Quick Algorithm for Calculating the Lower Bound of Bottleneck Traveling Salesman Problem
下载PDF
导出
摘要 瓶颈TSP是网络设计和优化中的一个NP难题,在数学推导和证明的基础上,给出了一个求解对称型瓶颈TSP问题下界的快速算法,利用该算法求解了TSP问题标准库中部分对称型问题,给出了计算结果并与标准问题库中已知的最好解进行了比较。 Finding the Bottleneck Traveling Salesman Problem (BTSP) tour in a given graph is a NP-hard problem which is important in network design and combinatorial optimization. Based on mathematical inference and proof, a quick algorithm for calculating the lower bound of symmetric bottleneck is proposed Travelling Salesman Problem is proposed. Series of numerical examples of BTSP from TSBLIB are tested and the computational results of the algorithm are compared with the best-known solutions published.
出处 《科学技术与工程》 2006年第9期1260-1263,共4页 Science Technology and Engineering
基金 国家自然科学基金(70471065) 上海市教委科技发展基金(05EZ31) 上海市重点学科建设项目(T0502)资助
关键词 瓶颈TSP 下界 算法 逼近程度 bottleneck traveling salesman problem lower bound algorithm approximation ratio
  • 相关文献

参考文献4

  • 1[1]Garfinkel R S,Gilbert K C.The bottleneck traveling salesman probem:algorithms and probabilistic analysis.J of ACM,1978; 25(3):435-448
  • 2马良.瓶颈TSP的蚂蚁系统优化[J].计算机工程,2001,27(9):24-25. 被引量:19
  • 3[4]Syslo M M,et al.Discrete optimization algorithms.Englewood Cliffs,New Jersey:Prentice-Hall,Inc.,1983; 343-361
  • 4[5]Hochbaum D S.Approximation algorithms for NP-hard:problems.Boston,MA:PWS Publishing Company,1997; 298-304

二级参考文献4

  • 1马良.中国144城市TSP的蚂蚁搜索算法[J].计算机应用研究,2000,17(1):36-37.
  • 2马良,计算机应用研究,2000年,17卷,1期,36页
  • 3马良,J Syst Sci Syst Eng,1999年,8卷,3期,335页
  • 4马良,Proc Of '99 Int Conf Management Science Engineering,1999年,448页

共引文献18

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部