クリストフィードのアルゴリズム

クリストフィードのアルゴリズム（英: Christofides algorithm）は三角不等式を満たす距離を持つグラフにおいて、巡回セールスマン問題の近似解を見つける近似アルゴリズムである^[1]。この近似アルゴリズムの出力は、最適解の重みの3/2以下になることが保証されている。1976年に発案者され、発案者であるNicos Christofidesにちなんで命名された^[2]。 2015年現在、距離空間における巡回セールスマン問題に対する多項式時間アルゴリズムの中では、近似度が最良であるアルゴリズムである（一部の特殊な場合では、より良い近似度が存在する事も知られている）。

アルゴリズム

$G = (V, w)$ について巡回セールスマン問題を考える。頂点集合を $V$ 、その完全グラフを $G$ とし、 $G$ に含まれる全ての辺に対し定義される非負の重み集合を $w$ とする。三角不等式より任意の3つの点 $u, v, x$ に対し、 $w (uv) + w (vx) \geq w (ux)$ が成立する。

以下に擬似コードを示す^[1]。

$G$ の最小全域木 $T$ を構築する。
$T$ に含まれる奇数次の頂点集合を $O$ とする。このとき、握手補題（英語版）より $O$ は偶数個の頂点を持つ。
$O$ に含まれる頂点によって与えられる誘導部分グラフにおいて最適マッチング $M$ を探索する。
$M$ と $T$ の辺を統合し、すべての頂点が偶数次となる多重グラフ $H$ を構築する。
$H$ 内部でオイラー閉路を構成する。
構成したオイラー閉路において、既に訪れた点を飛ばしながら辿る（近道）ことにより、ハミルトン閉路を形成する。

近似度が3/2以下である証明

このアルゴリズムによって生成された解の重みは最適な解の重みに対し3/2以下である。証明のため、 $C$ を巡回セールスマン問題の最適解とする。最適解 $C$ から辺を1つ削除すると全域木となり、その全域木の重みは（最小全域木の定義より）最小全域木の重みより小さくならないため、 $w (T) \leq w (C)$ である。次に、 $O$ の頂点に対し、最適解の経路 $C$ の順に番号を付け、 $C$ の順で奇数番目の辺の集合と、偶数番目の辺の集合の、2つの辺集合に分割する。それぞれの辺の集合は $O$ の最適マッチングに対応し、それぞれの経路の2つの端点と一致する。そして、その最適マッチングの辺の重みは最適解 $C$ によるものであるため、マッチングの重みは最適解の対応する辺の重み以上である。これらの2つの経路の集合は $C$ の辺を2分割するため、経路の集合の1つは $C$ の重みの半分以上であり、それに対応するマッチングは $C$ の重みの半分以下である。最小重み最適マッチングは最小の重みを選択するアルゴリズムであるため、 $w (M) \leq w (C)/2$ が保証される。そして $T$ と $M$ の重みを足すことで、オイラー回路の重みが $3 w (C)/2$ 以下であることがわかる。点を飛ばす処理（近道）によって、重みは増えないため、このアルゴリズムによって生成された経路の重みは最大 $3 w (C)/2$ である^[1]。

近似度の下限

クリストフィードのアルゴリズムの近似度を3/2まで限りなく近づけることができる頂点集合が存在する。そのような1つの入力は $n$ 個の頂点によって形成される道に対し、1つの頂点まで辺の重みを1とし、道において2辺分離れた頂点を結ぶ辺の重みを $1 + ε$ とし（但し、 $ε$ は限りなく0に近い正の数とする）、残りの完全グラフの辺の重みは既に定義された部分グラフの最短経路の重みの和とする。このグラフで形成される最小全域木が重み1の $n - 1$ 本の辺を持ち、ただ2つの奇数次の頂点を持つ。そしてその奇数次の頂点の最適マッチングは重みおよそ $n /2$ の1本の辺によって構築される。最小全域木と最適マッチングの辺を統合した経路は単純閉路であるため、近道は存在せず、重みの和はおよそ $3 n /2$ となる。しかし、最適解は重み $1 + ε$ の $n -2$ 本の辺と、道の端点の辺である重み1の2本の辺によって構成されるため、重みの和は $n + (n - 2) ε$ となり、 $ε$ が十分小さい場合 $n$ に近づく^[3]。したがって、近似度は3/2となる場合が存在する。

例

	辺の重みが三角不等式を満たす、完全グラフ $G$ を与える
	最小全域木 $C$ を構築する
	$T$ の奇数次の頂点集合 $O$ を抽出する
	$O$ の頂点のみを使い、 $G$ の部分グラフを形成する
	部分グラフ内部での、最小重み最適マッチング $M$ を求める
	最適マッチングと最小全域木を統合しオイラー多重グラフ $T \cup M$ = $H$ を得る
	オイラー回路を構築する
	既に訪れた点を飛ばしながら辿りアルゴリズムの出力とする

参考文献

^ ^a ^b ^c Goodrich, Michael T.; Tamassia, Roberto (2015), “18.1.2 The Christofides Approximation Algorithm”, Algorithm Design and Applications, Wiley, pp. 513–514 .
^ 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 (2008), “Metric TSP”, in Kao, Ming-Yang, Encyclopedia of Algorithms}, Springer-Verlag, pp. 517–519, ISBN 9780387307701 .

アルゴリズム

近似度が3/2以下である証明

近似度の下限

例

参考文献

関連項目