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

摘要：

欧氏旅行商问题(TSP)的多项式时间近似方案(PTAS)结合了递归剖分、动态规划两种方法.相似的技术已成功用于构造多个欧氏组合优化问题的PTAS.为进一步拓展该方法的适用范围,研究曲面上的TSP.观察到球面不像平面那样可以递归正则剖分,对于可被开半球完全覆盖的小尺度球面TSP,采用的策略为将其逆球心射影到一个球内接正方形上,扰动其顶点并构造剖分网格,接着将该网格射影到球面,然后如同平面TSP的PTAS一样进行动态规划等操作.该策略被拓展到非小尺度球面TSP及更一般的一类曲面TSP.需注意的是由于球面、平面之间射影变形的不规则性,无法将球面TSP直接PTAS归约为平面TSP.

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

所属期刊栏目：50

分类号：TP301.6(计算技术、计算机技术)

在线出版日期：2013-04-27（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：657-665