摘要
本文提出货郎担问题的一种新的求解方法，即几何解法．它的时间复杂性为：求距离运算次数为Ｏ（ｎｍ），比较次数为Ｏ（ｍａｘ（ｎｍ，ｎｌｏｇｎ）），求夹角次数为Ｏ（），其中ｎ为点集中点的数目，ｍ为点集的凸包顶点数．
In this paper, a new geometric method for solving TS problem is presented.Let n be the number of points in the point set, and m be the number of vertexes in convex hulls of the point set. The time complexity of the algorithm is: the number of computation distance is O(nm), the number of comparisons is O(max(nm, nlogn) ) and the number of computation included angle is O().
出处
《软件学报》
EI
CSCD
北大核心
1995年第7期420-424,共5页
Journal of Software
关键词
并行算法
货郎担问题
几何解法
Geometric algorithm, algorithmic complexity, travel salesman problem.
