曲面上旅行商问题的多项式时间近似方案  

A Polynomial Time Approximation Scheme for the Traveling Salesman Problem in Curved Surfaces

作　　者：王刚[1] 骆志刚[1] 

机构地区：[1]国防科学技术大学计算机学院,长沙410073

出　　处：《计算机研究与发展》2013年第3期657-665,共9页Journal of Computer Research and Development

摘　　要：欧氏旅行商问题(TSP)的多项式时间近似方案(PTAS)结合了递归剖分、动态规划两种方法.相似的技术已成功用于构造多个欧氏组合优化问题的PTAS.为进一步拓展该方法的适用范围,研究曲面上的TSP.观察到球面不像平面那样可以递归正则剖分,对于可被开半球完全覆盖的小尺度球面TSP,采用的策略为将其逆球心射影到一个球内接正方形上,扰动其顶点并构造剖分网格,接着将该网格射影到球面,然后如同平面TSP的PTAS一样进行动态规划等操作.该策略被拓展到非小尺度球面TSP及更一般的一类曲面TSP.需注意的是由于球面、平面之间射影变形的不规则性,无法将球面TSP直接PTAS归约为平面TSP.The polynomial time approximation scheme （PTAS） for Euclidean traveling salesman problem （TSP） combines the two methods of recursive partition and dynamic programming. Similar techniques have been used to construct PTASes for some other Euclidean combinatorial optimization problems. To extend the applications of this method further, TSP in curved surfaces is studied. Observing that the sphere surface has no recursive regular partition as the plane, for a spherical TSP instance that can be covered by an open hemisphere, which we call a small scale instance, we project it onto a sphere-inscribed square to get a plane TSP instance. We perturb the new instance and construct its partition grid. Then we project the perturbed instance and the grid back onto the sphere surface. Things left, such as dynamic programming and randomization, are the same as the PTAS for the plane TSP. This result is generalized to non-small scale spherical TSP and TSP in a set of other curved surfaces. Because of the irregularity of the projections between the sphere surface and the plane, this method is not a PTAS reduction from the spherical TSP to the plane TSP.

关 键 词：旅行商问题 近似算法 多项式时间近似方案 凸壳 旋转卡壳 射影 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]