Wikipedia

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

クリストフィードのアルゴリズム（英: 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) ≥ w(ux)が成立する。

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

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

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

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

近似度の下限 編集

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

例 編集

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

参考文献 編集

  1. ^ a b c Goodrich, Michael T.; Tamassia, Roberto (2015), “18.1.2 The Christofides Approximation Algorithm”, Algorithm Design and Applications, Wiley, pp. 513–514 .
  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 (2008), “Metric TSP”, in Kao, Ming-Yang, Encyclopedia of Algorithms}, Springer-Verlag, pp. 517–519, ISBN 9780387307701, https://books.google.com/books?id=i3S9_GnHZwYC&pg=PA517 .

関連項目 編集

「https://ja.wikipedia.org/w/index.php?title=クリストフィードのアルゴリズム&oldid=84958844」から取得