求解旅行商问题（克里斯托菲德斯算法）

求解旅行商问题（克里斯托菲德斯算法）

问题描述

• 一个售货员必须访问n个城市，恰好访问每个城市一次，并最终回到出发城市。
  售货员从城市i到城市j的旅行费用是一个整数，旅行所需的全部费用是他旅行经过的的各边费用之和，而售货员希望使整个旅行费用最低。
• （等价于求图的最短哈密尔顿回路问题）令G=(V, E)是一个带权重的有向图，顶点集$ V=(v0, v1, …, vn-1) $。从图中任一顶点$vi $出发，经图中所有其他顶点一次且只有一次，最后回到同一顶点$vi$的最短路径。

求解旅行商问题的算法大体可分为两类：确切算法和近似算法。

1. 确切算法保证给出最优解，但由于“组合爆炸”，其仅可用于计算较小规模实例。

2. 近似算法，或许有可能在短时间内，给出相当接近最优解的近似解。其中，非随机性 近似算法包括构建式启发/贪婪算法，克里斯托菲德斯算法等；随机性近似算法包括 随机局域搜索、模拟退火、遗传算法、粒子群算法等。

本文将主要介绍克里斯托菲德斯算法（Christofides Algorithm）

克里斯托菲德斯算法（Christofides Algorithm）

克里斯托菲德斯算法 (Christofides algorithm) 是旅行商问题在度量空间（即距离对称且满足三角不等式）上的一个近似算法。即使最差情况下，克里斯托菲德斯算法所得回路长度不会超过最优回路长度的 1.5 倍。

算法步骤

1、构造图的的最小生成树T

2、O为在最小生成树T上度数为奇数的顶点集，则O中有偶数个顶点(根据握手定理可得)

3、构造点集O在原完全图上的最小完全匹配M

匹配（或称独立边集）是指这个图之中，任意两条边都没有公共的顶点，这时每个顶点都至多连出一条边。

完全匹配是一个包括了图G中所有顶点的匹配。最小完全匹配是连接边总长度最小的完全匹配。

可参考：二分图的最大匹配、完美匹配和匈牙利算法 - Blog - Renfei Song

4、将最小完全匹配M和最小生成树T的边集取并，构造重图J，将满足其每个顶点都是偶数度的。

5、J可以形成一个欧拉回路E。

欧拉回路：图G的一个回路，如果恰通过图G的每一条边，则该回路称为欧拉回路，具有欧拉回路的图称为欧拉图。欧拉图就是从图上的一点出发，经过所有边且只能经过一次，最终回到起点的路径。（可以简单理解为一笔画）

一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数，且该图是连通图。

6、将前一步得到的图改造为一个哈密顿回路H：只需要跳过前一步欧拉回路中重复的顶点即可（这个步骤又称作选取近道，“short-cutting”）

哈密顿回路：由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次

可简单表示为

(a) 定义：S 代表一系列边（允许重边），c (S) 代表各边权重（长度）之和。

(b) 定义：H∗ G 为无向多重图 G 上，长度最短的哈密尔顿回路（Hamiltonian Cycle），即 途中经过所有点且只经过一次。

© 定义：假设 S 为无向多重图 G 上的导出子图，在 S 上长度最短的哈密尔顿回路记为 H∗ S。根据三角形三边关系定则易证，$c(H\ast S)\le c(H\ast G)$。

(d) 构造最小生成树 T，根据最小权生成树定义，$c(H\ast G)\ge c(H\ast G-e)\ge c(T)$。

(e) 分离在 T 上度数为奇数的点，生成导出子图 S（根据握手定理，给定无向图 G = (V, E)， 一条边贡献 2 度，故有 $\Sigma degG(v)=2|E|$；除开度数为偶数的顶点所贡献的度数，推 论可知，度数为奇数顶点数有偶数个）；

(f) 构造 S 的最小权完美匹配 M，构造多重图 G′ = T ∪ M（此时每个顶点均为偶数度， 故存在欧拉回路）；

(g) 生成 G′ 的欧拉回路 C，$c(C)=c(T)+c(M)$; (h) 搭桥（short-cut/bypass）略过重复访问的点（起点终点不删）得到符合问题描述的新 回路 C ′（最后回到起点）。

证明：

• 由 e,三角形三边关系定则，$c(C\prime )\le c(C)$；

• 由 d，$c(H\ast G)\ge c(H\ast G-e)\ge c(T)$；

• 由 g，$c(C)=c(T)+c(M)$；

• 由 f、c，$c(M)+c(M)\le c(M1)+c(M2)=c(H\ast S)\le c(H\ast G)$；

• 故 $c(C\prime )\le c(T)+c(M)\le c(H\ast G)+1/2c(H\ast G)$；

• 即得证 该算法求出的最优解与实际最优解的最大近似比为1.5。

参考资料

克里斯托菲德斯算法