摘要
旅行推销员问题(TSP)邻近算法的性能比已经被证明有一个关于点数的对数函数上界,本文就该方法在欧几里得平面上给出了性能比的一个对数下界。
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.
出处
《华东理工大学学报（自然科学版）》
CAS
CSCD
北大核心
2004年第3期336-338,共3页
Journal of East China University of Science and Technology
基金
华东理工大学科研基金资助项目
关键词
旅行推销员问题
启发式算法
邻近算法
性能比
traveling salesman problem
heuristics algorithm
nearest neighbor algorithm
performance ratio
