📚 The Nearest Neighbour Algorithm | 最近邻算法
The nearest neighbour algorithm is a greedy heuristic used to find an approximate solution to the Travelling Salesman Problem (TSP). Starting from a chosen city, it repeatedly visits the closest unvisited city until all cities have been visited, then returns to the start. This approach is simple to understand and implement, making it a popular choice when an optimal solution is computationally infeasible due to the exponential growth of possibilities. In the Edexcel A-Level Computer Science specification, students are expected to apply the nearest neighbour algorithm to a given graph or distance matrix, analyse its performance, and understand its limitations as a heuristic that does not always produce the shortest possible tour.
最近邻算法是一种贪心启发式算法，用于寻找旅行商问题（TSP）的近似解。它从一个选定的城市出发，反复访问距离最近的未访问城市，直到所有城市都访问完毕，然后返回起点。该方法易于理解和实现，因此在最优解由于可能性呈指数增长而计算上不可行时，成为一种常见选择。在 Edexcel A-Level 计算机科学大纲中，学生需要能够在给定的图或距离矩阵上应用最近邻算法，分析其性能，并理解其作为启发式算法的局限性——它并不总是产生最短的可能旅程。
1. The Travelling Salesman Problem (TSP) Context | 旅行商问题背景
The Travelling Salesman Problem asks for the shortest possible route that visits a set of cities exactly once and returns to the origin city. It is a classic NP-hard problem: the number of possible tours grows factorially with the number of cities, making brute-force enumeration impractical for even moderately sized instances. Heuristics like the nearest neighbour algorithm are therefore used to find good, though not necessarily optimal, solutions in reasonable time.
旅行商问题要求找出一条访问一组城市恰好一次并返回起点的最短可能路线。它是一个经典的 NP-hard 问题：可能的旅程数量随着城市数量阶乘增长，即便对于中等规模的实例，穷举法也不切实际。因此，像最近邻算法这样的启发式方法被用来在合理时间内找到不错的（尽管不一定是最优的）解。
2. Core Idea of the Nearest Neighbour Algorithm | 最近邻算法的核心思想
The algorithm builds a tour step by step by always choosing the nearest unvisited neighbour. This local, short-sighted decision is what makes it 'greedy'. It never backtracks or considers the global structure of the tour, which can lead to suboptimal choices that accumulate into a significantly longer overall path.
该算法通过总是选择最近的未访问邻居来逐步构建旅程。这种局部的、短视的决策使它成为“贪心”的。它从不回溯，也不考虑旅程的全局结构，这可能导致次优选择的累积，从而使整体路径显著变长。
3. Algorithm Steps in Detail | 详细算法步骤
1. Choose a starting city (often arbitrary or the first in the list).
2. Mark the current city as visited.
3. Find the unvisited city that has the smallest distance from the current city.
4. Move to that city and add the distance to the total tour length.
5. Repeat steps 2–4 until all cities have been visited.
6. Finally, return to the start city from the last visited city and add that distance to the total.
1. 选择一个起始城市（通常任意或列表中的第一个）。
2. 将当前城市标记为已访问。
3. 找到与当前城市距离最小的未访问城市。
4. 移动到该城市，并将该距离加入总旅程长度。
5. 重复步骤 2–4 直到所有城市都被访问。
6. 最后，从最后一个访问的城市返回起始城市，并将该距离加入总和。
4. Worked Example on a Graph | 基于图的实例演示
Consider four cities A, B, C, D with the following distance matrix. Starting from A, we apply the nearest neighbour rule.
考虑四个城市 A、B、C、D，距离矩阵如下。从 A 出发，应用最近邻规则。
| A | B | C | D | |
|---|---|---|---|---|
| A | — | 10 | 15 | 20 |
| B | 10 | — | 35 | 25 |
| C | 15 | 35 | — | 30 |
| D | 20 | 25 | 30 | — |
B (distance 10). From B, the nearest unvisited are A (already visited), C (35) and D (25) — choose D (25). From D, unvisited are C (30) and A (20, visited) — d, return to A (15). The tour is A → B → D → C → A. Total length = 10 + 25 + 30 + 15 = 80.
逐步演示：从 A 出发，最近的未访问城市是 B（距离 10）。从 B 出发，最近的未访问城市有 A（已访问）、C（35）和 D（25）——选择 D（25）。从 D 出发，未访问的有 C（30）和 A（20，已访问）——选择 C（30）。从 C 出发，所有城市均已访问，返回 A（15）。旅程为 A → B → D → C → A。总长度 = 10 + 25 + 30 + 15 = 80。
l tour is A → B → D → C → A or A → C → B → D → A (both 80), so this particular instance happened to yield the optimal solution, but that is not guaranteed.
如果我们改为从 B 出发，可能会得到不同的旅程。最近邻算法的结果依赖于起点。在这个例子中，最优旅程是 A → B → D → C → A 或 A → C → B → D → A（都是 80），因此这个特定实例恰好得到了最优解，但这并非必然。
5. Pseudocode Representation | 伪代码表示
The algorithm can be expressed in pseudocode to highlight its iterative greedy nature. This representation is often required in Edexcel exam questions.
该算法可以用伪代码表示，以突出其迭代贪心的本质。这种表示在 Edexcel 考试题目中常常需要。
FUNCTION nearestNeighbour(graph, startCity)
tour ← [startCity]
current ← startCity
unvisited ← all cities except startCity
totalDistance ← 0
WHILE unvisited is not empty
nearest ← city in unvisited with minimum distance from current
totalDistance ← totalDistance + distance(current, nearest)
tour.append(nearest)
unvisited.remove(nearest)
current ← nearest
ENDWHILE
totalDistance ← totalDistance + distance(current, startCity)
tour.append(startCity)
RETURN tour, totalDistance
ENDFUNCTION
The pseudocode initialises the tour with the start city, then loops until every city has been visited, always selecting the closest neighbour. The final step adds the return leg. The time complexity of this procedure depends on how the minimum distance search is implemented.
伪代码以起始城市初始化旅程，然后循环直到所有城市都被访问，始终选择最近的邻居。最后一步添加返回路段。该过程的时间复杂度取决于最小距离搜索的实现方式。
6. Complexity Analysis | 复杂度分析
Let n be the number of cities. In a naive implementation, each step scans all unvisited cities to find the nearest one. The first step checks n−1 cities, the next n−2, and so on, leading to a total of O(n²) comparisons. If the graph is represented as an adjacency matrix, the overall time complexity is O(n²). Memory usage is O(n) for storing the tour and unvisited set. This is dramatically faster than the O(n!) brute-force approach, enabling the algorithm to handle hundreds or thousands of cities within seconds, whereas brute force would be impossible beyond about 20 cities.
设 n 为城市数量。在简单的实现中，每一步扫描所有未访问城市以找到最近的一个。第一步检查 n−1 个城市，下一步 n−2 个，依此类推，总比较次数为 O(n²)。如果图用邻接矩阵表示，总时间复杂度为 O(n²)。存储旅程和未访问集合的内存使用为 O(n)。这比 O(n!) 的暴力方法快得多，使得算法能在几秒内处理数百或数千个城市，而暴力法对于超过约 20 个城市就不可行了。
7. Advantages of the Nearest Neighbour Heuristic | 最近邻启发式算法的优点
Speed and simplicity — easy to code and understand, running in quadratic time.
快速且简单——易于编码和理解，以二次方时间运行。
Provides an upper bound for the optimal tour length, useful in branch-and-bound algorithms.
为最优旅程长度提供一个上界，在分支限界算法中有用。
Works on any symmetric or asymmetric distance metric that satisfies the triangle inequality, and can be applied to incomplete graphs with minor adjustments.
适用于任何满足三角不等式的对称或非对称距离度量，稍作调整也可应用于不完全图。
Deterministic for a given start point, making results reproducible and suitable for comparison.
对于给定的起点具有确定性，结果可复现，适合比较。
8. Disadvantages and Limitations | 缺点与局限性
The solution quality is highly dependent on the starting city; a poor choice can lead to a tour 25–40% longer than optimal.
解的质量高度依赖于起始城市；选择不当会导致旅程比最优解长 25–40%。
The algorithm can be forced into an early 'trap' where leaving a remote city requires a very long return leg, because all nearby cities were visited earlier.
算法可能陷入早期的“陷阱”：由于附近的所有城市都已被提前访问，从一个偏远城市离开时需要非常长的返回路径。
It does not look ahead, so it may miss obviously better global routes that require a slightly longer step now to save much more later.
它不向前看，因此可能错过明显更优的全局路线，这些路线需要现在稍长的步骤以换取日后更大的节省。
Even running the algorithm from every possible start city (repeat heuristic) does not guarantee optimality, and multiplies the time by n.
即使从每一个可能的起点运行算法（重复启发式）也不能保证最优性，并且时间会乘以 n。
9. Comparison with Optimal and Other Heuristics | 与最优解及其他启发式算法的比较
est neighbour tour can be compared with the true optimal found by brute force. On average, the greedy tour is within about 25% can be much poorer. The Christofides algorithm, also on the Edexcel specification, offers a worst-case guarantee of 1.5 times optimal for metric TSP. The nearest neighbour is often used as a baseline because it is so easy to implement, but more advanced heuristics like 2-opt or simulated annealing can refine the tour further.
对于小规模实例（n ≤ 10），最近邻旅程可以与通过穷举找到的真实最优解进行比较。平均而言，贪心旅程在最优解的约 25% 以内，但最坏情况例子可能差得多。同样在 Edexcel 大纲中的 Christofides 算法，对于度量 TSP 提供了 1.5 倍最优解的最坏情况保证。最近邻算法通常被用作基线，因为它非常容易实现，但更先进的启发式算法，如 2-opt 或模拟退火，可以进一步优化旅程。
| Feature | Nearest Neighbour | Christofides (Metric TSP) | Brute Force |
|---|---|---|---|
| Time complexity | O(n²) | O(n³) | O(n!) |
| Optimality guarantee | None | ≤ 1.5 × optimal | Exact optimal |
| Ease of implementation | Very easy | Moderate | Easy but slow |
10. Application Scenarios in Real-World Computing | 实际计算中的应用场景
Although the pure nearest neighbour algorithm rarely finds the absolute shortest route in logistics, its principles appear in many practical systems. GPS navigation devices sometimes use a variant to quickly suggest a route when exact computation is too slow. In network routing, the idea of forwarding a packet to the 'nearest' next hop that makes progress towards the destination is a related greedy concept. It is also used in cluster analysis, for example in the initialisation phase of some clustering algorithms. Moreover, the algorithm serves as an educational stepping stone to understanding more sophisticated graph traversal and optimisation techniques.
尽管纯粹的最近邻算法在物流中很少能找到绝对最短的路线，但其原理出现在许多实际系统中。当精确计算太慢时，GPS 导航设备有时会使用变体快速建议一条路线。在网络路由中，将数据包转发到离目的地“最近的”下一跳以取得进展的理念，也是一个相关的贪心概念。它还被用于聚类分析，例如在某些聚类算法的初始化阶段。此外，该算法是理解更复杂图遍历和优化技术的教育阶梯。
11. Implementation Considerations and Traps | 实现注意事项与陷阱
When coding the nearest neighbour algorithm, students should decide on a data structure for the unvisited set. A simple list yields O(n²) scans; using a priority queue or a set with fast minimum extraction could be considered but the overhead might outweigh benefits for typical exam problems. Symmetric distances must be handled consistently — if the matrix is lower-triangular, ensure indexing works correctly. Also watch out for disconnected graphs: if at some point no unvisited city is reachable, the algorithm fails unless handled gracefully. In Edexcel questions, graphs are typically complete, but partial graphs can appear. Finally, remember to add the return distance to the start city at the end.
在编写最近邻算法代码时，学生应决定未访问集合使用何种数据结构。简单的列表导致 O(n²) 扫描；可以考虑使用优先队列或支持快速提取最小值的集合，但在典型考试题目中，额外开销可能超过好处。对称距离必须处理一致——如果矩阵是下三角的，确保索引正确。还要注意不连通的图：如果在某一点没有未访问的城市可达，除非妥善处理，否则算法会失败。在 Edexcel 题目中，图通常是完全的，但也可能出现部分图。最后，记得在末尾将从最后城市返回起始城市的距离加上。
12. Key Takeaways for Edexcel A-Level Computer Science | Edexcel A-Level 计算机科学要点总结
The nearest neighbour algorithm is a greedy heuristic for TSP, constructing a tour by repeatedly moving to the closest unvisited city.
最近邻算法是针对 TSP 的贪心启发式算法，通过重复移动到最近的未访问城市来构建旅程。
It runs in O(n²) time and is simple to implement but does not guarantee an optimal solution.
它以 O(n²) 时间运行且实现简单，但不保证最优解。
The outcome depends on the chosen start city; better results may be obtained by trying all start cities.
结果取决于所选的起始城市；尝试所有起点可能获得更好的结果。
Students must be able to apply the algorithm to a distance matrix, trace the route, calculate total length, and evaluate its effectiveness as a heuristic.
学生必须能够对距离矩阵应用该算法，追踪路线，计算总长度，并评估其作为启发式算法的有效性。
The algorithm appears in the context of tractability and heuristic approaches, forming part of the broader understanding of NP-hard problems and approximate solutions.
该算法出现在可解性和启发式方法的背景下，构成了对 NP-hard 问题及近似解更广泛理解的一部分。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图