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

• 作者: 王刚 骆志刚
• 来源期刊: 计算机研究与发展
• 学科: 工学
• 关键词: 旅行商问题 近似算法 多项式时间近似方案 凸壳 旋转卡壳 射影
• 年，卷（期）: 2013,（3）
• 所属期刊栏目: 算法理论
• 页码范围: 657-665
• 页数: 9页
• 分类号: TP301.6
• 字数: 8654字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王刚	国防科学技术大学计算机学院	16	158	6.0	12.0
2	骆志刚	国防科学技术大学计算机学院	21	149	7.0	12.0