克里斯托菲德斯算法

克里斯托菲德斯算法（英語：Christofides algorithm）是旅行商问题在度量空间（即距离对称且满足三角不等式）上的一个近似算法。^[1] 该算法可以保证相对最优哈密尔顿回路长度有3/2的近似比。尼科斯·克里斯托菲德斯（英语：Nicos Christofides）于1976年首次发表了这个算法，故以他的名字命名之。^[2] 截至2017年^[update]，这一算法仍然是一般性旅行商问题的算法中近似比最好的结果。

算法

令 $G = (V, w)$ 是旅行商问题的一个实例。即， $G$ 是一顶点集 $V$ 上的一个完全图，函数 $w$ 给 $G$ 的每条边指定了一个非负实边权。依三角不等式，对每三个顶点 $u$ , $v$ 和 $x$ 都有关系 $w (uv) + w (vx) \geq w (ux)$ .

算法可以被描述为如下伪代码。

构造图上的最小的生成树 T
令 O 为原图顶点集中在 T 上度数为奇数的顶点集。根据握手定理，O 中有偶数个顶点
构造点集O在原完全图上的最小完美匹配M
将 M 和 T 的边集取并，构造重图 H ，满足其每个顶点都是偶数度的
H 可以形成一个欧拉回路
将前一步得到的图改造为一个哈密尔顿回路：只需要跳过前一步欧拉回路中重复的顶点即可（这个步骤又称作选取近道，"short-cutting"）。

近似比

算法所生成的解相对最优解有3/2的近似比。下给出简要证明。

令 $C$ 为图上的最优旅行商回路。注意到，删除 $C$ 上的一条边将产生原图上的一棵生成树，其总权重至少为最小生成树的总权重，亦即 $w (T) \leq w (C)$ 。接下来，给 $O$ 中的顶点编号，编号顺序依据回路 $C$ 上的顶点顺序。再将 $C$ 做划分，得到两个边集：其一包含所有起始点为奇数编号的边，另一个则包含所有起始点为偶数编号的边。这两个边集各对应于 $O$ 上的一个完美匹配，且匹配的总边权不超过边集的总边权。

因为两个边集是 $C$ 的划分，二者中的某一个至多有 $C$ 总边权的一半，因而其对应匹配的总边权不超过 $C$ 总边权的一半。因为没有比最小完美匹配更小的匹配，所以 $w (M) \leq w (C)/2$ 。 $T$ 和 $M$ 的权重总和也就是欧拉回路的权重总和，也就是至多 $3 w (C)/2$ 。由于做选取近道操作并不增加权重，所有最终输出的总边权也不超过 $3 w (C)/2$ .

下界

存在使得克里斯托菲德斯算法近似比任意接近3/2的输入。

一类满足条件的输入由 $n$ 个顶点组成，满足最优环路上边的权重都为 $1$ ，且在最优环路上相隔一条边的边都有权重 $1 + ε$ ，其中 $ε$ 是一个足够小的正数。未由上述定义给出的权重由两点间的最短路径给出。

最小生成树可以从最优环路中构造，总长 $n - 1$ 。唯二的奇数度点是这棵树（此时也是条路径）的两个端点，其完美匹配仅由一条权重近似为 $n /2$ 的单边构成。生成树和这条单边的并集是一个回路，没有可能的近道 (short-cutting)，且其总边权近似为 $3 n /2$ 。而问题的最优解是使用所有权重为1或 $1 + ε$ 的边构造的环路，其总权重为 $n + (n - 2) ε$ ，对充分小的 $ε$ 可以无限靠近于 $n$ 。^[3]

例

	已知：一个边权满足三角不等式的完全图
	计算最小生成树T
	计算最小生成树中奇数度的顶点集O
	用 O 中的点构造原完全图上的一个完全子图
	构造这个子图上的最小完美匹配M
	将生成树和匹配取并 $T \cup M$ 形成一个欧拉重图
	计算欧拉回路
	删除重复顶点，选取近道 (short-cutting)，给出算法的输出

参考文献

^ Goodrich, Michael T.; Tamassia, Roberto, 18.1.2 The Christofides Approximation Algorithm, Algorithm Design and Applications, Wiley: 513–514, 2015 .
^ Nicos Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976.
^ Bläser, Markus, Metric TSP, Kao, Ming-Yang (编), Encyclopedia of Algorithms, Springer-Verlag: 517–519, 2008 [2017-12-26], ISBN 9780387307701, （原始内容存档于2016-04-28） .

外部链接

NIST 克里斯托菲德斯算法定义（页面存档备份，存于互联网档案馆）

[gt-1] Goodrich, Michael T.; Tamassia, Roberto, 18.1.2 The Christofides Approximation Algorithm, Algorithm Design and Applications, Wiley: 513–514, 2015 .

[2] Nicos Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976.

[3] Bläser, Markus, Metric TSP, Kao, Ming-Yang (编), Encyclopedia of Algorithms, Springer-Verlag: 517–519, 2008 [2017-12-26], ISBN 9780387307701, （原始内容存档于2016-04-28） .

[1]

[2]

[3]