# 图论算法 II

> Edexcel 国际 A-Level 数学 · D1 WDM11 2018
> 来源: https://www.owlsprep.com/zh/study/edexcel-ial-math-d1-algorithms-on-graphs-ii/

本指南覆盖Edexcel IAL决策数学1的核心图算法主题：路线检查（中国邮路）问题、TSP边界计算、最近邻算法、实用TSP捷径，完全适配2018年考纲要求。

**先修:** [图与网络术语](https://www.owlsprep.com/zh/study/edexcel-ial-math-d1-graphs-networks-basics/); [最小生成树算法（克鲁斯卡尔算法、普里姆算法）](https://www.owlsprep.com/zh/study/edexcel-ial-math-d1-minimum-spanning-trees/)

## 学习目标

- 求解最多包含4个奇度节点的网络的路线检查（中国邮路）问题
- 区分经典旅行商问题（TSP）和实用旅行商问题变体
- 使用最小生成树（MST）方法计算TSP的上界和下界
- 应用最近邻算法求解TSP上界
- 使用捷径优化TSP上界

## 路线检查（中国邮路）问题

**路线检查问题** — 寻找最短闭合路径，至少遍历连通网络的每条边一次，最终返回起点顶点。

*例:* 用于规划配送路线、撒盐除冰路线、或者覆盖区域内所有街道的邮递路线。

该问题基于可遍历网络的欧拉定理：一个网络存在闭合欧拉迹（恰好遍历每条边一次）当且仅当它有0个奇度顶点。如果存在奇度顶点，你需要重复经过某些边来消除奇顶点，将奇顶点两两配对，重复每对之间的最短路径，从而最小化总额外距离。对于Edexcel D1考试，涉及的网络最多有4个奇顶点：如果是2个奇顶点，重复它们之间的最短路径；如果是4个奇顶点，列出所有3种可能的配对，计算每种配对的总额外距离，选择最小值。总路径长度等于所有边的权重之和加上最小额外距离。

**例题:** 一个连通网络的总边权重为128，有4个奇顶点：A、B、C、D。奇顶点对之间的最短路径为：AB=7，AC=12，AD=9，BC=5，BD=10，CD=8。求至少遍历每条边一次并返回起点的最短路径的最小长度。

1. 列出4个奇顶点的全部3种有效配对：
2. 配对1：(A,B) 和 (C,D)：总额外距离 = 7 + 8 = 15
3. 配对2：(A,C) 和 (B,D)：总额外距离 = 12 + 10 = 22
4. 配对3：(A,D) 和 (B,C)：总额外距离 = 9 + 5 = 14
5. 选择最小额外距离：14
6. 总路径长度 = 128 + 14 = 142

> **考试提示:** 即使你一眼就能看出最小配对，也必须明确列出4个奇度节点的全部3种配对，才能拿到全部方法分。

*计算器:* allowed

## 旅行商问题（TSP）变体

**旅行商问题** — 寻找最短闭合路径，恰好访问网络中的每个顶点一次，最终返回起点顶点。

*记法:* TSP

Edexcel D1区分两种变体：**经典TSP**：适用于满足三角不等式的完全图（任意两个顶点之间的最短路径就是它们之间的直接边）。**实用TSP**：适用于非完全图，或者不满足三角不等式的图。对于实用TSP，首先将原始网络转换为所有顶点对之间都是最短距离的完全网络，然后在这个新网络上求解经典TSP。你可以使用捷径优化TSP上界：如果一条路径多次访问某个顶点，就将重复的路段替换为到下一个未访问顶点的直接路径，从而缩短总长度。

**例题:** 5顶点网络上的一条TSP路径为：A → B → C → A → D → E → A，总长度79。已知最短路径C→D为10，C→A + A→D = 14，使用捷径优化这个上界。

1. 识别重复顶点：在访问完C之后、遍历完所有顶点之前，A被访问了两次。
2. 将路段C → A → D替换为直接最短路径C → D，权重为10（原路段权重为14）。
3. 新路径：A → B → C → D → E → A，总长度 = 79 - 14 + 10 = 75，得到更紧的上界。

> **考试提示:** 捷径只有在不跳过任何未访问顶点的情况下才有效：应用捷径后要确保所有顶点仍然恰好被访问一次。

*计算器:* allowed

## 使用MST方法计算TSP边界

由于大型网络的精确TSP解计算成本极高，在Edexcel D1考试中你只需要计算最优TSP路径的上界和下界。**上界**：任意一条有效TSP路径的长度（上界越小，越接近最优解）。**下界**：最优TSP路径可能的最小长度（下界越大，对最优解的约束越严格）。

**MST TSP下界** — 通过从网络中删除一个顶点，找到剩余顶点的MST，然后将连接被删除顶点和MST的两条最短边的权重相加得到的下界。最优TSP路径的长度至少等于该值。

**例题:** 4顶点完全网络的边权重为：AB=6，AC=8，AD=5，BC=3，BD=9，CD=4。通过删除顶点A计算TSP的下界。

1. 删除顶点A，剩余顶点为B、C、D。
2. 求B、C、D的MST：边BC=3，CD=4，MST总权重=7。
3. 找到连接A和剩余顶点的两条最短边：AD=5，AB=6，和为11。
4. 下界 = 7 + 11 = 18。

使用MST方法求有效上界的方法是：将MST的每条边都复制一份，得到一条遍历每条边两次的闭合路径，然后应用捷径得到一条有效TSP路径。对于经典TSP，该方法得到的上界最多是最优TSP长度的两倍。

> **考试提示:** 为多个被删除的顶点分别计算下界，然后取最大值作为最终下界（这是对最优路径最严格的约束）。

*计算器:* allowed

## 最近邻算法

**最近邻算法** — 求解TSP上界的启发式算法，从指定顶点出发，反复访问最近的未访问顶点，直到所有顶点都被访问，然后返回起点顶点。

最近邻算法的执行步骤：1. 选择一个起点顶点。2. 从当前顶点移动到最近的未访问顶点。3. 重复步骤2直到所有顶点都被访问。4. 直接返回起点顶点。得到的路径长度就是TSP的一个上界。从每个顶点出发都运行一次该算法，选择得到的最小长度，就能得到最紧的上界。

**例题:** 使用上一例题中的4顶点网络，从顶点A出发运行最近邻算法：AB=6，AC=8，AD=5，BC=3，BD=9，CD=4。

1. 从A出发，最近的未访问顶点是D（权重5）。当前路径：A→D。
2. 在D点，最近的未访问顶点是C（权重4）。当前路径：A→D→C。
3. 在C点，仅剩的未访问顶点是B（权重3）。当前路径：A→D→C→B。
4. 从B返回A（权重6）。总路径长度 = 5 + 4 + 3 + 6 = 18。
5. 由于这个上界等于之前计算的下界，因此这就是最优TSP路径。

> **考试提示:** 必须明确写出最近邻算法的每一步才能拿到全分，不要只写出最终路径。

*计算器:* allowed

## 常见错误

- **错误做法:** 路线检查问题中，4个奇度节点只列出2种配对，而不是全部3种。
  - 原因: 你可能会漏掉总额外距离最小的配对，导致总路径长度计算错误，同时丢失方法分。
  - 正确做法: 始终列出4个奇度节点的全部3种不同配对，计算每种配对的额外距离，然后选择最小值。
- **错误做法:** 没有先将实用TSP网络转换为完整的最短距离网络，就直接对其应用最近邻算法。
  - 原因: 得到的路径可能无效，或者得到的上界过于宽松。
  - 正确做法: 对于实用TSP，首先构建所有顶点对之间的最短路径完整矩阵，然后在该矩阵上运行最近邻算法。
- **错误做法:** 计算TSP下界时，没有先删除一个顶点，直接计算所有顶点的MST权重。
  - 原因: 得到的下界值过低，不符合要求的计算方法。
  - 正确做法: 删除一个顶点，计算剩余顶点的MST，然后加上连接被删除顶点和网络的两条最短边的权重。
- **错误做法:** 优化TSP上界时，使用跳过未访问顶点的捷径。
  - 原因: 得到的路径不是有效TSP路径，因为它没有恰好访问每个顶点一次。
  - 正确做法: 只替换返回到已访问顶点的路段，确保所有未访问顶点仍然被包含在路径中。
- **错误做法:** 路线检查问题中，忘记将所有边的总权重加上重复路段的额外距离。
  - 原因: 你只会计算出额外长度，而不是总路径长度，丢失精度分。
  - 正确做法: 总路径长度 = 所有边的权重之和 + 奇节点配对得到的最小重复额外距离。

## 速查表

| 算法 | 核心步骤 | 适用场景 |
| --- | --- | --- |
| 路线检查 | 1. 统计奇节点数量 2. 列出所有配对 3. 最小化额外距离 4. 与总边权重相加 | 覆盖每条边至少一次的最短路径 |
| TSP MST下界 | 1. 删除一个顶点 2. 求剩余顶点的MST 3. 将两条最短边加回被删除顶点 | 最优TSP路径的最小可能长度 |
| 最近邻算法 | 1. 从一个顶点出发 2. 访问最近的未访问顶点 3. 重复，返回起点 | 求解TSP上界 |
| 实用TSP预处理 | 1. 构建完整最短距离矩阵 2. 在矩阵上求解经典TSP 3. 应用捷径 | 非完全网络或不满足三角不等式的网络 |

## 下一步

掌握了路线检查和TSP的图算法之后，你就可以继续学习Edexcel IAL决策数学1的后续核心主题了。这些图算法经常和网络流、关键路径分析一起出现在8-12分的大题中，所以一定要通过真题练习巩固这些知识点的综合应用。你还需要练习从非完全网络构建完整最短距离矩阵，这是很多实用TSP题目的第一步，也是很多学生失分的地方。考试中一定要完整写出所有配对、MST计算、最近邻算法步骤的推导过程，才能拿到全部方法分。

---

来自 [OwlsPrep](https://www.owlsprep.com) —— A-Level / IB / AP / IGCSE 免费学习指南，依据官方考纲编写。原页面：https://www.owlsprep.com/zh/study/edexcel-ial-math-d1-algorithms-on-graphs-ii/