Using the Nearest Neighbour Algorithm to Find an Upper Bound | 使用最近邻算法求上界

📚 Using the Nearest Neighbour Algorithm to Find an Upper Bound | 使用最近邻算法求上界

In many optimisation problems, especially the travelling salesman problem, we need a quick way to estimate the best possible solution without trying every possible route. The nearest neighbour algorithm is a simple greedy heuristic that constructs a complete Hamiltonian cycle and therefore provides an upper bound for the optimal tour length.

在许多优化问题中，尤其是旅行商问题，我们需要一种快速方法来估计最优解，而不必尝试每一条可能路线。最近邻算法是一种简单的贪心启发式算法，它构造一个完整的哈密顿回路，因此为最优回路长度提供了一个上界。

1. The Travelling Salesman Problem and Bounds | 旅行商问题与界限

The travelling salesman problem (TSP) asks for the shortest closed route that visits every vertex exactly once and returns to the starting vertex. This shortest route is called the optimal tour. In a minimisation problem, any feasible route gives an upper bound because the optimal tour cannot be longer than a route we have actually found.

旅行商问题要求找到一条最短的闭合路线，访问每个顶点恰好一次并返回起点。这条最短路线称为最优回路。在最小化问题中，任意可行路线都给出一个上界，因为最优回路的长度不可能大于我们已经找到的一条路线。

To narrow the search, we often look for a lower bound and an upper bound. If a lower bound is L and an upper bound is U, the optimal tour length T* satisfies L ≤ T* ≤ U.

为了缩小搜索范围，我们通常寻找下界和上界。如果下界为 L，上界为 U，则最优回路长度 T* 满足 L ≤ T* ≤ U。

2. What the Nearest Neighbour Algorithm Does | 最近邻算法做什么

The nearest neighbour algorithm builds a route by a greedy rule: from the current vertex, move to the nearest unvisited vertex. This is repeated until all vertices have been visited, and then the route returns to the starting vertex.

最近邻算法通过一条贪心规则构建路线：从当前顶点出发，移动到最近的未访问顶点。重复此过程，直到所有顶点都已访问，然后路线返回起始顶点。

Because the method always chooses the smallest immediate distance, it is fast and easy to apply by hand or program. However, being greedy does not guarantee the global optimum; it only guarantees a valid Hamiltonian cycle.

由于该方法总是选择当前最小的距离，因此无论是手工计算还是编程都十分快捷。但它只保证生成一个有效的哈密顿回路，并不保证全局最优。

3. Why It Produces an Upper Bound | 为什么它给出上界

Once the nearest neighbour process finishes, the output is a closed cycle that visits every vertex exactly once. This is a feasible solution to the travelling salesman problem. Since the optimal tour is the minimum over all feasible Hamiltonian cycles, its length must be less than or equal to the length of this constructed cycle.

最近邻过程完成后，输出是一个闭合回路，每个顶点恰好访问一次。这是旅行商问题的一个可行解。由于最优回路是所有可行哈密顿回路中长度最小的，因此最优回路的长度一定小于或等于这个构造出来的回路长度。

If the nearest neighbour tour has length U, then the optimal tour length T* satisfies T* ≤ U. This is why the result is called an upper bound.

如果最近邻回路长度为 U，那么最优回路长度 T* 满足 T* ≤ U。这就是该结果被称为上界的原因。

Do not confuse this with a lower bound: the nearest neighbour does not prove that no shorter route exists; it only gives a known feasible route.

不要将其与下界混淆：最近邻算法并不能证明不存在更短的路线，它只是给出一个已知的可行路线。

4. Step-by-Step Procedure | 分步流程

Use the following steps when applying the nearest neighbour algorithm to a distance table or complete graph.

在距离表或完全图上应用最近邻算法时，请使用以下步骤。