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

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

アルゴリズム 
について巡回セールスマン問題を考える。頂点集合を、その完全グラフをとし、に含まれる全ての辺に対し定義される非負の重み集合をとする。三角不等式より任意の3つの点に対し、が成立する。

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

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

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

例

参考文献

関連項目 
 巡回セールスマン問題
 最小全域木
 オイラー路

グラフアルゴリズム
近似アルゴリズム
巡回セールスマン問題
全域木
組合せ最適化
数学に関する記事