欧氏空间货郎担问题的一个多项式时间近似方案的改进与实现  

Improvement and Implementation of a Polynomial Time Approximation Scheme for Euclidean Traveling Salesman Problem

作　　者：赵卫中[1] 冯好娣[1] 朱大铭[1] 

机构地区：[1]山东大学计算机科学与技术学院,济南250061

出　　处：《计算机研究与发展》2007年第10期1790-1795,共6页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60603007;60573024);国家"九七三"重点基础研究发展规划基金项目(2005CCA04500);山东省自然科学基金项目(Q2006G01)

摘　　要：货郎担问题的实例是给定n个结点和任意一对结点{i,j}之间的距离di,j,要求找出一条封闭的回路,该回路经过每个结点一次且仅一次,并且费用最小,这里的费用是指回路上相邻结点间的距离和.货郎担问题是NP难的组合优化问题,是计算机算法研究的热点之一.在过去几十年中,这一经典问题成为许多重要算法思想的测试平台,并促使一些研究领域的出现,如多面体理论和复杂性理论.欧氏空间上的货郎担问题,结点限制在欧氏空间,距离定义为欧氏距离.即使是这样,欧氏空间上的货郎担问题仍然是NP难的.1996年,Arora提出欧氏空间上货郎担问题的第1个多项式时间近似方案.对其中货郎担问题的算法进行了改进:提出一种新的构造方法,使应用于该算法的"补丁引理"结论由常数6改进到常数3,从而使算法的时间复杂度大幅减少;同时,编程实现了该算法,并对实验结果进行了分析.In the traveling salesman problem（＂TSP＂ for short）,given n nodes and for each pair {i,j} of distinct nodes,a distance di,j,it desires a closed path that visits each node exactly once and incurs the least cost,which is the sum of the distances along the path.Traveling salesman problem is a NP-hard combinatorial optimization problem,and one of hot topics in computer algorithm field.The classic problem has proved a rich testing ground for most important algorithmic ideas during the past few decades,and influenced the emergence of fields such as polyhedral theory and complexity theory.However,exact optimization for TSP is NP-hard.So is approximating the optimum within any constant factor.TSP instances arising in practice are usually quite special,so the hardness result may not necessarily apply to them.In Euclidean TSP,the nodes lie in R2and distance is defined using the l2 norm.However,even Euclidean TSP is NP-hard.In 1996,S.Arora gave the first polynomial time approximation scheme（＂PTAS＂,for short） for this problem.An improvement on this scheme is proposed by reducing the constant in the so-called ＂patching lemma＂ from 6 to 3.At the same time,an implementation of the improved version is given.

关 键 词：货郎担问题 近似算法 多项式时间近似方案 计算复杂性 动态规划 

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