| 对称型TSP下界的快速估算法 |
| |
| 引用本文： | 宁爱兵,马良. 对称型TSP下界的快速估算法[J]. 系统工程理论与实践, 2004, 24(12): 84-88. DOI: 10.12011/1000-6788(2004)12-84 |
| |
| 作者姓名： | 宁爱兵 马良 |
| |
| 作者单位： | 上海理工大学管理学院 |
| |
| 基金项目： | 国家自然科学基金(70471065)，上海市教委重点学科建设资助项目 |
| |
| 摘 要： | 在数学推导和证明的基础上,给出了一个求解对称型TSP问题下界的快速算法,利用该算法求解了TSP标准问题库中部分对称型问题,给出了计算结果并与标准问题库中公布的最好解进行了比较,获得了令人满意的效果.
|
| 关 键 词： | 旅行商问题 下界 算法 逼近程度 |
| 文章编号： | 1000-6788(2004)12-0084-05 |
| 修稿时间： | 2003-06-02 |
A Quick Algorithm for Calculating the Lower Bound of Symmetric Traveling Salesman Problem |
| |
| NING Ai-bing,MA Liang. A Quick Algorithm for Calculating the Lower Bound of Symmetric Traveling Salesman Problem[J]. Systems Engineering —Theory & Practice, 2004, 24(12): 84-88. DOI: 10.12011/1000-6788(2004)12-84 |
| |
| Authors: | NING Ai-bing MA Liang |
| |
| Affiliation: | College of Management,University of Shanghai for Science and Technology |
| |
| Abstract: | Based on mathematical inference and proof, we propose a quick algorithm for calculating the lower bound of symmetric Travelling Salesman Problem. By using the algorithm, series of numerical examples of TSP(traveling salesman problem) from TSBLIB are solved and the computational results are compared with the best-known solutions published, which give promising results. |
| |
| Keywords: | TSP(traveling salesman problem) lower bound algorithm approximation ratio |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《系统工程理论与实践》浏览原始摘要信息 |
|
点击此处可从《系统工程理论与实践》下载全文 |
