旅行推销员问题 旅行商问题英語Travelling salesman problem縮寫TSP是组合优化中的一个NP困难问题在运筹学和理论计算机科学中非常重要问题内容为给定一系列城市和每對城市之间的距离求解访问每座城市一次并回到起始城市的最短回路 TSP是旅行购买者问题英语travelling purchaser problem与车辆路径问题的一种特殊情况 作为计算复杂性理论中一个典型的判定性问题TSP的一个版本是给定一个图和长度 L要求回答图中是否存在比 L 短的回路英语circuit或tour该问题被划分为NP完全问题已知TSP算法最坏情况下的时间复杂度随着城市数量的增多而成超多项式可能是指数英语Exponential time hypothesis级别增长 问题在年首次被形式化為最佳化中被研究得最深入的问题之一许多优化方法都奉其为基准尽管问题在计算上很困难但已经有了大量的启发式和精确方法因此可以完全求解城市数量上万的实例并且甚至能在误差范围内估计上百万个城市的问题 甚至纯粹形式的TSP都有若干应用如企划物流芯片制造稍作修改就是DNA测序等许多领域的一个子问题在这些应用中城市的概念用来表示客户焊接点或DNA片段而距离的概念表示旅行时间或成本或DNA片段之间的相似性度量TSP还被應用在天文学中减少在不同光源之间转动望远镜的时间在许多应用場景中如资源或时间窗口有限等等可能会需要加入额外的约束條件