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