旅行推销员问题
旅行商問題（英語：Travelling salesman problem, TSP）是組合最佳化中的一個 NP 困難問題，在作業研究和理論電腦科學中非常重要。問題內容為「給定一系列城市和每對城市之間的距離，求解訪問每一座城市一次並回到起始城市的最短迴路。」

TSP 是旅行購買者問題與車輛路徑問題的一種特殊情況。
作為計算複雜性理論中的一個典型的判定性問題，TSP 的一個版本是給定一個圖和長度 L，要求回答圖中是否存在比 L 短的迴路（英語：circuit 或 tour）。該問題被劃分為 NP 完全問題。已知 TSP 演算法最壞情況下的時間複雜度隨著城市數量的增多而成超多項式（可能是指數）級別增長。
問題在 1930 年首次被形式化，並且是在最佳化中研究最深入的問題之一。許多最佳化方法都用它作為一個基準。儘管問題在計算上很困難，但已經有了大量的啟發式和精確方法，因此可以完全求解城市數量上萬的實例，並且甚至能在誤差 1% 範圍內估計上百萬個城市的問題。甚至純粹形式的 TSP 都有若干應用，如企劃、物流、晶片製造。稍作修改，就是 DNA 定序等許多領域的一個子問題。在這些應用中，「城市」的概念用來表示客戶、焊接點或 DNA 片段，而「距離」的概念表示旅行時間或成本或 DNA 片段之間的相似性度量。TSP 還用在天文學中，觀察很多光源的天文學家會希望減少在不同光源之間轉動望遠鏡的時間。在許多應用場景中（如資源或時間窗口有限等等），可能會需要加入額外的約束條件。