Traveling Salesman Problem

定义 Definition

“旅行商问题”（TSP）是计算机科学与运筹学中的经典优化问题：给定一组城市及它们两两之间的距离，要求找出一条最短路线，使旅行商从某个城市出发，恰好访问每个城市一次并最终回到起点。它是著名的 NP 困难问题；也有许多变体（如不必回到起点、距离不对称等）。

发音 Pronunciation (IPA)

/ˈtrævəlɪŋ ˈseɪlzmən ˈprɑːbləm/

例句 Examples

We used the traveling salesman problem to model the shortest route to visit all our delivery points.
我们用旅行商问题来建模访问所有配送点的最短路线。

Although the traveling salesman problem looks simple, finding the exact optimal tour can become computationally infeasible as the number of cities grows.
尽管旅行商问题看起来简单，但随着城市数量增加，寻找精确的最优回路在计算上可能变得难以承受。

词源 Etymology

该术语直译为“旅行推销员问题”。“salesman（推销员）”指过去常见的上门或跨城推销人员；设定为“要跑遍多个城市再回到起点”，用来形象化“路线最短”的实际需求。作为数学/算法问题，它在20世纪中期的运筹学与组合优化研究中逐步定型，并成为展示“看似容易、实则难算”的代表性问题之一。

相关词 Related Words

• Optimization
• Algorithm
• Graph
• Hamiltonian Cycle
• NP-hard
• Heuristic
• Approximation
• Combinatorial

文学与经典著作 Literary Works

• Computers and Intractability: A Guide to the Theory of NP-Completeness（Garey & Johnson）——以TSP作为经典NP困难问题的代表进行讨论。
• The Traveling Salesman Problem: A Computational Study（Lawler, Lenstra, Rinnooy Kan, Shmoys 等编）——专门系统研究TSP的经典文集。
• The Design of Approximation Algorithms（Williamson & Shmoys）——在近似算法语境下多次以TSP作为核心例题。
• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein）——在算法与复杂性相关章节中常以TSP作为典型案例出现。