图论算法 II
Edexcel 国际 A-Level 数学· D1 §3.1 至 §3.4 2018 第3版· 25 分钟阅读
1. 路线检查（中国邮路）问题★★☆☆☆⏱ 8 min
✓ 计算器
路线检查问题
寻找最短闭合路径，至少遍历连通网络的每条边一次，最终返回起点顶点。
例:
用于规划配送路线、撒盐除冰路线、或者覆盖区域内所有街道的邮递路线。
该问题基于可遍历网络的欧拉定理：一个网络存在闭合欧拉迹（恰好遍历每条边一次）当且仅当它有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
Exam tip:
即使你一眼就能看出最小配对，也必须明确列出4个奇度节点的全部3种配对，才能拿到全部方法分。
2. 旅行商问题（TSP）变体★★★☆☆⏱ 6 min
✓ 计算器
旅行商问题
寻找最短闭合路径，恰好访问网络中的每个顶点一次，最终返回起点顶点。
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，得到更紧的上界。
Exam tip:
捷径只有在不跳过任何未访问顶点的情况下才有效：应用捷径后要确保所有顶点仍然恰好被访问一次。
3. 使用MST方法计算TSP边界★★★★☆⏱ 6 min
✓ 计算器
由于大型网络的精确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长度的两倍。
Exam tip:
为多个被删除的顶点分别计算下界，然后取最大值作为最终下界（这是对最优路径最严格的约束）。
4. 最近邻算法★★★☆☆⏱ 5 min
✓ 计算器
最近邻算法
求解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路径。
Exam tip:
必须明确写出最近邻算法的每一步才能拿到全分，不要只写出最终路径。
5. 常见陷阱
错误做法:
路线检查问题中，4个奇度节点只列出2种配对，而不是全部3种。
原因:
你可能会漏掉总额外距离最小的配对，导致总路径长度计算错误，同时丢失方法分。
正确做法:
始终列出4个奇度节点的全部3种不同配对，计算每种配对的额外距离，然后选择最小值。
错误做法:
没有先将实用TSP网络转换为完整的最短距离网络，就直接对其应用最近邻算法。
原因:
得到的路径可能无效，或者得到的上界过于宽松。
正确做法:
对于实用TSP，首先构建所有顶点对之间的最短路径完整矩阵，然后在该矩阵上运行最近邻算法。
错误做法:
计算TSP下界时，没有先删除一个顶点，直接计算所有顶点的MST权重。
原因:
得到的下界值过低，不符合要求的计算方法。
正确做法:
删除一个顶点，计算剩余顶点的MST，然后加上连接被删除顶点和网络的两条最短边的权重。
错误做法:
优化TSP上界时，使用跳过未访问顶点的捷径。
原因:
得到的路径不是有效TSP路径，因为它没有恰好访问每个顶点一次。
正确做法:
只替换返回到已访问顶点的路段，确保所有未访问顶点仍然被包含在路径中。
错误做法:
路线检查问题中，忘记将所有边的总权重加上重复路段的额外距离。
原因:
你只会计算出额外长度，而不是总路径长度，丢失精度分。
正确做法:
总路径长度 = 所有边的权重之和 + 奇节点配对得到的最小重复额外距离。
6. 速查表
算法 | 核心步骤 | 适用场景 |
|---|---|---|
路线检查 |
| 覆盖每条边至少一次的最短路径 |
TSP MST下界 |
| 最优TSP路径的最小可能长度 |
最近邻算法 |
| 求解TSP上界 |
实用TSP预处理 |
| 非完全网络或不满足三角不等式的网络 |
7. 常见问题
路线检查问题中，4个奇度节点我需要列出多少种配对方式？
对于4个奇度节点，恰好有3种不同的配对方式需要计算。你不需要使用任何算法来寻找配对：直接通过枚举列出所有配对即可获得全部方法分。
什么时候我需要为TSP构建完整的最短距离网络？
对于实用TSP（原始网络不是完全网络，或者不满足三角不等式），你需要先将其转换为所有节点对之间都是最短路径的完全网络，之后再计算边界或者应用最近邻算法。
深入阅读
下一步
掌握了路线检查和TSP的图算法之后，你就可以继续学习Edexcel IAL决策数学1的后续核心主题了。这些图算法经常和网络流、关键路径分析一起出现在8-12分的大题中，所以一定要通过真题练习巩固这些知识点的综合应用。你还需要练习从非完全网络构建完整最短距离矩阵，这是很多实用TSP题目的第一步，也是很多学生失分的地方。考试中一定要完整写出所有配对、MST计算、最近邻算法步骤的推导过程，才能拿到全部方法分。