📚 Using a Minimum Spanning Tree Method to Find a Lower Bound | 利用最小生成树方法求下界
In the study of decision mathematics, particularly when tackling the classic Travelling Salesman Problem (TSP), finding efficient ways to estimate the optimal tour length is crucial. One powerful technique involves using a minimum spanning tree (MST) to calculate a lower bound for the shortest possible Hamiltonian cycle. This method not only gives us a benchmark for evaluating possible solutions but also forms a key part of the branch-and-bound algorithm you may encounter in your Edexcel course.
在学习决策数学的过程中，特别是解决经典旅行商问题（TSP）时，寻找有效的方法来估计最优回路长度至关重要。一种强有力的技术是利用最小生成树（MST）来计算最短可能的哈密顿回路的长度下界。这种方法不仅为我们提供了评估可能解的一个基准，也是你在Edexcel课程中可能会遇到的分支定界算法的关键部分。
1. Introduction to the Travelling Salesman Problem and Bounds | 旅行商问题与界限简介
The Travelling Salesman Problem asks for the shortest closed tour that visits every vertex of a weighted graph exactly once and returns to the start. Since the number of possible tours grows factorially, finding the exact optimum often becomes impractical. This is where bounds come into play: an upper bound gives a tour length that might not be optimal but is achievable, while a lower bound guarantees that no tour can be shorter than that value.
旅行商问题要求找出一条最短的闭合回路，该回路访问带权图中的每个顶点恰好一次并返回起点。由于可能的回路数量呈阶乘增长，找到精确的最优解往往不现实。这时候界限就派上用场了：上界给出一个可能不是最优但可以实现的回路长度，而下界则保证没有任何回路能比这个值更短。
Knowing both bounds helps us assess how close our current best solution is to the theoretical minimum. If the upper bound equals the lower bound, we have found the optimal tour. Even when they differ, a tighter lower bound can prune unpromising branches during systematic search methods.
同时知道这两个界限有助于我们评估当前最佳解与理论最小值的接近程度。如果上界等于下界，我们就找到了最优回路。即使它们不同，一个更紧的下界也能在系统搜索方法中剪除掉没有希望的分支。
2. The Concept of a Lower Bound | 下界的概念
A lower bound for the TSP is a number L such that the length of any valid Hamiltonian cycle is greater than or equal to L. The challenge is to compute a value that is as large as possible (tight), without overestimating the true minimum. A weak lower bound is easy to obtain, but a tight one provides real insight and practical help in optimization.
旅行商问题的下界是一个数L，使得任何合法的哈密顿回路的长度都大于或等于L。挑战在于计算出一个尽可能大（紧）而又不会高估真实最小值的下界。一个弱下界很容易得到，但一个紧的下界才能真正提供洞见并在优化中起到实际帮助。
The minimum spanning tree method cleverly exploits the structure of any optimal tour: if you remove one vertex from the tour, what remains must be a path that visits all the other vertices. The length of that path is at least the weight of the MST on those vertices, and the two edges connecting the removed vertex to the path add extra cost. This observation directly yields our lower bound formula.
最小生成树方法巧妙地利用了任何最优回路的结构：如果你从回路中移除一个顶点，剩下的必定是一条访问所有其他顶点的路径。该路径的长度至少是这些顶点上的最小生成树的权重，而连接被移除顶点与这条路径的两条边则增加了额外的代价。这一观察直接得出了我们的下界公式。
3. Why Use a Minimum Spanning Tree? | 为何使用最小生成树？
A minimum spanning tree of a graph connects all vertices with the smallest total edge weight and contains no cycles. In the context of the TSP, if we delete one specified vertex, the remaining part of any tour must form a spanning tree on the rest of the vertices—in fact, it's a path, which is a special kind of tree. The MST weight is therefore a minimal estimate for that portion of the tour.
一个图的最小生成树以最小的总边权连接所有顶点，且不包含环。在旅行商问题的上下文中，如果我们删除一个指定的顶点，任何回路剩余的部分必定构成剩余顶点上的一棵生成树——事实上它是一条路径，也就是一种特殊的树。因此，最小生成树的权重就是对这部分回路的最小估计。
Using the MST is computationally efficient thanks to Prim's or Kruskal's algorithms, which run in polynomial time. By adding the two cheapest edges incident to the deleted vertex, we obtain a valid lower bound without having to examine the factorial number of possible tours.
得益于普里姆算法或克鲁斯卡尔算法，使用最小生成树的计算效率很高，这些算法在多项式时间内运行。通过加上与被删除顶点相关联的两条最便宜边，我们就能得到一个有效的下界，而无需遍历阶乘数量级的可能回路。
4. Step 1: Choose a Vertex to Remove | 步骤1：选择一个顶点删除
The first action is to select one vertex from the complete graph and temporarily remove it, along with all its incident edges. The choice can be arbitrary—you might start with vertex A for convenience. However, different choices will often produce different lower bounds, so in practice you may need to compute bounds for several vertices and select the maximum.
第一个动作是从完全图中选择一个顶点，并将它以及与之关联的所有边暂时移除。这个选择可以是任意的——为了方便，你可以从顶点A开始。然而，不同的选择往往会得出不同的下界，因此实践中你可能需要为多个顶点计算下界，并选择最大值。
In the Edexcel examination, the question might specify which vertex to remove, or ask you to find the best lower bound by trying all possibilities. Mark schemes value clear labeling and systematic working. Remember, deleting a vertex essentially breaks the tour, and we will later stitch it back intelligently.
在Edexcel考试中，题目可能会指定移除哪个顶点，或者要求你尝试所有可能以找到最佳下界。评分标准重视清晰的标注和系统性的演算。请记住，删除顶点实质上打断了回路，我们稍后会聪明地将其重新缝合。
5. Step 2: Find the Minimum Spanning Tree of the Remaining Graph | 步骤2：寻找剩余图的最小生成树
With the chosen vertex gone, you are left with a complete graph on n-1 vertices. Use either Kruskal's or Prim's algorithm to find a minimum spanning tree (MST) for this reduced network. List the edges in order of increasing weight, and add them one by one, skipping any that would create a cycle, until all remaining vertices are connected.
在所选顶点被移除后，你将得到一个在n-1个顶点上的完全图。使用克鲁斯卡尔算法或普里姆算法为这个缩小的网络找到一棵最小生成树（MST）。按权重递增的顺序列出所有边，并逐一添加，跳过任何会形成环的边，直到所有剩余顶点都被连接起来。
The total weight of these selected edges is denoted as w(MST). This value alone represents the absolute minimum needed to connect the remaining vertices, though a TSP tour will always require a little more. Note that the MST itself is not a tour; it’s simply a lower bound component.
这些被选边的总权重记作 w(MST)。这个数值本身就代表了连接剩余顶点所需的绝对最小值，尽管一个旅行商回路总会需要多一点点。请注意，最小生成树本身并不是一条回路；它只是一个下界组成部分。
6. Step 3: Identify the Two Shortest Edges from the Removed Vertex | 步骤3：识别被删顶点的两条最短边
Return to the original graph and look at all edges that connected the removed vertex to the others. From this list, select the two edges with the smallest weights. Label them as e₁ and e₂, with weights w(e₁) and w(e₂). These two edges are the cheapest way to link the deleted vertex into any spanning structure of the rest.
回到原图，查看所有连接被删除顶点与其他顶点的边。从这个列表中选出权重最小的两条边。将它们标记为 e₁ 和 e₂，权重分别为 w(e₁) 和 w(e₂)。这两条边是将被删顶点连接到其他顶点的任何生成结构中最便宜的方式。
Why two edges? Because in any Hamiltonian cycle, each vertex has degree 2. After removal, the two edges that originally connected the deleted vertex must be part of the tour. Therefore, adding their weights is necessary, and picking the two smallest gives the least possible addition, ensuring we still maintain a valid lower bound.
为什么是两条边？因为在任何哈密顿回路中，每个顶点的度数都是2。在移除之后，最初连接被删除顶点的两条边必定是回路的一部分。因此，加上它们的权重是必要的，而选择最小的两条边给出了尽可能小的增加值，确保我们仍然保持一个有效的下界。
7. Step 4: Calculate the Lower Bound | 步骤4：计算下界
The lower bound is obtained by combining the MST weight with the two shortest incident edges:
LB(Deleted Vertex) = w(MST) + w(e₁) + w(e₂)
This sum provides a guaranteed minimum length for any complete tour. It is a true lower bound because any valid tour must contain a spanning tree on the reduced vertex set (worth at least w(MST)) and two edges from the removed vertex (worth at least w(e₁) + w(e₂)).
下界是通过将最小生成树的权重与两条最短关联边相结合得出的：
下界(被删顶点) = w(MST) + w(e₁) + w(e₂)
这个总和为任何完整的回路提供了一个有保证的最小长度。这是一个真正的下界，因为任何有效回路必定包含在缩减顶点集合上的一棵生成树（其权重至少为 w(MST)）以及从被删顶点出发的两条边（其权重至少为 w(e₁) + w(e₂)）。
It is essential to avoid accidentally including a cycle when mentally constructing the tour, but the mathematical argument stands regardless: the MST plus the two shortest edges cannot exceed the optimal tour length. Whenever you see a value smaller than this lower bound, you know it is impossible.
在脑海中构建回路时，必须避免意外包含环，但无论如何数学论证都是成立的：最小生成树加两条最短边不可能超过最优回路的长度。每当你看到一个比这个下界更小的数值时，你就知道这是不可能的。
8. Example: Finding the Lower Bound Step-by-Step | 示例：逐步寻找下界
Let us work through a concrete example with five towns A, B, C, D, and E. The complete distance matrix (weights) is given below. All entries are symmetric and the dash indicates the absence of a self-loop.
让我们通过一个具体的例子来操作，其中有五个城镇 A、B、C、D 和 E。下面给出完整的距离矩阵（权重）。所有条目都是对称的，短划线表示没有自环。
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | - | 12 | 10 | 19 | 8 |
| B | 12 | - | 9 | 14 | 6 |
| C | 10 | 9 | - | 11 | 7 |
| D | 19 | 14 | 11 | - | 15 |
| E | 8 | 6 | 7 | 15 | - |
Suppose we delete vertex A. The remaining vertices are B, C, D, E. Apply Kruskal' : B-E (6), C-E (7), B-C (9), C-D (11), B-D (14), D-E (15). We select B-E (6), then B-C (9) – C-D (11) is added. The MST consists of B-E, B-C, C-D with total weight = 6 + 9 + 11 = 26.
假设我们删除顶点A。剩余顶点为B、C、D、E。在此四个顶点上使用克鲁斯卡尔算法。边列表按权重排序为：B-E (6), C-E (7), B-C (9), C-D (11), B-D (14), D-E (15)。我们选择B-E (6)，然后选择B-C (9)——没有环，之后C-E (7)会形成环B-C-E-B，故跳过，接着添加C-D (11)。最小生成树由B-E、B-C、C-D组成，总权重 = 6 + 9 + 11 = 26。
ng A is LB(A) = 26 + 8 + 10 = 44. We can interpret this as: no complete tour visiting all five towns can be shorter than 44.
现在查看从A到其他顶点的边：A-E (8), A-C (10), A-B (12), A-D (19)。最小的两条是A-E (8)和A-C (10)。因此，删除A时的下界为 LB(A) = 26 + 8 + 10 = 44。我们可以这样解读：没有任何访问所有五个城镇的完整回路能短于44。
9. Choosing the Best Lower Bound | 选择最佳下界
The bound we found (44) depends on the choice of deleted vertex. To tighten our estimate, we should repeat the process for every vertex and take the maximum lower bound, because the optimal tour length must be at least as large as the highest of these individually valid lower bounds.
我们找到的界（44）取决于被删顶点的选择。为了收紧估计，我们应该对每个顶点重复这一过程，并取最大下界，因为最优回路长度必须至少与这些各自有效的下界中最大的那个一样大。
For instance, deleting E might yield an even larger bound. Let' s: B-C (9), A-C (10), C-D (11), total = 30. Edges from E: E-B (6), E-C (7), E-A (8), E-D (15). Two smallest: 6 + 7 = 13. LB(E) = 30 + 13 = 43. That is lower than 44, so the best so far is 44. Continue with other vertices if needed.
例如，删除E可能会得出一个更大的界。我们来快速计算一下：移除E，剩余顶点A、B、C、D。这些顶点之间边的排序为：B-C (9), A-C (10), C-D (11), A-B (12), B-D (14), A-D (19)。最小生成树的边：B-C (9), A-C (10), C-D (11)，总权重 = 30。从E出发的边：E-B (6), E-C (7), E-A (8), E-D (15)。最小的两条：6 + 7 = 13。LB(E) = 30 + 13 = 43。这比44低，因此目前最佳下界是44。如有必要，继续计算其他顶点。
In many exam questions, the largest bound obtained is the final answer. Always keep a small table of your bounds for clarity. The best lower bound gives you the tightest guarantee and is used in branch-and-bound to discard suboptimal routes early.
在许多考试题目中，得到最大界就是最终答案。为清晰起见，请始终用一个小表格记录你求出的各个下界。最佳下界为你提供了最紧的保证，并在分支定界法中用于尽早舍弃次优路线。
10. Limitations and Practical Use | 局限与实际应用
The MST lower bound method is not an algorithm to solve the TSP; it only provides an estimate. The bound can be weaker (lower) than the actual optimum, especially if the chosen vertex is not a weak spot in the network. That is why we test all possibilities. In symmetric complete graphs satisfying the triangle inequality, the bound is often reasonably close.
最小生成树下界方法并不是解决旅行商问题的算法；它只提供一个估计值。这个界可能比实际最优值弱（低），特别是当所选顶点并不是网络中的弱点时。这就是为什么我们要测试所有可能的原因。在满足三角不等式的对称完全图中，这个下界通常是比较接近的。
Practically, the method shines in branch-and-bound: if an upper bound is already known (say 50), a city with a lower bound of 44 means the optimal cannot be below 44, but we still need to explore branches; but if another branch has a lower bound of 50, it becomes uninteresting because we already have a tour of 50. Understanding this principle helps in writing efficient decision algorithms.
在实际中，该方法在分支定界中大放异彩：如果已知一个上界（例如50），那么一个下界为44的城市意味着最优值不可能低于44，但我们仍需要探索分支；但如果另一个分支的下界达到50，它就变得没有吸引力了，因为我们已经有了一个长度为50的回路。理解这一原理有助于编写高效的决策算法。
11. Alternate Lower Bound Using a Different Vertex | 使用不同顶点的替代下界
Sometimes the question will explicitly ask for the best lower bound by deleting each vertex in turn. You must be methodical: draw a neat table with columns "Vertex removed", "MST weight", "Two shortest edges", and "Lower bound". Computations can be speeded up by noting that the graph often has only 4 or 5 vertices, making repeated MST calculations straightforward.
有时题目会明确要求通过依次删除每个顶点来求得最佳下界。你必须按部就班：画一个整洁的表格，列包括“被删顶点”、“MST权重”、“两条最短边”和“下界”。通过注意到图通常只有4或5个顶点，可以使重复计算最小生成树变得直接，从而加快计算速度。
Beware of a common pitfall: after deleting a vertex, the MST must be found on the reduced complete graph. Do not use the full graph's MST. Also, the two shortest incident edges must be from the original graph, not from the reduced one. Mixing up these can lead to an invalid bound. Double-check your selections.
注意一个常见误区：删除顶点后，必须在缩减后的完全图上寻找最小生成树。不要使用全图的最小生成树。此外，两条最短关联边必须选自原图，而不是缩减图。混淆两者会导致无效的下界。请仔细核对你的选择。
When all vertex-specific bounds are listed, simply pick the largest number. If the same bound appears from several vertices, that is perfectly fine; just state it. As an extension, note that if the MST method gives a value equal to a known tour, then that tour is optimal.
当列出所有特定顶点的下界后，只需选择最大的数字。如果同一个下界从多个顶点得出，这完全没有问题；只需陈述即可。作为延伸，请注意如果最小生成树方法得出的数值与已知的某条回路长度相等，那么那条回路就是最优的。
12. Summary and Exam Tips | 总结与考试技巧
The MST method for finding a TSP lower bound is a highly structured process: delete a vertex, find the MST of the rest, add the two smallest incident edges, and repeat for all vertices if necessary. The result is a powerful theoretical guarantee that no tour can be shorter. In Edexcel Decision Mathematics, you must show clear working, including edge selection tables and intermediate totals.
利用最小生成树方法求旅行商问题下界是一个高度结构化的过程：删除一个顶点，求出剩余部分的最小生成树，加上两条最小关联边，如有必要对所有顶点重复这一过程。其结果是提供了没有回路能更短的有力理论保证。在Edexcel决策数学中，你必须展示清晰的演算过程，包括边选择表格和中间总和。
Remember these key points: (1) The MST guarantee works because any tour must contain a spanning tree on the other vertices. (2) Always select the two absolutely smallest edges from the removed vertex, even if they both go to the same vertex? Wait—no, in a simple graph there is only one edge between two vertices. The two smallest will go to two different vertices naturally. (3) The maximum lower bound over all choices of deleted vertex is the best overall lower bound. (4) This technique is foundational for more advanced topics such as branch-and-bound.
记住这些要点：(1) MST保证之所以成立，是因为任何回路必定包含一条在其他顶点上的生成树。(2) 始终选择从被删顶点出发的绝对最小的两条边，即使它们指向同一顶点？等一下——不，在简单图中两个顶点之间只有一条边。最小的两条自然会指向两个不同的顶点。(3) 所有被删顶点选择中得出的最大下界就是整体最佳下界。(4) 这项技术是更高级主题（如分支定界）的基础。
With diligent practice, you will be able to compute these bounds quickly and accurately, impressing examiners and sharpening your algorithmic thinking. Always interpret your final number in the context of the problem to confirm its logical validity.
通过勤奋练习，你将能够快速而准确地计算出这些下界，给考官留下深刻印象，并磨练你的算法思维。始终在问题情境中解释你的最终数值，以确认其逻辑有效性。
Published by TutorHao | Decision Mathematics 1 Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图