📚 The Classical and Practical Travelling Salesman Problems | 经典与实用旅行商问题
The Travelling Salesman Problem (TSP) is a cornerstone of decision mathematics, asking for the shortest possible route that visits every vertex in a network exactly once and returns to the start. In Edexcel A-Level Decision Mathematics, you encounter two distinct flavours: the classical TSP on a complete graph, and the practical TSP where the graph may be incomplete and edge weights represent real-world distances or times. Understanding both, and the algorithms that bound the optimal tour, is essential for exam success.
旅行商问题（TSP）是决策数学的基石，它要求找出一条最短路径，访问网络中的每个顶点恰好一次并返回起点。在Edexcel A-Level决策数学中，你会遇到两种不同的类型：完全图上的经典TSP，以及图可能不完全且边权代表实际距离或时间的实用TSP。理解这两者以及界定最优巡回的算法，是考试成功的关键。
1. Introduction to the Travelling Salesman Problem | 旅行商问题简介
The TSP sets out to minimise the total distance (or cost/time) of a tour that visits every vertex exactly once and returns to the starting vertex. In graph theory terms, we are looking for a Hamiltonian cycle of minimum total weight. The problem is famous because, as the number of vertices n grows, the number of possible tours grows as (n−1)!/2, making complete enumeration impractical even for moderately sized networks.
TSP旨在最小化一个巡回的总距离（或成本/时间），该巡回访问每个顶点恰好一次并返回起点。在图论术语中，我们寻找一个总权重最小的哈密顿圈。这个问题之所以著名，是因为随着顶点数n的增长，可能的巡回数按 (n−1)!/2 增长，即使对于中等规模的网络，完全列举也不可行。
2. The Classical TSP: Hamiltonian Cycles | 经典TSP：哈密顿圈
In the classical TSP, we assume the network is a complete graph, meaning every pair of vertices is directly connected by an edge. The weight of each edge is given, and the graph obeys the triangle inequality – direct routes are never longer than going via another vertex. You will typically work from a table of distances. The goal is to find a Hamiltonian cycle that gives the minimum total weight, or at least to find upper and lower bounds for the optimal tour length.
在经典TSP中，我们假设网络是完全图，即每对顶点之间都有直接的边相连。每条边的权重是给定的，且图满足三角不等式——直接路线决不会比经过另一顶点更长。你通常会根据距离表来解题。目标是找到一个总权重最小的哈密顿圈，或者至少找出最优巡回长度的上界和下界。
3. Finding a Lower Bound: Using Minimum Spanning Tree | 寻找下界：利用最小生成树
A simple lower bound can be found by removing one vertex, say A, and finding a minimum spanning tree (MST) for the remaining vertices. The two shortest edges from A to this tree are then added. This sum provides a lower bound. Repeating the process by removing a different vertex gives another lower bound; the best (largest) of these lower bounds is taken. This method works because any tour must include a path through the n−1 vertices that forms a spanning tree, plus two edges connecting the vertex removed to that tree.
一个简单的下界可以通过移除一个顶点（比如A），并找出剩余顶点的最小生成树（MST）来得到。然后将从A到该树的两条最短边加进去。这个总和就是一个下界。重复此过程，移除不同的顶点会得到另一个下界；取这些下界中最佳（最大）的那个。这个方法之所以有效，是因为任何巡回必须包含一条穿过n−1个顶点且构成生成树的路径，再加上两条将移除的顶点与该树连接起来的边。
Lower bound = weight of MST on {all vertices except X} + two smallest edges incident to X
下界 = 除X外所有顶点上的最小生成树权重 + 与X关联的两条最小边
4. Upper Bounds and Heuristic Algorithms | 上界与启发式算法
An upper bound is any valid tour, found by a heuristic (quick method). The nearest neighbour algorithm and the use of minimum spanning tree doubling are common. The optimal tour lies between the best lower bound and the smallest upper bound. In exams, you might be asked to find an upper bound by applying the nearest neighbour algorithm starting from a specified vertex.
上界是任何有效的巡回，通过启发式算法（快速方法）找到。最近邻算法和最小生成树加倍法都是常用的。最优巡回位于最佳下界与最小上界之间。在考试中，你可能会被要求从指定顶点出发，应用最近邻算法来找到一个上界。
5. The Nearest Neighbour Algorithm | 最近邻算法
Starting from a chosen vertex, move to the nearest unvisited vertex. Repeat until all vertices have been visited, then return directly to the start. This gives a tour. The length of this tour is an upper bound for the optimal solution. To improve the bound, you can repeat the algorithm from different starting vertices and take the shortest tour found. The algorithm is 'greedy' — it may not find the optimal tour but is very fast.
从一个选定的顶点出发，移动到最近的未访问顶点。重复此步骤直到所有顶点都已访问，然后直接返回起点。这就得到一个巡回。该巡回的长度即为最优解的一个上界。为改进此上界，你可以从不同起点重复该算法，并取所得最短巡回。该算法是“贪婪”的——它可能找不到最优巡回，但速度非常快。
6. The Practical TSP: Real-World Constraints | 实用TSP：现实约束
The practical TSP relaxes the assumption of a complete graph. The network may be a road map where direct connections do not exist between all pairs of vertices. Edge weights might represent actual distances, driving times, or costs, and they must satisfy the triangle inequality in the underlying metric. The main challenge is that the shortest path between two vertices may pass through other vertices, so you first need to construct a complete table of shortest distances.
实用TSP放宽了完全图的假设。网络可能是一张道路图，其中并非所有顶点对之间都有直接连接。边权重可以代表实际距离、行驶时间或成本，且它们必须满足底层度量的三角不等式。主要挑战在于两个顶点之间的最短路径可能经过其他顶点，因此你首先需要构建一个最短距离的完全表。
7. Road Networks and Incomplete Graphs | 道路网络与不完全图
Consider a network of towns connected by roads where each edge is marked with a time or distance. The graph is likely to be incomplete, and a direct edge between two towns might not exist. To apply TSP algorithms, you must turn this incomplete graph into a complete graph of shortest travel times. This is done using Dijkstra's algorithm to find the shortest path between every pair of vertices.
考虑一个由道路连接的城镇网络，每条边标注了时间或距离。该图很可能是不完全的，两个城镇之间可能不存在直接的边。为应用TSP算法，你必须将这个不完全图转化为最短行驶时间的完全图。这需要使用Dijkstra算法找出每对顶点之间的最短路径。
8. Converting a Network into a Complete Table of Distances | 将网络转化为完全距离表
The conversion process involves applying Dijkstra's algorithm to each vertex as the source, or systematically working out the shortest distances using the network's weights. Once you have the complete table of shortest distances, the practical TSP reduces to the classical TSP. You then find upper and lower bounds using the methods described earlier, but now the entries in your table are the shortest path lengths, not necessarily direct edges.
转换过程包括对每个顶点作为源点应用Dijkstra算法，或利用网络权重系统地计算出最短距离。一旦你有了最短距离的完全表，实用TSP就简化为经典TSP。然后你使用前述方法找出上界和下界，但此时表中的条目是最短路径长度，而不一定是直接边的权重。
9. The Route Inspection Problem Connection | 路径检查问题的联系
Students often confuse the TSP with the Route Inspection Problem (Chinese Postman Problem). The TSP seeks a tour visiting every vertex once, while the route inspection problem seeks a route covering every edge at least once. In practical TSP, you may first need to consider whether a network needs to be made Eulerian for a postman, but for the travelling salesman, the focus is on vertices, not edges. A clear distinction is essential for the exam.
学生们经常将TSP与路径检查问题（中国邮差问题）混淆。TSP寻求一个访问每个顶点一次的巡回，而路径检查问题寻求一条至少覆盖每条边一次的路线。在实用TSP中，你可能首先需要考虑是否要为邮差构造欧拉图，但对于旅行商，重点是顶点而非边。清晰区分两者对考试至关重要。
10. Solving Practical TSPs by Using Shortest Paths | 通过最短路径求解实用TSP
Once the complete distance table is built, solving the practical TSP follows the same steps: find a lower bound by deleting a vertex and using MST on the remainder, adding the two cheapest connectors. Find an upper bound via nearest neighbour on the complete table. The actual tour may involve revisiting vertices when you translate the sequence back onto the original network, because the shortest path between two vertices might pass through a vertex already visited in the tour sequence. This is allowed in the practical interpretation – you are covering the vertices, and you may pass through a vertex again on the ground.
一旦构建了完全距离表，求解实用TSP就遵循同样的步骤：通过删除一个顶点并对剩余顶点使用MST，加上两个最便宜的连接边来找到下界。通过在完全表上使用最近邻算法找到上界。当你将序列转换回原始网络时，实际的巡回可能涉及重复访问顶点，因为两个顶点间的最短路径可能经过巡回序列中已经访问过的顶点。在实用解释中这是允许的——你是在覆盖这些顶点，并且在地面上你可能再次经过某个顶点。
11. Comparison: Classical vs Practical TSP | 经典与实用TSP比较
The classical TSP starts with a complete graph where edges obey the triangle inequality, and a tour visits each vertex exactly once. The practical TSP starts with an incomplete graph representing real roads; you must first compute shortest paths to create a complete table. The optimal tour in the practical TSP is the shortest route that visits each vertex at least once, which is equivalent to the classical TSP on the shortest-distance complete graph. Exam questions often include a table of direct distances that already satisfies the triangle inequality, but you may be asked to explain how the table would be derived from a practical network.
经典TSP从一个完全图开始，边满足三角不等式，巡回访问每个顶点恰好一次。实用TSP从代表真实道路的不完全图开始；你必须先计算最短路径来创建完全表。实用TSP中的最优巡回是访问每个顶点至少一次的最短路线，这等价于最短距离完全图上的经典TSP。考试题通常包括一个已经满足三角不等式的直接距离表，但你可能需要解释该表格如何从实用网络中推导出来。
| Aspect | Classical TSP | Practical TSP |
| Graph | Complete, weighted | Often incomplete (real map) |
| Data given | Direct distance table or matrix | Network diagram with weights |
| First step | Can apply algorithms directly | Build complete table of shortest distances |
| Tour meaning | Visits each vertex exactly once | Visits each vertex at least once; may repeat vertices on shortest paths |
| 方面 | 经典TSP | 实用TSP |
| 图 | 完全，加权 | 通常不完全（真实地图） |
| 给定数据 | 直接距离表或矩阵 | 带权网络图 |
| 第一步 | 可直接应用算法 | 构建最短距离完全表 |
| 巡回含义 | 访问每个顶点恰好一次 | 至少访问每个顶点一次；在最短路径上可能重复顶点 |
12. Exam Tips and Common Pitfalls | 考试技巧与常见错误
Always check whether you are dealing with a classical or practical context. If a table is given, verify the triangle inequality – if an entry looks too large compared to a two-step journey, it might be impractical, but usually tables in classical TSP already obey it. When finding lower bounds, be systematic: delete each vertex in turn, record the bound, select the maximum. For the nearest neighbour algorithm, show your working clearly by stating the order of vertex selection and the cumulative weight. When a practical network is presented, draw a clear complete table of shortest distances before applying TSP heuristics. Do not apply nearest neighbour directly to the original graph unless it is already complete and shortest distances are given.
始终要检查你面对的是经典还是实用情境。如果给出了表格，请验证三角不等式——如果某个条目相比两步路线看起来过大，它可能不实用，但经典TSP中的表格通常已经满足。在寻找下界时，要有条理：依次删除每个顶点，记录下界，选择最大值。对于最近邻算法，要清楚展示你的解题过程，注明顶点选择的顺序和累积权重。当给出实用网络时，要在应用TSP启发式算法之前画出一个清晰的最短距离完全表。切勿直接在原始图上应用最近邻算法，除非该图本身已是完全图且给出了最短距离。
Published by TutorHao | Decision Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图