![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/1/11/GLPK_solution_of_a_travelling_salesman_problem.svg/langzh-hk-640px-GLPK_solution_of_a_travelling_salesman_problem.svg.png&w=640&q=50)
旅行推銷員問題
组合优化问题 / 維基百科,自由的 encyclopedia
旅行商問題(英語:Travelling salesman problem,縮寫:TSP)是組合最佳化中的一個NP困難問題,在作業研究和理論電腦科學中非常重要。問題內容為「給定一系列城市和每對城市之間的距離,求解訪問每座城市一次並回到起始城市的最短迴路。」
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/11/GLPK_solution_of_a_travelling_salesman_problem.svg/320px-GLPK_solution_of_a_travelling_salesman_problem.svg.png)
![]() | 此條目可參照德語維基百科相應條目來擴充。 |
TSP是旅行購買者問題(英語:travelling purchaser problem)與車輛路徑問題的一種特殊情況。
作為計算複雜性理論中一個典型的判定性問題,TSP的一個版本是給定一個圖和長度 L,要求回答圖中是否存在比 L 短的迴路(英語:circuit或tour)。該問題被劃分為NP完全問題。已知TSP演算法最壞情況下的時間複雜度隨着城市數量的增多而成超多項式(可能是指數(英語:Exponential time hypothesis))級別增長。
問題在1930年首次被形式化,為最佳化中被研究得最深入的問題之一,許多最佳化方法都奉其為基準。儘管問題在計算上很困難,但已經有了大量的啟發式和精確方法,因此可以完全求解城市數量上萬的實例,並且甚至能在誤差1%範圍內估計上百萬個城市的問題。[1]
甚至純粹形式的TSP都有若干應用,如企劃、物流、晶片製造。稍作修改,就是DNA定序等許多領域的一個子問題。在這些應用中,「城市」的概念用來表示客戶、焊接點或DNA片段,而「距離」的概念表示旅行時間或成本或DNA片段之間的相似性度量。TSP還被應用在天文學中,減少在不同光源之間轉動望遠鏡的時間。在許多應用場景中(如資源或時間窗口有限等等),可能會需要加入額外的約束條件。