The Traveling Salesman Problem and Route Planning | 旅行商问题与路径规划

📚 The Traveling Salesman Problem and Route Planning | 旅行商问题与路径规划

The Traveling Salesman Problem (TSP) is one of the most famous problems in computer science. It asks a deceptively simple question: given a set of cities and the distances between every pair of them, what is the shortest possible route that visits every city exactly once and returns to the starting city?

旅行商问题（TSP）是计算机科学中最著名的问题之一。它提出了一个看似简单的问题：给定一组城市以及任意两座城市之间的距离，能够访问每座城市恰好一次并返回出发城市的最短路线是什么？

TSP is central to route planning, logistics, and algorithm design. It is also a classic example of an NP-hard problem, which means no efficient algorithm is known for solving every large instance quickly.

TSP 是路径规划、物流和算法设计的核心问题。它也是 NP-hard 问题的经典例子，这意味着目前没有已知的高效算法可以在短时间内求解所有大规模实例。

1. The Formal Definition | 正式定义

Formally, we are given a complete graph G = (V, E), where V is a set of n cities or vertices, and every edge (u, v) has a non-negative weight w(u, v) representing the travel distance, time, or cost. The goal is to find a Hamiltonian cycle, a closed loop that visits each vertex exactly once, with the minimum total weight.

形式化地说，我们给定一个完全图 G = (V, E)，其中 V 是包含 n 个城市或顶点的集合，并且每一条边 (u, v) 都有一个非负权重 w(u, v)，表示行驶距离、时间或成本。目标是找到一个哈密顿回路，即一条访问每个顶点恰好一次并返回起点的闭合环路，且总权重最小。

The objective can be written as:

目标可以写成：

minimize w(v₁, v₂) + w(v₂, v₃) + … + w(vₙ, v₁)

where v₁, v₂, …, vₙ is a permutation of all vertices. The notation vₙ + 1 means returning to the starting vertex.

其中 v₁, v₂, …, vₙ 是所有顶点的一个排列。符号 vₙ₊₁ 表示返回起点。

2. Complexity of TSP | TSP 的复杂度

If there are n cities, how many possible tours exist? For the first city, there are n choices, but because a cyclic rotation of the same tour is identical, and travelling in the reverse direction gives the same total distance, the number of distinct tours is:

如果有 n 个城市，一共有多少种可能的旅行路线？对于第一个城市，有 n 个选择，但由于同一路线的循环旋转实际上是同一条路线，而且反向旅行的总距离相同，因此不同路线的数量为：

Tours = (n − 1)! / 2

For n = 10 cities, there are 181,440 distinct tours. For n = 20 cities, there are about 1.2 × 10¹⁷ tours. This factorial explosion makes brute-force search impossible for large n.

对于 n = 10 个城市，存在 181,440 条不同路线。对于 n = 20 个城市，大约有 1.2 × 10¹⁷ 条路线。这种阶乘爆炸使得大规模情形下的暴力搜索无法实现。

In formal complexity theory, the decision version of TSP is NP-complete, and the optimisation version is NP-hard. This means that if someone found a polynomial-time algorithm for TSP, it would solve all problems in the NP complexity class.

在形式化复杂性理论中，TSP 的决策版本是 NP-complete，而优化版本是 NP-hard。这意味着如果有人找到了 TSP 的多项式时间算法，那么 NP 复杂性类中的所有问题都可以被解决。

3. Why TSP Matters | 为什么 TSP 很重要

TSP is not just a theoretical puzzle; it appears in many practical engineering and business systems.

TSP 不仅是理论上的谜题；它出现在许多实际的工程和商业系统中。

Logistics and delivery: A courier truck must visit many customers and return to the depot, minimising fuel and time.

物流与配送：快递卡车必须访问多个客户并返回仓库，以最小化燃油和时间。
Manufacturing: In printed circuit board drilling, a machine must drill holes at many positions; the shortest tool path saves production time.

制造业：在印刷电路板钻孔中，一台机器必须在许多位置钻孔；最短的刀具路径可以节省生产时间。
Biology: DNA sequencing and genome assembly can be modelled as TSP instances on overlapping DNA fragments.

生物学：DNA 测序和基因组组装可以被建模为重叠 DNA 片段上的 TSP 实例。
Route planning apps: Multi-stop navigation in mapping software often solves a practical version of TSP with traffic constraints.

路径规划应用：地图软件中的多目的地导航通常求解带有交通约束的 TSP 实用版本。

4. Brute-Force Search | 暴力搜索

The simplest exact method is brute-force enumeration: generate every possible Hamiltonian cycle, calculate its total distance, and keep the minimum. This method always finds the optimal answer, but its time complexity is O(n!), which makes it unusable when n is large.

最简单的精确方法是暴力枚举：生成每一条可能的哈密顿回路，计算其总距离，并保留最小值。这种方法总能找到最优答案，但其时间复杂度为 O(n!)，当 n 较大时不可用。

For n = 50, the number of tours is far greater than the number of atoms in the observable universe, so brute-force is only practical for very small n.

对于 n = 50，路线数量远超可观测宇宙中的原子数量，因此暴力搜索只适用于很小的 n。

In examination questions, you may be asked to solve a small TSP instance by hand, usually with 4 or 5 cities, by listing all distinct routes. For such small inputs, brute force is acceptable.

在考试题目中，你可能会被要求通过手算求解一个小的 TSP 实例，通常是 4 或 5 个城市，方法是列出所有不同路线。对于这种小型输入，暴力搜索是可以接受的。

5. The Nearest Neighbour Heuristic | 最近邻启发式

Because exact solutions are expensive, computer scientists use heuristics to find good, though not always optimal, solutions quickly. One simple heuristic is the nearest neighbour algorithm.

由于精确解代价高昂，计算机科学家使用启发式算法来快速找到良好的解，虽然不一定是最优解。一种简单的启发式算法是最近邻算法。

Starting from a chosen city, repeatedly move to the nearest unvisited city. When no unvisited cities remain, return to the starting city. This greedy strategy runs in O(n²) time and is easy to implement.

从选定城市出发，反复移动到最近的未访问城市。当没有未访问城市时，返回到起点城市。这种贪心策略的运行时间为 O(n²)，并且易于实现。

However, nearest neighbour can produce poor results. It often leaves a very long edge for the final return, because it only thinks about the next step and not the overall structure of the tour.

然而，最近邻算法可能产生较差的结果。它常常在最后返回时留下一条非常长的边，因为它只考虑下一步，而不考虑整体路线结构。

Example: in a route with cities clustered in two groups, nearest neighbour may jump back and forth between groups, creating a twisted, inefficient path.

例如：在城市分成两组的路线中，最近邻算法可能会在两组之间来回跳跃，形成曲折且低效的路径。

6. Local Search and 2-Opt | 局部搜索与 2-opt

A powerful improvement is called 2-opt. Given an existing tour, we remove two edges and reconnect the path in the opposite order. If the new tour is shorter, we keep it. This process is repeated until no further improvement is found.

一种强大的改进方法称为 2-opt。给定现有路线，我们移除两条边并以相反顺序重新连接路径。如果新路线更短，则保留它。重复此过程，直到找不到进一步改进。

The 2-opt move is easy to understand: if a tour crosses itself, 2-opt removes the crossing and creates a shorter non-crossing tour. In most Euclidean TSP instances, the optimal tour does not cross itself, so 2-opt often brings a good solution close to optimal.

2-opt 操作很容易理解：如果一条路线出现交叉，2-opt 会移除交叉并形成更短的无交叉路线。在大多数欧几里得 TSP 实例中，最优路线不会自我交叉，因此 2-opt 通常能使好的解接近最优。

2-opt is a local search method. It guarantees a local optimum, but not necessarily the global optimum. For larger instances, a better starting tour is first built using nearest neighbour, and then 2-opt is applied to improve it.

2-opt 是一种局部搜索方法。它保证得到局部最优，但不一定是全局最优。对于较大实例，首先使用最近邻算法构建初始路线，然后应用 2-opt 进行改进。

7. Christofides and Approximation Guarantees | Christofides 与近似保证

Another famous approach is the Christofides algorithm, which gives a route whose total length is at most 1.5 times the optimal length. It uses a minimum spanning tree, a perfect matching on odd-degree vertices, and then traverses a resulting Eulerian graph, shortcutting repeated vertices.

另一个著名方法是 Christofides 算法，它给出总长度最多为最优长度 1.5 倍的路线。该算法使用最小生成树、对奇度顶点的完美匹配，然后遍历由此产生的欧拉图，并对重复顶点进行捷径处理。

For the metric TSP, where distances obey symmetry and the triangle inequality, Christofides is a polynomial-time 1.5-approximation algorithm. This is often an exam-worthy distinction: an approximation algorithm has a proven worst-case bound, while a heuristic only has an empirical expectation of good performance.

对于度量 TSP，在距离满足对称性和三角不等式时，Christofides 是一种多项式时间的 1.5 近似算法。这一点在考试中很有价值：近似算法具有可证明的最坏情况界，而启发式算法只有经验上的良好表现预期。

The triangle inequality states that the direct edge from A to C is never longer than the path A to B plus B to C. This property holds for standard road distances.

三角不等式是指从 A 到 C 的直接边永远不会长于从 A 到 B 再加上从 B 到 C 的路径。对于标准道路距离，这个性质成立。

8. Exact Dynamic Programming: Held-Karp | 精确动态规划：Held-Karp 算法

Although TSP is NP-hard, optimal solutions can be found for moderate n using dynamic programming. The Held-Karp algorithm defines a state as (S, j), where S is a subset of cities already visited, and j is the last city visited.

虽然 TSP 是 NP-hard，但使用动态规划可以求解中等规模的 n。Held-Karp 算法将状态定义为 (S, j)，其中 S 是已经访问过的城市子集，j 是最后访问的城市。

The recurrence is:

递推关系为：

dp(S, j) = min over i in S \ {j} of dp(S \ {j}, i) + w(i, j)

The base case is dp({j}, j) = w(start, j), and the final answer is the minimum over j of dp(V, j) + w(j, start). This algorithm runs in O(n² 2ⁿ) time, which is much better than O(n!) for n around 20 to 25.

基础情况是 dp({j}, j) = w(start, j)，最终答案是所有 j 中 dp(V, j) + w(j, start) 的最小值。该算法运行时间为 O(n²2ⁿ)，对于 n 约为 20 到 25 时远优于 O(n!)。

The Held-Karp algorithm is important because it shows that sometimes we can use extra memory to reduce time. It requires O(n2ⁿ) memory, which is still large, but much more practical than brute-force enumeration for many real-world subproblems.

Held-Karp 算法很重要，因为它表明有时我们可以用额外内存来减少时间。它需要 O(n2ⁿ) 内存，这仍然很大，但对于许多现实世界的子问题而言，比暴力枚举实际得多。

9. Route Planning and Shortest Path Algorithms | 路径规划与最短路径算法

Many students confuse TSP with the shortest path problem. The shortest path problem, solved by Dijkstra’s algorithm and the A* search algorithm, finds the best single route from one source node to one destination node.

许多学生将 TSP 与最短路径问题混淆。最短路径问题由 Dijkstra 算法和 A* 搜索算法解决，目标是找到从单个源节点到单个目标节点的最佳单一路线。

Dijkstra’s algorithm runs efficiently in polynomial time because it does not need to visit every node. It explores nodes in increasing order of distance from the start until the destination is reached.

Dijkstra 算法可以在多项式时间内高效运行，因为它不需要访问每个节点。它按照从起点出发距离递增的顺序探索节点，直到到达目的地。

In contrast, TSP requires a complete loop visiting all nodes. Repeatedly applying Dijkstra to connect cities in arbitrary order does not solve TSP, because we must also decide the order of visitation, not just the route between two points.

相比之下，TSP 要求访问所有节点的完整回路。反复应用 Dijkstra 以任意顺序连接城市并不能解决 TSP，因为我们还必须决定访问顺序，而不仅仅是两点之间的路线。

Problem	Goal	Complexity
Shortest path / 最短路径	Find shortest route from S to T / 找到从 S 到 T 的最短路线	Polynomial / 多项式
TSP / 旅行商问题	Find shortest cycle visiting all cities / 找到访问所有城市的最短回路	NP-hard / NP-hard

10. Branch and Bound | 分支定界法

Another exact solution method is branch and bound. The algorithm searches through possible partial tours and uses a lower bound to prune branches that cannot improve the current best solution.

另一种精确求解方法是分支定界法。该算法搜索可能的局部路线，并使用下界来剪除无法改进当前最优解的分支。

For a TSP, a simple lower bound is the cost of a minimum spanning tree on the remaining unvisited cities, plus the cost of entering and leaving the current city. If this lower bound is already greater than the best-known tour, that branch is discarded.

对于 TSP，一个简单的下界是剩余未访问城市的最小生成树代价，加上进入和离开当前城市的代价。如果该下界已经大于已知最佳路线，则该分支被丢弃。

Branch and bound can solve larger instances than brute force, but its worst-case time complexity is still exponential. In exams, you may only need to explain the idea of a lower bound and why pruning reduces the search space.

分支定界法可以求解比暴力搜索更大的实例，但其最坏情况时间复杂度仍然是指数级的。在考试中，你可能只需要解释下界的想法以及剪枝为何减少搜索空间。

11. Real-World TSP Variants | 现实世界中的 TSP 变体

In practice, route planning rarely deals with the pure TSP. Real systems include constraints such as time windows, vehicle capacity, one-way streets, traffic congestion, and multiple vehicles.

在实践中，路径规划很少处理纯 TSP。现实系统包含诸如时间窗口、车辆容量、单行道、交通拥堵和多车辆等约束。

For example, the Vehicle Routing Problem (VRP) involves multiple vehicles starting from a depot. The Travelling Salesman Problem with Time Windows (TSPTW) adds a deadline for each city. These variants are even more difficult than the original TSP.

例如，车辆路径问题（VRP）涉及从仓库出发的多辆车辆。带时间窗口的旅行商问题（TSPTW）为每个城市增加了截止时间。这些变体比原始 TSP 更加困难。

Modern mapping software combines TSP heuristics with real-time data. It may first use a greedy construction to produce an initial route, then improve it with 2-opt or larger k-opt moves, and finally adjust the route based on live traffic information.

现代地图软件将 TSP 启发式算法与实时数据结合。它可能首先使用贪心构造生成初始路线，然后使用 2-opt 或更大的 k-opt 操作进行改进，最后根据实时交通信息调整路线。

12. Exam Tips for TSP Questions | TSP 考题要点

In a computer science exam, TSP questions usually test definitions, complexity, and small manual calculations rather than advanced mathematics. You should be able to explain why TSP is NP-hard and why exact algorithms become useless as n grows.

在计算机科学考试中，TSP 题目通常测试定义、复杂性和小型手算，而不是高等数学。你应该能够解释为什么 TSP 是 NP-hard，以及为什么随着 n 增长精确算法变得无用。

Know that a Hamiltonian cycle is a cycle that visits every vertex exactly once.

知道哈密顿回路是访问每个顶点恰好一次的回路。
Be able to compute the number of distinct tours using (n − 1)! / 2.

能够使用 (n − 1)! / 2 计算不同路线的数量。
Know that nearest neighbour is greedy, fast, but not guaranteed optimal.

知道最近邻算法是贪心的、快速的，但不保证最优。
Know that Christofides has a proven 1.5 approximation factor for metric TSP.

知道 Christofides 对度量 TSP 具有可证明的 1.5 近似因子。
Distinguish between shortest path algorithms and TSP: Dijkstra solves point-to-point routing, while TSP solves multi-stop tour planning.

区分最短路径算法与 TSP：Dijkstra 解决点对点路径，而 TSP 解决多站点路线规划。
When solving a 4-city TSP by hand, fix the starting city and check all remaining permutations, remembering to divide by 2 for the reverse direction.

当手算 4 城市 TSP 时，固定起点并检查所有剩余排列，记得对反向路线除以 2。

The most important takeaway is that TSP demonstrates a central theme in computer science: for some problems, finding an optimal solution is too slow, so we must decide between exact algorithms for small inputs and heuristics or approximation algorithms for large inputs.

最重要的观点是，TSP 展示了计算机科学中的核心主题：对于某些问题，寻找最优解太慢，因此我们必须决定是使用适合小规模输入的精确算法，还是使用适合大规模输入的启发式算法或近似算法。

By understanding TSP, you also understand why route planning systems use a combination of mathematics and engineering trade-offs. The shortest route in theory is not always the fastest route in practice, but TSP provides the foundation for all multi-stop path optimisation.

通过理解 TSP，你也理解了为什么路径规划系统使用数学与工程权衡的组合。理论上的最短路线在实践中不一定是最快路线，但 TSP 为所有多站点路径优化提供了基础。

Published by TutorHao | 计算机 Revision Series | aleveler.com

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

The Traveling Salesman Problem and Route Planning | 旅行商问题与路径规划