📚 The Classical and Practical Travelling Salesman Problems | 经典与实用旅行商问题
The travelling salesman problem is one of the most important optimisation problems in decision mathematics. It asks for the cheapest closed route that starts at a given point, visits a set of locations, and returns to the starting point. In the Edexcel specification, the problem is studied in two forms: the classical travelling salesman problem, where every vertex must be visited exactly once, and the practical travelling salesman problem, where repeated visits are allowed because the network may not be complete.
旅行商问题是决策数学中最重要的优化问题之一。它要求找出一条成本最低的闭合路线：从给定点出发，访问一组地点后返回起点。在Edexcel考试大纲中，该问题分为两种形式：经典旅行商问题要求每个顶点恰好访问一次；实用旅行商问题则允许重复访问，因为实际网络可能不是完全图。
1. What Is the Travelling Salesman Problem? | 什么是旅行商问题？
The travelling salesman problem, often abbreviated as TSP, is a routing problem in a weighted network. A salesperson must leave a home city, visit a list of cities, and return home. The aim is to make the total distance or cost as small as possible.
旅行商问题通常缩写为TSP，是加权网络中的路线问题。销售员必须离开出发城市，访问一系列城市后回家。目标是使总距离或总成本尽可能小。
In Edexcel Decision Mathematics, a solution is called a tour or Hamiltonian cycle if it visits every vertex exactly once and returns to the start. The classical and practical versions differ in how strictly this ‘exactly once’ rule is applied.
在Edexcel决策数学中，如果一条路线恰好访问每个顶点一次并返回起点，则称为一条回路或哈密顿回路。经典版和实用版在“恰好访问一次”这一规则的严格程度上有所不同。
2. Classical TSP: Definition and Assumptions | 经典TSP：定义与假设
The classical travelling salesman problem assumes a complete network. This means there is a direct edge between every pair of vertices. Each edge has a known weight, such as distance, time, or cost, and the network is usually undirected and symmetric.
经典旅行商问题假设网络是完全的。这意味着任意两个顶点之间都有一条直接的边。每条边都有已知的权重，例如距离、时间或成本，并且网络通常是无向且对称的。
A valid classical tour is a Hamiltonian cycle. It must visit every vertex exactly once and return to the starting vertex. The objective is to find the Hamiltonian cycle with the smallest total weight.
一条有效的经典回路是哈密顿回路。它必须恰好访问每个顶点一次并返回起始顶点。目标是找到总权重最小的哈密顿回路。
For a complete graph with n vertices, there are (n − 1)! / 2 possible Hamiltonian cycles if the graph is undirected. Checking every cycle quickly becomes impractical, so algorithms such as nearest neighbour and minimum spanning tree bounds are used.
对于有n个顶点的完全无向图，共有(n − 1)! / 2条可能的哈密顿回路。逐条检查很快就会变得不现实，因此通常使用最近邻算法和最小生成树下界等方法。
3. Practical TSP: When the Network Is Not Complete | 实用TSP：网络不完整时
In real applications, the network often is not complete. Some pairs of locations may have no direct road or rail link. The practical travelling salesman problem allows the route to travel along any available edges and to visit vertices more than once.
在实际应用中，网络往往不是完全的。某些地点之间可能没有直接的道路或铁路连接。实用旅行商问题允许路线使用任意可用边，并且可以多次经过顶点。
The only requirements are that the route must visit every vertex at least once, return to the starting vertex, and have the smallest possible total weight. A practical route is therefore not necessarily a Hamiltonian cycle.
唯一的要求是路线必须至少访问每个顶点一次，返回起始顶点，并且总权重尽可能小。因此，实用路线不一定是哈密顿回路。
4. Converting a Practical TSP into a Classical TSP | 将实用TSP转化为经典TSP
A practical travelling salesman problem can be converted into a classical travelling salesman problem by building a complete shortest-distance table. First, use Dijkstra’s algorithm to find the shortest path between every pair of vertices in the original network.
实用旅行商问题可以通过构建完全最短距离表转化为经典旅行商问题。首先，使用Dijkstra算法求出原网络中每对顶点之间的最短路径。
Record these shortest distances in a square table. This table is complete because every pair of vertices now has a value. The shortest distances also satisfy the triangle inequality, which means the direct table value between two vertices is no greater than any indirect route through another vertex.
将这些最短距离记录在方阵表格中。因为任意两个顶点现在都有一个数值，所以该表格是完全的。最短距离还满足三角不等式，即两个顶点之间的表格值不大于经过其他顶点的任何间接路线。
Once the complete shortest-distance table is formed, solve it as a classical TSP. Each selected edge in the classical tour corresponds to a shortest path in the original practical network, so the route can be translated back.
一旦形成完全最短距离表，就可以按经典TSP求解。经典回路中选定的每条边对应原实用网络中的一条最短路径，因此可以将路线翻译回原网络。
5. Finding an Upper Bound with the Nearest Neighbour Algorithm | 用最近邻算法求上界
Any valid tour gives an upper bound for the optimal tour length. The nearest neighbour algorithm is a quick constructive method. It starts at a chosen vertex, then repeatedly moves to the nearest unvisited vertex, and finally returns to the start.
任何有效回路都给出最优回路长度的上界。最近邻算法是一种快速的构造方法。它从选定的顶点出发，然后反复移动到最近的未访问顶点，最后返回起点。
The total weight of this tour is an upper bound. Starting from different vertices can produce different tours, so it is useful to try several starting points and take the smallest resulting tour as the best upper bound.
该回路的总权重就是一个上界。从不同顶点出发可能得到不同的回路，因此通常应尝试几个起点，并取所得回路中最小的一个作为最佳上界。
For a nearest neighbour tour T, we write:
对于最近邻回路T，可写为：
Upper bound = total weight of T
6. Finding a Lower Bound Using a Minimum Spanning Tree | 用最小生成树求下界
A lower bound can be calculated by deleting one vertex, say A. In any Hamiltonian cycle, the part connecting all vertices except A must contain a spanning tree of those remaining vertices. Therefore its weight is at least the weight of the minimum spanning tree, or MST, on the remaining vertices.
下界可以通过删除一个顶点（例如A）来计算。在任意哈密顿回路中，连接除A以外所有顶点的部分必然包含这些剩余顶点的一棵生成树。因此，其权重至少等于剩余顶点上最小生成树（MST）的权重。
The tour must also enter and leave A using two distinct edges. The total weight of these two edges is at least the sum of the two smallest edges incident to A. This gives the formula:
回路还必须使用两条不同的边进出A。这两条边的总权重至少等于与A关联的两条最小边的权重之和。由此得到公式：
Lower bound = MST weight on V − {A} + two smallest edge weights from A
This value is a lower bound for the optimal classical tour length. For practical TSP, the same calculation is applied to the complete shortest-distance table.
该值是经典最优回路长度的下界。对于实用TSP，同样的计算应用于完全最短距离表。
7. Choosing the Best Lower Bound | 选择最佳下界
Since any vertex can be deleted in the lower bound calculation, you should repeat the process for several different vertices. The largest lower bound obtained is the most useful, because it is closest to the optimal value.
由于在下界计算中可以删除任意顶点，因此应对多个不同顶点重复该过程。所得的最大下界最有用，因为它最接近最优值。
If an upper bound and a lower bound are equal, the corresponding tour is proven optimal. This is an important technique in exam questions that ask you to justify optimality.
如果上界与下界相等，则对应的回路被证明是最优的。这是考试题中要求证明最优性的重要技巧。
8. Worked Example: Classical TSP | 经典TSP例题
Five vertices A, B, C, D, E have the following symmetric distance table in kilometres:
五个顶点A、B、C、D、E的对称距离表如下，单位为公里：
| A | B | C | 更多咨询请联系16621398022（同微信）
CommentsMore posts |
|---|
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply