The Travelling Salesman Problem | 旅行商问题

📚 The Travelling Salesman Problem | 旅行商问题

The Travelling Salesman Problem (TSP) is one of the most famous problems in Decision Mathematics. It asks: given a set of cities and the distances between them, what is the shortest possible route that visits every city exactly once and returns to the starting city? Despite its simple formulation, the TSP belongs to a class of problems known as NP-hard, meaning that no efficient algorithm is currently known to solve it exactly for large numbers of cities.

旅行商问题（TSP）是决策数学中最著名的问题之一。它提出：给定一组城市及它们之间的距离，访问每个城市恰好一次并返回出发城市的最短可能路线是什么？尽管其表述简单，TSP 属于被称为 NP-hard 的一类问题，这意味着目前尚无已知的高效算法能够精确求解大量城市的 TSP。

1. The Problem Statement | 问题表述

In its classical form, the Travelling Salesman Problem can be stated as follows: a salesman must visit a number of cities, starting and ending at his home city. He must visit each city exactly once, and he must minimise the total distance travelled. In graph-theoretic terms, the task is to find the minimum weight Hamiltonian cycle in a complete weighted graph.

在经典形式下，旅行商问题可以表述如下：一位推销员必须访问若干城市，从家乡城市出发并最终返回。他必须恰好访问每个城市一次，并且必须使总行程距离最小。用图论的术语来说，任务是在一个完全加权图中找到最小权重的哈密顿回路。

For example, consider four cities A, B, C and D. The salesman starts at A, visits B, C and D in some order, and returns to A. There are (4−1)!/2 = 3 distinct Hamiltonian cycles to consider. Even for just 10 cities, there are (10−1)!/2 = 181,440 possible cycles. For 20 cities, the number exceeds 6 × 10¹⁶, far too many to check exhaustively.

例如，考虑四个城市 A、B、C 和 D。推销员从 A 出发，按某种顺序访问 B、C 和 D，然后返回 A。需要考虑 (4−1)!/2 = 3 条不同的哈密顿回路。仅对于 10 个城市，就有 (10−1)!/2 = 181,440 种可能的回路。而对于 20 个城市，这个数字超过 6 × 10¹⁶，数量之庞大，无法穷举检查。

2. Classical vs Practical TSP | 经典与实际旅行商问题

In the Edexcel A-Level syllabus, two versions of the TSP are distinguished. The classical TSP requires each vertex to be visited exactly once. The practical (or realistic) TSP allows vertices to be revisited, meaning we seek the shortest route that visits every vertex at least once. In the practical version, the shortest route will always be a Hamiltonian cycle if the graph satisfies the triangle inequality: the direct distance between two vertices is always less than or equal to the distance via any intermediate vertex.

在 Edexcel A-Level 大纲中，区分了两种版本的旅行商问题。经典 TSP 要求每个顶点恰好被访问一次。实际（或现实）TSP 允许顶点被重复访问，这意味着我们寻找的是访问每个顶点至少一次的最短路线。在实际版本中，如果图满足三角不等式：两点之间的直接距离总是小于或等于经由任何中间顶点的距离，则最短路线始终是哈密顿回路。

The difference matters because in real-world road networks, the shortest route between two cities may pass through another city. In such cases, the practical TSP route might naturally pass through a city without ‘visiting’ it, so the Hamiltonian cycle constraint can be relaxed. Exam questions often specify which version to use, so read carefully.

这一区别之所以重要，是因为在现实道路网络中，两个城市之间的最短路线可能经过另一个城市。在这种情况下，实际 TSP 路线可能自然地经过某个城市而无需专门访问，因此哈密顿回路的约束可以放宽。考试题目通常会指明使用哪个版本，请仔细阅读。

3. Hamiltonian Cycles and Complete Graphs | 哈密顿回路与完全图

A Hamiltonian cycle is a cycle that visits every vertex of a graph exactly once and returns to the starting vertex. A complete graph, denoted Kₙ, is a graph in which every pair of distinct vertices is connected by an edge. In a complete graph with n vertices, the number of distinct Hamiltonian cycles is (n−1)!/2.

哈密顿回路是访问图中每个顶点恰好一次并返回起始顶点的回路。完全图，记作 Kₙ，是每对不同顶点之间都有一条边相连的图。在有 n 个顶点的完全图中，不同哈密顿回路的总数为 (n−1)!/2。

Number of Hamiltonian cycles in Kₙ = (n−1)!/2

Note that rotations of the same cycle are considered identical, since starting at a different vertex does not create a new cycle. Reversing the direction of travel also yields the same cycle, which is why we divide by 2.

请注意，同一回路的旋转被视为相同的，因为从不同顶点出发并不会产生新的回路。反转行进方向也得到同一回路，这就是为什么我们需要除以 2。

In the Edexcel exam, you will typically work with graphs of 5 to 7

Published by TutorHao | A-Level Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）