旅行推销员问题
组合优化问题 / 維基百科,自由的 encyclopedia
親愛的 Wikiwand AI, 讓我們通過簡單地回答這些關鍵問題來保持簡短:
你能列出最重要的事實和統計數據嗎 旅行推销员问题?
為 10 歲的孩子總結這篇文章
顯示所有問題
旅行商问题(英語: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还被應用在天文学中,减少在不同光源之间转动望远镜的时间。在许多应用場景中(如资源或时间窗口有限等等),可能会需要加入额外的约束條件。