| 求解货郎担问题的几何算法 |
| |
| 引用本文： | 周培德. 求解货郎担问题的几何算法[J]. 北京理工大学学报, 1995, 15(1): 97-99 |
| |
| 作者姓名： | 周培德 |
| |
| 作者单位： | 北京理工大学计算机科学与工程系 |
| |
| 摘 要： | 提出了求解货郎担问题的一种几何算法，它的时间复性为：Ｏ（ｎ＾３／ｍ）次比较，Ｏ（ｎ＾２）次求距离运算与Ｏ（ｎ＾３／ｍ＾３）次加法运算，其中ｎ，ｍ分别为点集的点数和凸包顶点数。
|
| 关 键 词： | 计算几何 旅行商问题 凸包 点集 |
A Geometrical Algorithm for Solving the Travelling Salesman Problem |
| |
| Zhou Peide. A Geometrical Algorithm for Solving the Travelling Salesman Problem[J]. Journal of Beijing Institute of Technology(Natural Science Edition), 1995, 15(1): 97-99 |
| |
| Authors: | Zhou Peide |
| |
| 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. |
| |
| Keywords: | computation geometric algorithmic complexity travelling-salesman problem |
| 本文献已被 CNKI 维普 等数据库收录！ |
| 点击此处可从《北京理工大学学报》浏览原始摘要信息 |
|
点击此处可从《北京理工大学学报》下载全文 |
