📚 The Nearest Neighbour Algorithm | 最近邻算法
The nearest neighbour algorithm is a fast, greedy route-building method. It is particularly important in the Edexcel A Level Computer Science specification when solving the travelling salesman problem (TSP), where an exact solution is often computationally infeasible.
最近邻算法是一种快速、贪心的路径构建方法。在 Edexcel A Level 计算机科学大纲中，它在求解旅行商问题（TSP）时尤为重要，因为精确解往往在计算上不可行。
1. Overview and Exam Context | 概述与考试背景
In Edexcel A Level Computer Science, the nearest neighbour algorithm is a standard example of a greedy heuristic. It is used to produce a route, or tour, through a graph in which every pair of vertices is connected by a weighted edge. The most common application is the travelling salesman problem, where the goal is to visit every vertex exactly once and return to the start with the smallest possible total weight.
在 Edexcel A Level 计算机科学中，最近邻算法是贪心启发式算法的标准示例。它用于在每对顶点都由加权边相连的图中生成一条路线或回路。最常见的应用是旅行商问题，目标是恰好访问每个顶点一次并返回起点，使总权重尽可能小。
Exam questions may ask candidates to trace the algorithm on a distance matrix, write pseudocode, state the time complexity, or discuss why the result is not necessarily optimal. Marks are typically awarded for a clear sequence of visited vertices, the running total after each step, and a final statement of the completed tour plus its total weight.
考题可能要求考生在距离矩阵上追踪该算法、编写伪代码、说明时间复杂度，或讨论为什么结果不一定最优。评分通常看重：清晰的已访问顶点序列、每一步后的累计总权重，以及最终完整回路和总权重的结论。
Typical question stems you should recognise include the following.
你应该能识别出以下典型题干形式。
Trace the nearest neighbour algorithm starting at vertex X. | 从顶点 X 出发追踪最近邻算法。
State the time complexity of the algorithm for n vertices. | 说明该算法在 n 个顶点下的时间复杂度。
Explain why the greedy approach may not give the shortest tour. | 解释为什么贪心方法可能得不到最短回路。
Give one advantage and one disadvantage of using a heuristic here. | 说明在此使用启发式算法的一个优点和一个缺点。
2. Formal Definition and Key Terminology | 形式化定义与核心术语
The algorithm operates on a complete weighted graph. A complete graph has an edge between every pair of vertices, so a salesperson can always travel directly from any city to any other. Each edge carries a non-negative weight, which usually represents distance, travel time or cost.
该算法在完全加权图上运行。完全图中每一对顶点之间都有一条边，因此销售人员总能从任一城市直达另一城市。每条边带有一个非负权重，通常表示距离、行驶时间或成本。
A tour that visits every vertex exactly once and returns to the starting vertex is called a Hamiltonian cycle. The TSP asks for the Hamiltonian cycle of minimum total weight. Because the graph is complete, the number of distinct tours for n vertices is (n − 1)! ÷ 2 when weights are symmetric.
恰好访问每个顶点一次并回到起点的回路称为哈密顿回路。TSP 要求总权重最小的哈密顿回路。由于图是完全图，当权重对称时，n 个顶点共产生 (n − 1)! ÷ 2 条不同的回路。
Rather than drawing the graph, exam questions almost always supply a distance matrix. The entry in row i, column j is the weight of the edge from vertex i to vertex j. A symmetric matrix, where the entry in row i column j equals the entry in row j column i, represents an undirected graph; the leading diagonal contains dashes or zeros because no vertex is connected to itself.
考题几乎总是提供距离矩阵而不是图形。第 i 行第 j 列的数值即从顶点 i 到顶点 j 的边权重。若第 i 行第 j 列与第 j 行第 i 列相等，矩阵是对称的，表示无向图；主对角线为短横线或零，因为没有顶点与自身相连。
Key vocabulary to use precisely in written answers.
在书面答案中需精确使用以下术语。
| Term | 术语 | Meaning | 含义 |
| Greedy | 贪心 | Makes the best local choice at each step without looking ahead. | 每步只做当前最优选择，不考虑后续影响。 |
| Heuristic | 启发式 | A method that finds a good, not guaranteed optimal, solution quickly. | 快速找到较好但非保证最优解的方法。 |
| Tour | 回路 | A closed route visiting every vertex exactly once. | 恰好访问每个顶点一次的闭合路线。 |
| Distance matrix | 距离矩阵 | A table of edge weights between every pair of vertices. | 每对顶点之间边权重的表格。 |
3. The Algorithm Step by Step | 算法逐步流程
The nearest neighbour algorithm is easy to state. Start at a chosen vertex and record it as visited. Then repeatedly move to the unvisited vertex joined by the smallest edge weight, adding that weight to a running total as you go. When only one vertex remains unvisited, move to it, and finally close the tour by returning from the last vertex to the start.
最近邻算法的表述很简单。从选定顶点出发并标记为已访问。然后反复移动到权重最小的未访问邻接顶点，同时把该权重累加到总权重中。当只剩一个顶点未访问时，移动到它，最后从终点返回起点以闭合回路。
Formally, the steps are as follows.
形式化地，步骤如下。
Choose and visit a starting vertex. | 选择一个起始顶点并访问它。
From the current vertex, examine every edge leading to an unvisited vertex. | 从当前顶点出发，检查所有指向未访问顶点的边。
Select the edge with the smallest weight and travel along it. | 选择权重最小的边并沿其前进。
Add that weight to the running total and mark the new vertex as visited. | 将该权重累加到总权重，并标记新顶点为已访问。
Repeat from step 2 until all vertices have been visited. | 从第 2 步重复，直到所有顶点都被访问。
Add the weight of the edge from the final vertex back to the start. | 加上从最后一个顶点返回起点的边权重。
Two features of the method are worth stating explicitly in an exam answer. First, the algorithm never revisits a vertex and never backtracks; every decision is final. Second, if two unvisited vertices are equally close, any tie-breaking rule is acceptable, but you must state the rule you used so the marker can follow your trace.
有两点值得在答卷中明确指出。第一，该算法从不重复访问顶点，也从不回溯；每个决定都是最终的。第二，若两个未访问顶点距离相同，任何打破平局的规则都可接受，但你必须说明所用的规则，以便阅卷人跟上你的追踪过程。
4. Worked Example: Tracing on a Distance Matrix | 实例演示：在距离矩阵上追踪
Consider five vertices A, B, C, D and E with the symmetric distance matrix below. We will start at A and apply the algorithm exactly as an exam candidate should.
考虑五个顶点 A、B、C、D、E 及如下对称距离矩阵。我们从 A 出发，完全按考生的方式应用该算法。
| A | B | C | D | E | |
| A | – | 5 | 9 | 12 | 7 |
| B | 5 | – | 4 | 8 | 11 |
| C | 9 | 4 | – | 6 | 3 |
| D | 12 | 8 | 6 | – | 10 |
| E | 7 | 11 | 3 | 10 | – |
C (9), D (12) and E (7). The smallest is B, so we travel A → B and the running total is 5.
第 1 步：从 A 出发，候选为 B（5）、C（9）、D（12）、E（7）。最小的是 B，因此走 A → B，累计总权重为 5。
(8) and E (11). The smallest is C, so we travel B → C and the running total is 5 + 4 = 9.
第 2 步：从 B 出发，未访问候选为 C（4）、D（8）、E（11）。最小的是 C，因此走 B → C，累计总权重为 5 + 4 = 9。
(6) and E (3). The smallest is E, so we travel C → E and the running total is 9 + 3 = 12.
第 3 步：从 C 出发，未访问候选为 D（6）和 E（3）。最小的是 E，因此走 C → E，累计总权重为 9 + 3 = 12。
Step 4: only D remains, so we travel E → D with weight 10, giving 12 + 10 = 22.
第 4 步：只剩 D，因此走 E → D，权重为 10，得到 12 + 10 = 22。
Step 5: close the tour by returning D → A with weight 12, giving a final total of 34.
第 5 步：闭合回路，由 D → A，权重为 12，最终总权重为 34。
Nearest neighbour tour: A → B → C → E → D → A, total weight = 5 + 4 + 3 + 10 + 12 = 34
5. Pseudocode and Implementation Details | 伪代码与实现细节
Examiners frequently ask for pseudocode, so you should be able to reproduce the structure below from memory. The routine stores the distance matrix as a two-dimensional array indexed from 1 to n, and keeps a Boolean visited array.
考官常要求写伪代码，因此你应能凭记忆复现下面的结构。该例程把距离矩阵存为下标 1 到 n 的二维数组，并维护一个布尔型 visited 数组。
procedure NearestNeighbour(distance, n, start)
visited ← array of n Booleans, all false
current ← start
visited[start] ← true
total ← 0
tour ← [start]
for count ← 1 to n − 1
best ← ∞
nearest ← 0
for v ← 1 to n
nbsp; if visited[v] = false AND distance[current][v] < best then
best ← distance[current][v]
nearest ← v
end if
next v
visited[nearest] ← true
tour ← tour + [nearest]
total ← total + best
current ← nearest
next count
total ← total + distance[current][start]
return tour, total
end procedure
ministic and reproducible result. Use ∞ (infinity) as the initial value of best so that the first unvisited vertex is always accepted.
注意内层判断使用的是严格小于号。用 < 而不是 ≤，意味着先遇到的最近顶点在平局时胜出，结果确定且可复现。把 best 的初值设为 ∞（无穷大），以确保第一个未访问顶点总能被接受。
The final line after the loop is easy to forget: the edge that returns to the start must be added to the total. Omitting it produces a path rather than a tour and usually loses a mark.
循环之后的那一行很容易被遗忘：返回起点的边必须加入总权重。漏掉它就变成了一条路径而非回路，通常会丢分。
6. Why the Nearest Neighbour Tour Is Not Optimal | 为什么最近邻路线不一定最优
The algorithm is greedy, which means it optimises each decision in isolation. A short edge chosen early can force a very long edge later, or leave an awkward vertex that can only be reached by an expensive return leg. Because the algorithm never reconsiders earlier choices, it cannot repair such a mistake.
该算法是贪心的，即孤立地优化每一个决定。早期选择的一条短边可能迫使后期使用一条很长的边，或者留下一个只能通过昂贵返程抵达的尴尬顶点。由于算法从不重新考虑先前选择，它无法修复这类错误。
t the true optimum is 29, achieved by A → B → D → C → E → A. The heuristic is therefore about 17% han optimal in this small case, even though every individual step looked locally sensible.
在上面的实例中，从 A 出发的最近邻得到总权重 34 的回路。穷举全部十二条不同回路可知，真正的最优值是 29，对应 A → B → D → C → E → A。因此在这个小例子中，启发式结果比最优值长约 17%，尽管每一步在局部看都合理。
Two formal points are useful for higher-mark discussion questions.
对于高分论述题，有两点形式化结论很有用。
For general weighted graphs, the nearest neighbour tour can be arbitrarily worse than the optimum; there is no constant approximation ratio. | 对一般加权图，最近邻回路可能任意差于最优解；不存在常数近似比。
For metric TSP, where the triangle inequality holds, the tour length is provably O(log n) times the optimum, which is still unbounded as n grows. | 对满足三角不等式的度量型 TSP，回路长度可证明为最优值的 O(log n) 倍，但随 n 增大仍无上界。
C). Real road networks using shortest-path distances satisfy this, which is why nearest neighbour performs respectably in practice even though its worst case is bad.
三角不等式指直达不会比经中间顶点更贵；符号表示为 d(A, C) ≤ d(A, B) + d(B, C)。使用最短路径距离的真实道路网络满足该性质，这就是为什么最近邻在实践中表现尚可，尽管最坏情况很差。
7. Time and Space Complexity | 时间复杂度与空间复杂度
With a distance matrix, each of the n −
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图