F. Euclidean Traveling Salesman Problem
数学大学
F. Euclidean Traveling S
计算几何 · 05. Delaunay Triangulation
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
F. Euclidean Traveling S
计算几何 · 05. Delaunay Triangulation
Definition
欧几里得旅行商问题：访问所有点各一次并回到起点的最短回路。
输入
平面上的 n 个点，边权为欧氏距离
目标
总长度最小的哈密顿回路
NP-Hardness
欧氏 TSP 是 NP 难的：精确解不存在已知的多项式算法。
难度
即使限定欧氏距离仍 NP 难
实践
大规模依赖近似与启发式
Approximation
近似算法：EMST 先序遍历给出 2 倍近似，Christofides 给 1.5 倍。
EMST 2 倍
树先序遍历的回路长 ≤ 2×MST ≤ 2×OPT
Christofides
补最小完美匹配后欧拉化，1.5 倍近似
本节要点
- ✓欧氏 TSP：最短哈密顿回路
- ✓NP 难，精确解不可行时用近似
- ✓EMST 遍历 2 倍、Christofides 1.5 倍
延伸主题：实现 EMST 2 倍近似在小规模上对照精确解
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1为什么欧氏 TSP 的 EMST 遍历能保证 2 倍近似？
参考答案EMST 的总长不超过最优回路的长度（去掉回路一条边即得生成树）；树先序遍历形成的回路每条树边恰走两次，总长 ≤ 2×MST ≤ 2×OPT。近似的上界由此闭合。
2三角不等式在近似分析中扮演什么角色？
参考答案欧氏距离满足三角不等式，使「抄近路」不增加长度——树遍历的捷径化、匹配连接的短路边都依赖它。没有三角不等式，近似比完全失去保证。
3Christofides 1.5 倍近似的改进来自哪里？
参考答案在最小生成树上找出奇度顶点，用最小权完美匹配把它们两两配对——配对总长不超过 OPT/2。树加匹配构成欧拉图，抄近路成回路后总长 ≤ OPT×1.5。