| TSP邻近算法在Euclid平面上的性能比分析 |
| |
| 引用本文： | 刘剑平. TSP邻近算法在Euclid平面上的性能比分析[J]. 华东理工大学学报(自然科学版), 2004, 30(3): 336-338 |
| |
| 作者姓名： | 刘剑平 |
| |
| 作者单位： | 华东理工大学数学系,上海,200237 |
| |
| 基金项目： | 华东理工大学科研基金资助项目 |
| |
| 摘 要： | 旅行推销员问题(TSP)邻近算法的性能比已经被证明有一个关于点数的对数函数上界，本文就该方法在欧几里得平面上给出了性能比的一个对数下界。
|
| 关 键 词： | 旅行推销员问题 启发式算法 邻近算法 性能比 |
| 文章编号： | 1006-3080(2004)03-0336-03 |
| 修稿时间： | 2003-06-06 |
Performance Ratio Analysis of the Nearest Neighbor Algorithm of TSP in Euclidean Plane |
| |
| LIU Jian-ping. Performance Ratio Analysis of the Nearest Neighbor Algorithm of TSP in Euclidean Plane[J]. Journal of East China University of Science and Technology, 2004, 30(3): 336-338 |
| |
| Authors: | LIU Jian-ping |
| |
| Abstract: | The performance ratio of the nearest neighbor algorithm of traveling salesman problem has been shown to have an upper bound above by a logarithmic function of the number of nodes. In this paper, we provide a logarithmic lower bound on the worst case in Euclidean plane. |
| |
| Keywords: | traveling salesman problem heuristics algorithm nearest neighbor algorithm performance ratio |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
