求解货郎担问题的几何算法
A Geometrical Algorithm for Solving the Travelling Salesman Problem
-
摘要: 提出了求解货郎担问题的一种几何算法,它的时间复性为:O(n^3/m)次比较,O(n^2)次求距离运算与O(n^3/m^3)次加法运算,其中n,m分别为点集的点数和凸包顶点数。Abstract: A geometrical algorithm for solving TSP is presented.The algorithm requires O(n2/m)comparisons,O(n2)operations for calculating the distance between the points and the distance between the points and the lines and O(n3/m3)additive operations,in Which n,m are the numbers of the given points and the numbers of the vertices of the convex hull respectively.
下载: