| 瓶颈TSP下界快速算法 |
| |
| 引用本文： | 宁爱兵,马良,王周缅.瓶颈TSP下界快速算法[J].科学技术与工程,2006,6(9):1260-1263. |
| |
| 作者姓名： | 宁爱兵 马良 王周缅 |
| |
| 作者单位： | 上海理工大学管理学院,上海,200093;上海理工大学管理学院,上海,200093;上海理工大学管理学院,上海,200093 |
| |
| 基金项目： | 国家自然科学基金（70471065）,上海市教委科技发展基金（05EZ31）和上海市重点学科建设项目（T0502）资助 |
| |
| 摘 要： | 瓶颈TSP是网络设计和优化中的一个NP难题，在数学推导和证明的基础上，给出了一个求解对称型瓶颈TSP问题下界的快速算法，利用该算法求解了TSP问题标准库中部分对称型问题，给出了计算结果并与标准问题库中已知的最好解进行了比较。
|
| 关 键 词： | 瓶颈TSP 下界 算法 逼近程度 |
| 文章编号： | 1671-1815(2006)09-1260-04 |
| 收稿时间： | 2006-01-11 |
| 修稿时间： | 2006年1月11日 |
A Quick Algorithm for Calculating the Lower Bound of Bottleneck Traveling Salesman Problem |
| |
| NING Aibing,MA Liang,Wang Zhoumian.A Quick Algorithm for Calculating the Lower Bound of Bottleneck Traveling Salesman Problem[J].Science Technology and Engineering,2006,6(9):1260-1263. |
| |
| Authors: | NING Aibing MA Liang Wang Zhoumian |
| |
| Abstract: | 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. |
| |
| Keywords: | bottleneck traveling salesman problem lower bound algorithm approximation ratio |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《科学技术与工程》浏览原始摘要信息 |
| 点击此处可从《科学技术与工程》下载免费的PDF全文 |
