📚 The Travelling Salesman Problem | 旅行商问题
The Travelling Salesman Problem (TSP) is one of the most celebrated challenges in combinatorial optimisation. At A-Level, especially within the Edexcel Decision Mathematics module, students learn how to estimate the minimum length of a Hamiltonian cycle – a tour that visits every vertex exactly once and returns to the start – by calculating upper and lower bounds. Although TSP is extremely difficult to solve exactly for large networks (it is 'NP-hard'), the bounding techniques give us powerful tools to determine an optimal tour or at least to judge whether a given tour is acceptably close to the optimum. This article revisits every key concept you need: from the nearest neighbour algorithm for an upper bound, to the minimum spanning tree method for a lower bound, and how to combine them to prove optimality.
旅行商问题（TSP）是组合优化中最著名的难题之一。在 A-Level 课程中，特别是 Edexcel 决策数学模块，学生需要学习如何估算哈密顿圈（即访问每个顶点恰好一次并返回起点的回路）的最短长度，方法就是计算上界和下界。尽管对于大规模网络，精确求解 TSP 极其困难（属于“NP-hard”问题），但这些界定技术为我们提供了强有力的工具，可以帮助确定最优回路，或者至少判断一个给定回路是否接近最优。本文将系统回顾你所需的每一个关键概念：从求上界的最近邻算法，到用最小生成树求下界的方法，以及如何将它们结合起来证明最优性。
1. What Is the Travelling Salesman Problem? | 什么是旅行商问题？
The classical Travelling Salesman Problem asks: given a list of vertices (cities) and the weights (distances, times or costs) of travelling between every pair, find the shortest possible route that visits each vertex exactly once and returns to the starting vertex. In graph theory terms, we are looking for a minimum-weight Hamiltonian cycle in a complete graph. At Edexcel A-Level, you will almost always be given a complete distance table or a complete weighted graph, guaranteeing that every vertex is directly connected to every other. If a problem starts as a practical network where some direct connections are missing, you must first convert it into a complete table of shortest distances – this is known as converting a practical TSP into a classical TSP.
经典的旅行商问题是这样描述的：给定一组顶点（城市）以及每对顶点之间的权重（距离、时间或成本），寻找一条最短的路径，该路径访问每个顶点恰好一次并返回起点。用图论的术语来说，我们是在完全图中寻找一个权重最小的哈密顿圈。在 Edexcel A-Level 考试中，你几乎总是会拿到一张完整的距离表或者一个完全加权图，保证每个顶点之间都有直接连线。如果问题起始于一个实用网络——其中某些直接连接缺失——你必须首先将其转化为一张最短距离的完全表，这就是所谓的将实用 TSP 转化为经典 TSP。
Because the number of possible tours grows factorially, brute-force checking is impossible even for moderate numbers of vertices. Hence the syllabus focuses on efficient heuristic and bound methods rather than exhaustive listing.
由于可能回路的总数随着顶点数以阶乘形式增长，哪怕对中等数量的顶点进行暴力穷举也是不可能的。因此，教学大纲侧重于高效的启发式算法和界定方法，而非穷举罗列。
2. The Importance of Upper and Lower Bounds | 上界与下界的重要性
Any feasible tour provides an upper bound for the optimal solution – because the true minimum cannot be longer than a tour you have actually found. Conversely, a lower bound is a value that the optimal tour weight must be at least as large as. If you can find an upper bound and a lower bound that are equal, you have proved that this value is the exact length of the optimal tour. Even when the bounds are not equal, they give you a narrow interval within which the optimum must lie, and they can tell you how good your current best tour is.
任何一个可行的回路都为最优解提供了一个上界——因为真正的最短长度不可能比你实际找到的回路更长。反之，下界则是最优回路长度至少要达到的一个值。如果你能找到相等的上界和下界，你就证明了该值就是最优回路的精确长度。即使上下界不相等，它们也能给出一个最优解必须落在其中的小区间，并告诉你当前找到的最佳回路究竟有多好。
In Edexcel exams, you will typically be asked to find both the best upper bound (from several attempts) and the best lower bound (by deleting different vertices) and then to decide what you can conclude about the optimal tour length.
在 Edexcel 考试中，通常会要求你求出最佳上界（通过多次尝试）和最佳下界（通过删除不同顶点），然后判断关于最优回路长度你能得出什么结论。
3. Finding an Upper Bound: The Nearest Neighbour Algorithm | 求上界：最近邻算法
The nearest neighbour algorithm is a simple, greedy method to construct a tour. You select a starting vertex, then repeatedly move to the closest unvisited vertex. Once all vertices have been visited, you return directly to the start. The total weight of the resulting cycle gives an upper bound. It is rarely optimal by itself, but it is quick and provides a baseline.
最近邻算法是一种简单的贪心构造回路的方法。你先选择一个起始顶点，然后反复移动到最接近且尚未访问的顶点。一旦所有顶点都已访问，你就直接返回起点。所得回路的权重总和即为一个上界。它本身很少是最优的，但速度快，并能提供一个基线。
Algorithm steps:
算法步骤：
- Choose any starting vertex and mark it as visited.
- Repeat: go to the nearest unvisited vertex (if there is a tie, you may choose any), mark it visited.
- After all vertices have been visited, return to the starting vertex.
- 选择任意一个起始顶点并标记为已访问。
- 重复：移动到最近的未访问顶点（若出现平局可任意选择），标记为已访问。
- 所有顶点访问完毕后，返回起始顶点。
weight 2), then from E to D (weight 4), then D to B (weight 5), and finally back to A (weight 7). The tour A–C–E–D–B–A has total weight 3+2+4+5+7 = 21. This 21 is an upper bound for the optimal tour.
假设我们有五个顶点 A, B, C, D, E 以及一张完整的距离表。从 A 出发，最近的是 C（权重 3）。从 C 出发，最近的未访问顶点是 E（权重 2），然后从 E 到 D（权重 4），然后 D 到 B（权重 5），最后回到 A（权重 7）。回路 A–C–E–D–B–A 的总权重为 3+2+4+5+7 = 21。这个 21 就是最优回路的一个上界。
4. Finding a Better Upper Bound: Starting from Different Vertices | 求更佳上界：从不同顶点出发
The result of the nearest neighbour algorithm depends heavily on the choice of the starting vertex. By repeating the algorithm with each vertex as the start, you can obtain several tours. The smallest of their total weights is taken as the best upper bound. In exam questions, you are often told 'by using the nearest neighbour algorithm starting from each vertex, find the best upper bound'.
最近邻算法的结果高度依赖于起始顶点的选择。如果用每个顶点作为起点重复该算法，你就可以获得多个回路。其中总权重最小的那个就被视为最佳上界。在考题中，经常会出现类似“通过从每个顶点出发使用最近邻算法，求最佳上界”这样的要求。
Continuing our example, starting from B might give a tour of weight 22, starting from C might give 20, and so on. We would record the smallest, say 19. Then 19 becomes the best upper bound. Note that even the best nearest neighbour tour is not guaranteed to be optimal, but it provides an excellent reference.
延续我们的例子，从 B 出发可能给出权重为 22 的回路，从 C 出发可能给出 20，等等。我们会记录其中最小的，比如 19。那么 19 就是最佳上界。注意，即使是最好的最近邻回路也不能保证是最优解，但它提供了一个极好的参考值。
5. Lower Bound by Deleting a Vertex – Principle | 删除顶点求下界——基本原理
A widely taught method for obtaining a lower bound is to delete a vertex, find the minimum spanning tree (MST) of the remaining network, and then add the weights of the two shortest edges from the deleted vertex to the tree. The reasoning is that any Hamiltonian cycle must include two edges incident with the chosen vertex – one entering and one leaving – and the rest of the cycle, when those two edges are removed, forms a spanning tree on the remaining vertices. The weight of the cycle is therefore at least (MST of the remaining vertices) + (weights of the two cheapest edges from the deleted vertex).
求下界的一个广泛教授的方法是：删除一个顶点，求剩余网络的最小生成树（MST），然后加上从被删顶点到树上最短的两条边的权重。其推理是：任何哈密顿圈必定包含两条与所选顶点关联的边——一条进入，一条离开——而回路剩下的部分，当去掉这两条边后，就在其他顶点上形成一棵生成树。因此，回路的权重至少等于（剩余顶点的 MST）+（从被删顶点出发的最短两条边的权重）。
This value is a valid lower bound because the MST is the cheapest way to connect the remaining vertices, and you must use at least two edges from the deleted vertex. Even if the two shortest edges both attach to the same vertex, the sum is still a lower bound (it might even be smaller than the true requirement, but that is safe – it never overestimates the optimum).
这个值是一个有效的下界，因为 MST 是连接剩余顶点的最廉价方式，而且从被删顶点出发你至少得用两条边。即便这两条最短边都连在同一个顶点上，其总和仍然是一个下界（它甚至可能比实际所需还小，但这是安全的——它绝不会高估最优值）。
6. Lower Bound: Choosing Which Vertex to Delete | 下界：选择删除哪个顶点
Because the lower bound obtained can vary depending on which vertex you delete, we can calculate a lower bound by deleting each vertex in turn and then take the largest of these values as the best lower bound. If one vertex gives a bound of 16 and another gives 18, then 18 is the better (tighter) lower bound. The true optimal tour must be at least 18.
由于得到的下界可能会因删除不同顶点而有所不同，我们可以依次删除每个顶点来计算下界，然后取这些值中的最大者作为最佳下界。如果一个顶点给出的界是 16，另一个给出 18，那么 18 就是更好的（更紧的）下界。真正的最优回路长度至少为 18。
Procedure for one vertex, say A:
针对某个顶点 A 的操作步骤：
- Remove vertex A and all edges connected to it from the table or graph.
- Use Prim's or Kruskal's algorithm to find the minimum spanning tree of the remaining vertices. Record its total weight, say WMST.
- From the original table, identify the two smallest weights among all edges directly joining A to other vertices. Add these two weights to WMST. The sum is the lower bound obtained by deleting A.
- 从表格或图中移除顶点 A 以及所有与之相连的边。
- 使用普里姆算法或克鲁斯卡尔算法求出剩余顶点的最小生成树。记录其总权重，记为 WMST。
- 在原表格中，找出所有直接连接 A 与其他顶点的边中最小的两个权重。将这两个权重加到 WMST 上。总和即为删除 A 所得到的下界。
This process is repeated for B, C, etc., and the maximum result is reported as the best lower bound.
对 B, C 等重复此过程，报告其中最大值作为最佳下界。
7. Lower Bound Calculation Using a Distance Table | 利用距离表进行下界计算
Consider the following complete distance table for five vertices A, B, C, D, E. All entries are symmetric.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | - | 8 | 5 | 7 | 6 |
| B | 8 | - | 9 | 4 | 10 |
| C | 5 | 9 | - | 3 | 11 |
| D | 7 | 4 | 3 | - | 2 |
| E | 6 | 10 | 11 | 2 | - |
Suppose we delete vertex A. The remaining vertices are B, C, D, E. Using Prim's algorithm, the MST of these four vertices has edges D–E (2), D–C (3) and D–B (4), total weight 2+3+4 = 9. The two smallest edges from A are A–C (5) and A–E (6); their sum is 11. Therefore the lower bound by deleting A is 9 + 11 = 20.
假设我们删除顶点 A。剩余顶点为 B, C, D, E。使用普里姆算法，这四个顶点的 MST 包含的边为 D–E (2)、D–C (3) 和 D–B (4)，总权重 2+3+4 = 9。从 A 出发最短的两条边是 A–C (5) 和 A–E (6)，总和为 11。因此删除 A 所得到的下界为 9 + 11 = 20。
If we delete B instead, the MST of A, C, D, E might have weight 5 (A–C) + 3 (C–D) + 2 (D–E) = 10; the two smallest edges from B are B–D (4) and B– uppose deleting C gives 19, deleting D gives 21, deleting E gives 20. Then the best lower bound is max(20,22,19,21,20) = 22. Wait, the example shows we take the largest, so best lower bound is 22.
如果我们改为删除 B，剩下 A, C, D, E 的 MST 可能权重为 5 (A–C) + 3 (C–D) + 2 (D–E) = 10；从 B 出发最短的两条边为 B–D (4) 和 B–A (8)，总和 12，下界 = 22。删除 C 得 19，删除 D 得 21，删除 E 得 20。最佳下界是 max(20,22,19,21,20) = 22。
8. Classical and Practical TSP Variants | 经典与实用旅行商问题的变体
In the classical TSP, every vertex is directly connected to every other, and the weights satisfy the triangle inequality (the direct edge is never longer than a path via another vertex). In a practical TSP, the original network may not be complete, and you are allowed to revisit vertices. However, any practical problem can be converted into a classical one by constructing a complete table of shortest distances between all pairs (e.g. using Dijkstra's algorithm). Once you have that complete table, all the bounding techniques apply. The exam will either provide this complete table or ask you to derive it.
在经典 TSP 中，每个顶点之间都有直连边，并且权重满足三角不等式（直连边绝不会比经过其他顶点的路径更长）。在实用 TSP 中，原始网络可能并非完全图，并且允许重复访问顶点。然而，任何实用问题都可以通过构建所有顶点对之间的最短距离完全表（例如使用 Dijkstra 算法）转化为经典问题。一旦你有了这张完全表，所有界定技术就都能适用了。考试中要么直接提供这张完全表，要么要求你推导出来。
It is crucial to remember that when converting, you replace the network with a complete digraph (or just a weighted table) containing the shortest path distances. After that, you look for a tour in this classical representation, and the tour weight will correspond to a walk in the original network that visits all vertices.
必须牢记，在转化时，你要用包含最短路径距离的完全有向图（或直接是一张加权表）替换原网络。之后，你在这个经典表示中寻找一条回路，该回路权重将对应于在原网络中访问所有顶点的一条行走路径。
9. Determining If a Solution Is Optimal | 判断解是否最优
Once you have computed a best upper bound (say 19 from nearest neighbour) and a best lower bound (say 19 from some deletion), you can immediately conclude that the optimal tour length is exactly 19. If the lower bound is strictly less than the upper bound, you only know that the optimum lies somewhere in between. In exam questions, you might be told that a certain tour has been found – you then compute a lower bound and compare. A common task is: 'Find, using the nearest neighbour algorithm, an upper bound. Then obtain a lower bound by deleting a vertex. What can you deduce about the length of the optimal tour?'
一旦你算出了一个最佳上界（比如通过最近邻算法得到 19）和一个最佳下界（比如通过某个删除得到也是 19），你就可以立即断定最优回路长度就是 19。如果下界严格小于上界，你只能知道最优解位于两者之间的某个值。在考试题中，可能会告诉你已找到某个回路——然后你计算下界并进行比较。一个常见任务是：“使用最近邻算法求一个上界。然后通过删除一个顶点求下界。关于最优回路的长度你能推断出什么？”
Always answer with a clear concluding statement, e.g. 'Since the upper bound is 22 and the best lower bound is 21, the optimal tour length must be at least 21 and at most 22.' If they are equal, state '19 is the optimal tour length.'
回答时务必给出清晰的结论性陈述，例如“由于上界是 22，最佳下界是 21，因此最优回路长度至少为 21 且至多为 22。”如果二者相等，则说明“19 就是最优回路长度。”
10. Step-by-Step Example with Full Working | 完整例题步骤详解
Let us tackle a complete problem. Vertices: P, Q, R, S, T. Distances are given in the table below. We will find an upper bound using the nearest neighbour algorithm starting from each vertex, then a lower bound by deleting a vertex, and finally comment on the optimal value.
我们来解决一个完整的问题。顶点：P, Q, R, S, T。距离如下表所示。我们将通过从每个顶点出发使用最近邻算法求上界，然后通过删除一个顶点求下界，最后就最优值给出评论。
| P | Q | R | S | T | |
|---|---|---|---|---|---|
| P | - | 12 | 10 | 9 | 11 |
| Q | 12 | - | 8 | 15 | 7 |
| R | 10 | 8 | - | 13 | 6 |
| S | 9 | 15 | 13 | - | 14 |
| T | 11 | 7 | 6 | 14 | - |
Upper bound via nearest neighbour: Starting from P: P–S (9), S–P? No, S unvisited after first, from S, nearest unvisited is P? k at Q, R, T. Distances from S: to P=9 (visited), Q=15, R=13, T=14. Smallest is R=13. So S–R. From R: unvisited Q, T. R–T=6 (smallest), then T–Q=7. Finally Q–P=12. Tour: P–S–R–T–Q–P. Total = 9+13+6+7+12 = 47. From Q: Q–T (7), T–R (6), R–P (10), P–S (9), S–Q (15) → 7+6+10+9+15 = 47. Other starts may give smaller. Check from R: R–T (6), T–Q (7), Q–P (12), P–S (9), S–R (13) → 6+7+12+9
Published by TutorHao | A-Level Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图