| 摘要: |
| 本文提出货郎担问题的一种新的求解方法，即几何解法．它的时间复杂性为：求距离运算次数为Ｏ（ｎｍ），比较次数为Ｏ（ｍａｘ（ｎｍ，ｎｌｏｇｎ）），求夹角次数为Ｏ（n2/m），其中ｎ为点集中点的数目，ｍ为点集的凸包顶点数． |
| 关键词: 几何算法 算法复杂性 货郎担问题 |
| DOI： |
| 分类号: |
| 基金项目: |
|
| GEOMETRIC METHOD FOR SOLVING TS PROBLEM |
|
Zhou Peide
|
| Abstract: |
| 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 Ｏ（ｎｍ）, the number of comparisons is Ｏ（ｍａｘ（ｎｍ，ｎｌｏｇｎ）） and the number of computation included angle is Ｏ（n2/m）. |
| Key words: Geometric algorithm algorithmic complexity travel salesman problem. |
