📚 Using the nearest neighbour algorithm to find an upper bound | 使用最近邻算法寻找上界
The travelling salesman problem challenges us to find the shortest possible route that visits every location exactly once and returns to the start. Exhaustive search becomes impossible for large datasets, so heuristic methods like the nearest neighbour algorithm are used to quickly produce a feasible tour. That tour's total distance provides an upper bound for the optimal solution — a key concept in Edexcel A-Level Computer Science.
旅行商问题要求找到一条访问每个地点恰好一次并返回起点的最短路线。对于大规模数据，穷举搜索变得不可行，因此像最近邻算法这样的启发式方法被用来快速产生一个可行的行程。该行程的总距离为最优解提供了一个上界——这是Edexcel A-Level计算机科学中的一个关键概念。
1. The Travelling Salesman Problem and Upper Bounds | 旅行商问题与上界
The Travelling Salesman Problem (TSP) is a classic optimisation challenge. Given a list of cities and the distances between each pair, the goal is to determine the shortest Hamiltonian cycle — a circuit that visits every city exactly once and returns to the starting point. In decision mathematics and computer science, we often talk about bounds for the optimal tour length. An upper bound is any value that is guaranteed to be greater than or equal to the optimal solution. Any complete tour we construct gives such an upper bound because the true shortest tour cannot be longer than a tour we have actually found.
旅行商问题是一个经典的优化挑战。给定一个城市列表以及每对城市之间的距离，目标是确定最短的哈密顿回路——一条访问每个城市恰好一次并返回起点的回路。在决策数学和计算机科学中，我们经常讨论最优行程长度的界。上界是任何保证大于或等于最优解的值。我们构造的任何完整行程都提供了这样一个上界，因为真正的最短行程不可能比我们已经找到的行程更长。
2. What Is a Heuristic Algorithm? | 什么是启发式算法？
A heuristic is a problem-solving technique that sacrifices optimality, completeness, or accuracy for speed. In the context of TSP, an exact algorithm would check all permutations, which is O(n!). The nearest neighbour algorithm is a greedy heuristic: it makes the locally best choice at each step without worrying about the global optimum. It does not guarantee the optimal solution, but it quickly yields a reasonably short tour, which serves as an upper bound for the true shortest tour.
启发式是一种为速度而牺牲最优性、完备性或精确性的问题求解技术。在TSP的背景下，精确算法会检查所有排列，时间复杂度为O(n!)。最近邻算法是一种贪心启发式：它在每一步做出局部最优选择，而不考虑全局最优。它不能保证最优解，但能快速产生一个相当短的行程，这可以作为真正最短行程的上界。
3. The Nearest Neighbour Algorithm Explained | 最近邻算法详解
The nearest neighbour algorithm builds a tour by starting at a chosen vertex. At each step, it moves to the closest unvisited vertex. Once all vertices have been visited, it returns directly to the starting vertex. The algorithm can be summarised as: (1) Select a starting vertex. (2) Mark it as visited. (3) Find the nearest unvisited vertex and go there, adding the edge weight to the total distance. (4) Repeat step 3 until all vertices are visited. (5) Return to the start, adding the distance from the final vertex back to the starting vertex. The order of visits forms the tour, and the total distance is the length of that tour, which is an upper bound for the optimal TSP solution.
最近邻算法通过从选定顶点出发构建行程。每一步，它移动到最近且尚未访问的顶点。当所有顶点都被访问后，它直接返回起始顶点。该算法可以概括为：(1) 选择起始顶点。(2) 将其标记为已访问。(3) 找到最近的未访问顶点并移动到那里，将边的权重加到总距离上。(4) 重复步骤3直到所有顶点都被访问。(5) 返回起点，加上从最后一个顶点回到起点的距离。访问的顺序构成行程，总距离即为该行程的长度，这是TSP最优解的一个上界。
4. Step-by-Step Example (Starting from Vertex A) | 分步示例（从顶点A开始）
Consider a small network with four vertices A, B, C, D and the following symmetric distance matrix:
考虑一个包含四个顶点A、B、C、D的小型网络，距离矩阵如下（对称）：
| A | B | C | D | |
|---|---|---|---|---|
| A | - | 10 | 15 | 20 |
| B | 10 | - | 35 | 25 |
| C | 15 | 35 | - | 30 |
| D | 20 | 25 | 30 | - |
e C (35) and D (25). Choose D (distance 25). Total: 35. From D, only C remains unvisited (30). Add 30. Total: 65. Finally, return to A from C: distance 15. Total tour length = 10 + 25 + 30 + 15 = 80. The tour is A → B → D → C → A.
从A开始。未访问的邻居有B(10)、C(15)、D(20)。最近的是B（距离10）。访问B。目前总距离：10。在B处，未访问的顶点为C(35)和D(25)。选择D（距离25）。总距离：35。在D处，只剩下C未访问(30)。加30。总距离：65。最后，从C返回A：距离15。总行程长度 = 10 + 25 + 30 + 15 = 80。行程为A → B → D → C → A。
5. Calculating the Tour Length and Upper Bound | 计算行程长度和上界
le has length ≤ 80. In this example, the actual optimum might be A → B → D → C → A (which we found) or perhaps A → C → B → D → A with length 15+35+25+20 = 95 (worse). By inspection, A → C → D → B → A would be 15+30+25+10 = 80 as well, so the optimal length is at most 80, and possibly exactly 80. The key point is that the nearest neighbour result provides a quick, computable upper bound that we can use to evaluate other tours or prune searches.
最近邻行程的总距离80是TSP最优解行程长度的一个上界。这意味着真正的最短哈密顿回路长度 ≤ 80。在这个例子中，实际最优解可能就是我们找到的A → B → D → C → A，或者可能是A → C → B → D → A，长度为15+35+25+20 = 95（更差）。通过观察，A → C → D → B → A的长度也是15+30+25+10 = 80，所以最优长度至多为80，很可能就是80。关键点在于最近邻结果提供了一个快速、可计算的上界，我们可以用它来评估其他行程或进行剪枝搜索。
6. Impact of Starting Vertex on the Upper Bound | 起始顶点对上界的影响
ore different upper bounds. In our example, starting from B might yield a different tour. From B, nearest unvisited is A (10) or D (25) — choose A. From A, nearest unvisited is C (15) or D (20) — . From A, nearest is B (10). From B, only D remains (25). Return to C (30). Tour: C → A → B → D → C, length = 15+10+25+30 = 80. All give 80, but in other networks the differences can be significant. Taking the smallest upper bound from several starting points improves the bound.
最近邻算法的结果取决于所选的起始顶点。不同的起点可能导致不同的行程，从而导致不同的上界。在我们的例子中，从B开始可能产生不同的行程。从B出发，最近未访问的是A(10)或D(25)——选择A。从A，最近未访问的是C(15)或D(20)——选择C。从C，仅剩D(30)。从D返回B(25)。行程：B → A → C → D → B，长度为10+15+30+25 = 80。从C开始：最近未访问的是A(15)。从A，最近的是B(10)。从B，仅剩D(25)。返回C(30)。行程：C → A → B → D → C，长度为15+10+25+30 = 80。在这个网络中所有起点都得80，但在其他网络中差异可能很大。从多个起点中取最小的上界可以改进上界。
7. Nearest Neighbour on a Complete Graph | 完全图上的最近邻算法
For a complete graph where every pair of vertices is directly connected, the nearest neighbour algorithm works seamlessly. At each vertex, you simply scan all unvisited vertices to find the one with the smallest edge weight. If multiple neighbours share the same minimum distance, you can choose any of them arbitrarily; this may affect the final tour. In exam questions, the convention is usually to pick the first alphabetically if a tie occurs, but be sure to state your decision rule.
对于每对顶点都直接相连的完全图，最近邻算法可以无缝工作。在每个顶点，只需要扫描所有未访问的顶点，找到边权最小的那个。如果多个邻居具有相同的最小距离，可以任意选择其中一个；这可能会影响最终的行程。在考试题目中，如果出现平局，惯例通常是按字母顺序选择第一个出现的地点，但一定要说明你的选择规则。
8. Nearest Neighbour on a Weighted Table (Distance Matrix) | 基于加权表（距离矩阵）的最近邻算法
When a distance matrix is provided, you can trace the algorithm row by row. Start in the row of the initial vertex. Look across columns for the smallest value among unvisited vertices. After selecting the next vertex, cross out its column to indicate it is visited, but be careful because the return journey will later be read from the distance matrix using the final vertex's row back to the start. Many students find it helpful to keep a list of visited vertices and a running total.
当给出距离矩阵时，可以逐行追踪算法。首先查看起始顶点所在的行，在未访问顶点对应的列中寻找最小的值。选择下一个顶点后，将其列划掉以表示已访问，但要小心，因为返回行程将根据最后访问顶点的行读回到起点的距离。许多学生发现，保持已访问顶点列表和累计距离是很有帮助的。
9. Advantages and Limitations of Nearest Neighbour | 最近邻算法的优点与局限性
Advantages: (1) Extremely fast, with O(n²) time complexity for n vertices. (2) Simple to implement and understand. (3) Immediately yields an upper bound that can be used in branch-and-bound or to assess other solutions. Limitations: (1) It is a greedy algorithm and often misses shorter global routes, especially if early choices lead to long final edges. (2) The tour length can vary greatly with the starting point. (3) It does not guarantee optimality; the upper bound may be far from the true optimum. Despite this, it remains a valuable heuristic for quickly generating an upper bound in TSP contexts.
优点：(1) 速度极快，对于n个顶点时间复杂度为O(n²)。(2) 实现和理解简单。(3) 立即产生一个上界，可用于分枝定界法或评估其他解。局限性：(1) 它是一种贪心算法，常常错过更短的全局路径，特别是如果早期选择导致最后的长边。(2) 行程长度可能因起点不同而差异很大。(3) 它不能保证最优性；上界可能与真正最优解相差甚远。尽管如此，它仍然是在TSP情境中快速生成上界的一种有价值的启发式。
10. Improving Upper Bounds with Different Starting Points | 通过不同起点改进上界
To find a tighter upper bound, you can run the nearest neighbour algorithm from each possible starting vertex and take the smallest resulting tour length. For a large network this might be computationally expensive if done exhaustively, but often a few well-chosen starting points suffice. In Edexcel exam questions, you may be asked to repeat the algorithm for two different starts and then state which gives the better upper bound. Remember, the best upper bound is the smallest tour length you have actually constructed.
为了找到更紧的上界，可以从每一个可能的起始顶点运行最近邻算法，然后取所得行程长度的最小值。对于大型网络，若穷尽所有起点可能计算量较大，但通常选取几个精心挑选的起点就足够了。在Edexcel考试题目中，可能会要求你对两个不同的起点重复执行算法，然后说明哪一个给出了更好的上界。请记住，最好的上界是你实际构造出的行程长度中的最小值。
11. Exam Tips for Edexcel A-Level Computer Science | Edexcel A-Level计算机科学的应试技巧
e the final return leg; circle or underline the final tour length and state clearly that it is an upper bound. If the question asks 'Find an upper bound for the optimal tour' tour clearly, e.g., A → B → D → C → A. If a tie occurs, explain your tie-breaker, such as 'choose the first alphabetically' nd . Also, be prepared to compare this upper bound with a lower bound obtained from a minimum spanning tree if required in the same paper.
在回答最近邻算法问题时，始终做到：展示顶点被选择的顺序；记录每一步增加的边距；包含最后的返回边；圈出或下划线标注最终的行程长度，并明确指出它是一个上界。如果题目要求“找出最优行程的一个上界”，期望的答案就是该行程长度。不要忘记清晰地标注你的行程，例如A → B → D → C → A。如果出现平局，解释你的打破平局规则，如“按字母顺序选择第一个”。另外，如果同一份试卷中要求，还要做好将这个上界与从最小生成树得到的下界进行比较的准备。
12. Summary and Key Points | 总结与关键点
The nearest neighbour algorithm is a greedy heuristic that quickly builds a feasible TSP tour. Its tour length is an upper bound for the optimal tour length because the true shortest tour cannot be longer than a known possible tour. Running the algorithm from different starting vertices can produce different bounds; the smallest of these is the tightest upper bound we can obtain by this method. Understanding this concept is essential for Edexcel A-Level Computer Science, where heuristic algorithms and optimisation bounds feature prominently in algorithm analysis questions.
最近邻算法是一种贪心启发式方法，能快速构建一个可行的TSP行程。其行程长度是最优行程长度的一个上界，因为真正的最短行程不可能比一个已知的可能行程更长。从不同的起始顶点运行该算法可以产生不同的界；其中最小的就是通过此方法能得到的最紧上界。理解这一概念对Edexcel A-Level计算机科学至关重要，因为启发式算法和优化界限在算法分析题中占有突出地位。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图