摘要
研究求解中国货郎担问题最短回路的多项式时间算法．首先利用计算几何中凸亮与中轴的结构将点集划分成若干个子点集，然后反复采用求子点集凸壳及划分剩余干点集的方法，求得通过于点集的子路径，最后将各子路径连接成一条回路．中国货郎担问题存在多项式时间算法求得最短回路．所设计的算法的时间复杂性为O（n2lbn），将它用于中国货郎担问题，得到一条长度为15404km的最短回路．与陈沐天等人采用几何分块方法所得的最短回路相一致．
To present a new polynomial time algorithm for China traveling salesman problem, first, point set was partitioned into a number of subpoint sets by using convex hull and medial axis. Then the method for solving the convex hulls of subpoint sets and partitioning the remaining subsets was repeatedly used to obtain a subpath through the subpoint set. Finally, the subpaths were joined to form a circuit. The time complexity of the new algorithm is O(n2lbn). And its application to China traveling salesman problem will give the shortest circuit 15404 km in length. There exists polynomial time algorithm to solve China traveling salesman problem and obtain the shortest circuit.
出处
《北京理工大学学报》
EI
CAS
CSCD
2000年第2期201-204,共4页
Transactions of Beijing Institute of Technology
关键词
中国货郎担问题
最短回路
多项式时间算法
China traveling salesman problem
the shortest circuit
polynomial time algorithm
