Christofides 算法

Christofides 算法是求解度量旅行商问题(TSP)的著名近似算法,由希腊裔学者 Nicos Christofides 于 1976 年提出。当距离满足对称性和三角不等式时,该算法能保证输出的巡回路线长度不超过最优解的 1.5 倍,这一近似比在很长时间里都是度量 TSP 的最佳纪录。

概述

旅行商问题要找一条经过所有城市恰好一次并回到起点的最短闭合路线,是著名的 NP 困难问题。在距离满足三角不等式的度量版本下,Christofides 算法巧妙地组合了几个经典图论工具,在多项式时间内给出带 1.5 倍质量保证的近似解。

核心原理

算法分为几个关键步骤,依次构造出一条巡回路线:

• 求最小生成树:先在所有城市上构造一棵最小生成树 T。
• 处理奇度顶点:找出 T 中度数为奇数的所有顶点,在它们之间求一个最小权完美匹配 M。
• 合并成欧拉图:把 T 与 M 合并,所得多重图每个顶点度数均为偶数,存在欧拉回路。
• 短路成哈密顿回路:沿欧拉回路遍历,遇到已访问的城市则跳过(抄近道),借助三角不等式得到不更长的哈密顿回路。

应用场景

Christofides 算法用于物流配送、线路规划、电路板钻孔顺序优化等需要近似求解度量 TSP 的实际问题。它是近似算法理论的里程碑;直到近年才有研究给出近似比略优于 1.5 的改进算法。

常见问题

问:为什么只对度量 TSP 有效?答:算法的最后一步依赖三角不等式来保证跳过已访问城市不会增加路线长度;若距离不满足三角不等式,这一保证不成立,近似比也无法证明。

问:为什么近似比是 1.5?答:最小生成树的权不超过最优解,而奇度顶点上的最小权匹配可证明不超过最优解的一半,二者相加即得 1.5 倍上界。