Christofides 算法

算法步骤 ​

输入满足三角不等式的完全加权图。先求 MST $T$；令 $O$ 为 $T$ 中奇度顶点集合，握手定理保证 $|O|$ 为偶数。在 $O$ 的诱导完全图上求最小权完美匹配 $M$。多重图 $T\cup M$ 所有度为偶数且连通，取 Euler 回路，再按首次出现次序 shortcut 重复顶点，得到 Hamilton 回路。

3/2 证明 ​

删除最优 TSP 回路的一条边得到生成树，所以

$$w(T)\le OPT.$$

最优回路按出现顺序连接 $O$ 中顶点，交替取边得到两组完美匹配，二者总权不超过该回路；较轻者至多 $OPT/2$，故最小完美匹配 $w(M)\le OPT/2$。三角不等式保证 shortcut 不增成本，最终

$$w(C)\le w(T)+w(M)\le \frac{3}{2}OPT.$$

奇度修复图像 ​

MST 已连通但不一定有 Euler 回路。只给奇度点各加一条匹配边，会把所有奇度翻成偶度，同时保留连通性；任意匹配虽能修复奇偶性，却可能太贵，必须使用最小权完美匹配。

边界与词义 ​

没有三角不等式时，跳过重复顶点可能显著增重，近似界失效；一般非 metric TSP 甚至难以获得此保证。$T\cup M$ 是允许平行边的多重图，不能去重。这里的 Eulerian graph tour 与树 DFS 的Euler tour 技巧公理库树的 Euler Tour 技巧Euler tour technique for trees用 DFS 次序把子树或树上行走线性化，并区分三种常见序列。同名但对象不同。

匹配上界细节 ​

最优 Hamilton 回路限制到奇度集合 $O$ 的访问次序，沿回路在相邻 $O$ 顶点之间取 shortcut，得到一个 metric cycle，其总权不超过 OPT。偶数个顶点的 cycle 可交替拆成两份完美匹配，所以至少一份不超过 OPT$/2$；算法求的是最小匹配，因此也不超过。

若图只给部分边，应先取 metric closure（全对最短路距离），运行算法后再把 shortcut 边展开成原图路径。存在负边或负环时 metric closure 与三角不等式语义需重新检查。

从多重图恢复 Hamilton 回路 ​

把最小生成树 $T$ 与奇度点上的完美匹配 $M$ 合并后，每个顶点度数为偶数，连通性也由 $T$ 保证，故存在 Euler 回路。沿回路行走时维护“已访问顶点”集合：遇到重复顶点就直接跳到下一个未访问顶点，最后回到起点。

跳跃把两条或多条度量边替换成一条直达边。由三角不等式，新边费用不超过被跳过路径费用，所以 shortcut 后得到 Hamilton 回路且不增成本。若图不是完全图，可先用最短路距离做 metric closure，再把直达边展开回原图路径；若存在负边或三角不等式失败，这一步的证明断裂。

奇度顶点数由握手定理必为偶数，因此完美匹配有定义。实现中匹配只在奇点诱导的完全度量图上求，而不是在原 MST 边上找；后者可能根本没有完美匹配。

参考资料

• Nicos Christofides, Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem, 1976.
• David Williamson, David Shmoys, The Design of Approximation Algorithms, 2011.