图论应用：中国邮路问题（CPP）和旅行商问题（TSP）
IB 数学 AI HL· 主题 5：统计与概率· 30 分钟阅读
1. 中国邮路问题（CPP）★★★☆☆HL 专属⏱ 15 min
✓ 计算器
中国邮路问题
寻找最短闭合路径的问题，要求该路径至少遍历无向连通图的每一条边一次，起点和终点为同一个顶点。
例:
规划覆盖街区所有街道的邮政路线，最终回到配送仓库。
CPP的解取决于图中奇度顶点的数量。根据欧拉握手引理，任何图的奇顶点数量都是偶数。IB AI HL仅考察含0个或2个奇顶点的CPP问题。
如果0个奇顶点：图是欧拉图，最优路线就是欧拉回路，总权重 = 所有边权重之和。
如果2个奇顶点：最优路线需要重复两个奇顶点之间的最短路径。总权重 = 所有边权重之和 + 重复路径的权重。
如果奇顶点数量超过2：配对奇顶点，重复配对之间的最短路径以得到最小额外权重（IB AI HL不考察）。
一个连通图有4个顶点A、B、C、D，度数分别为：A(2，偶)、B(3，奇)、C(2，偶)、D(1，奇)。所有边权重之和为22。B和D之间的最短路径总权重为5。求最优CPP路线的长度。
- 1
步骤1：统计奇度顶点的数量。共有2个奇顶点：B和D。
- 2
步骤2：对于2个奇顶点的情况，将两个顶点之间最短路径的权重加到所有边的总权重上：
- 3
Exam tip:
求解CPP问题前一定要先检查每个顶点的度数；数错奇顶点是最常见的早期错误。
2. 旅行商问题（TSP）简介★★★★☆HL 专属⏱ 20 min
✓ 计算器
旅行商问题
寻找最小总权重哈密顿回路的最优化问题，要求该回路恰好访问图的每个顶点一次，最终回到起点顶点。
例:
规划访问每个城市各一次后回到中心仓库的配送路线。
与CPP不同，对于大型图，没有简单高效的算法可以找到TSP的精确最优解。在IB AI HL考试中，大多数问题只要求你计算最优解的上下界，不需要找到精确值。
检查你对CPP和TSP区别的理解：
哪个问题要求至少遍历每一条边一次？
CPP
TSP
哪个问题要求恰好访问每个顶点一次（起点/终点除外）？
CPP
TSP
显示答案
1 —正确！TSP要求访问每个顶点一次，而CPP可以重复访问顶点。
3. 求解TSP的上界★★★★☆HL 专属⏱ 20 min
✓ 计算器
TSP的上界是一个保证大于或等于真实最优解的总权重。IB AI HL求解上界的标准方法是最近邻算法：
从题目给定的起点顶点出发
移动到当前顶点出发未访问过的、边权重最小的顶点
重复直到所有顶点都被访问
加上最后一个顶点回到起点顶点的边权重，闭合回路
从顶点A出发，使用最近邻算法为该对称TSP求上界：边权重为 ，，，，，。
- 1
步骤1：从A出发。未访问顶点是B、C、D。A出发最小边是AB=3和AD=3；先选AD。目前总权重：3。
- 2
步骤2：当前顶点D。未访问顶点是B、C。D出发最小边是CD=2。移动到C。目前总权重：。
- 3
步骤3：当前顶点C。仅剩下未访问顶点B。边CB=5。移动到B。目前总权重：。
- 4
步骤4：所有顶点都已访问。从B返回A。边BA=3。计算上界总权重：
- 5
4. 求解TSP的下界★★★★★HL 专属⏱ 20 min
✓ 计算器
TSP的下界是一个保证小于或等于真实最优解的值。IB AI HL的标准方法使用最小生成树（MST）：
从原图中删除任意一个顶点
找到剩余图的最小生成树（MST）
将连接被删除顶点的两个最小不同边的权重加到MST权重上
得到的总和就是下界
对前一个例子中的TSP（边权重：，，，，，），删除顶点A后求下界。
- 1
步骤1：删除顶点A。剩余顶点是B、C、D。
- 2
步骤2：找到剩余图的MST。MST使用边CD=2和BD=4，因此MST总权重为 。
- 3
步骤3：得到连接被删除顶点A的两个最小边。A的边为AB=3、AD=3、AC=6，因此两个最小边是3和3。
- 4
步骤4：计算下界总权重：
- 5
5. 常见陷阱
错误做法:
混淆CPP和TSP的要求，把CPP问题当成需要访问所有顶点而非所有边来求解。
原因:
两个问题的核心目标完全不同，混淆会导致错误解。
正确做法:
一定要先确认问题类型：CPP = 覆盖所有边，TSP = 访问所有顶点。
错误做法:
对于含2个奇顶点的CPP问题，忘记将重复路径的权重加到所有边的总权重上。
原因:
很多学生只报告重复路径的权重，而不是完整路线的权重。
正确做法:
求解CPP时，一定要将重复路径的权重加到所有原边权重的总和上。
错误做法:
在TSP的最近邻算法中，访问完所有顶点就停止，忘记加上回到起点的返回边。
原因:
TSP要求闭合回路回到起点，这一步是得满分必须的。
正确做法:
一定要加上最后一个顶点回到起点的边权重，才能得到总上界。
错误做法:
计算TSP下界时，只加了一条连接被删除顶点的边，而非两条。
原因:
TSP回路必须进出被删除顶点，因此需要两条不同的边。
正确做法:
计算下界时，一定要加上连接被删除顶点的两个最小不同边的权重。
6. 速查表
问题类型 | 核心要求 | 关键求解规则 |
|---|---|---|
CPP（0个奇顶点） | 遍历所有边，回到起点 | 最优值 = 所有边权重之和 |
CPP（2个奇顶点） | 遍历所有边，回到起点 | 最优值 = 所有边权重之和 + 奇顶点之间最短路径权重 |
TSP 上界 | 访问所有顶点，回到起点 | 最近邻法：从给定顶点出发，选最近未访问顶点，加返回边 |
TSP 下界 | 访问所有顶点，回到起点 | 删除1个顶点，求剩余图MST，加连接删除顶点的两个最小边 |
真题中的出现
AI 根据考纲规律估算的考点位置,请对照官方真题核实准确性。仅作复习重点参考。
- 2025 · 2
CPP最优路线计算
- 2023 · 2
TSP上下界计算
- 2021 · 2
真实场景TSP物流问题
深入阅读
下一步
CPP和TSP是核心最优化主题，经常作为扩展回答题出现在IB AI HL试卷2中，广泛应用于真实世界物流、配送路线规划和网络设计。掌握这些方法建立在你对图基础和最小生成树的理解上，也为你学习更高级的网络问题（如项目管理的关键路径分析）做准备。这些主题也为大学学习运筹学、计算机科学和数据分析打下坚实基础。