寻求中国货郎担问题最短回路的多项式时间算法

研究求解中国货郎担问题最短回路的多项式时间算法。首先利用计算机几何凸壳与中轴的结构将集划分尤其中干个子点集，然后反复采用求子点集凸壳及划分科余子点集的方法，求得通过子点集的子路径，最后将各子路径连接成一条回路。中国货郎担问题存在多项时间算法求得最短回路。

A Polynomial Time Algorithm for Solving the Shortest Circuit of China Traveling Salesman Problem

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.