クリストフィードのアルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/04/14 10:13 UTC 版)
クリストフィードのアルゴリズム（英: Christofides algorithm）は三角不等式を満たす距離を持つグラフにおいて、巡回セールスマン問題の近似解を見つける近似アルゴリズムである[1]。 この近似アルゴリズムの出力は、最適解の重みの3/2以下になることが保証されている。1976年に発案者され、発案者であるNicos Christofidesにちなんで命名された[2]。 2015年現在、距離空間における巡回セールスマン問題に対する多項式時間アルゴリズムの中では、近似度が最良であるアルゴリズムである（一部の特殊な場合では、より良い近似度が存在する事も知られている）。
- ^ 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.
[続きの解説]
「クリストフィードのアルゴリズム」の続きの解説一覧
- 1 クリストフィードのアルゴリズムとは
- 2 クリストフィードのアルゴリズムの概要
- 3 関連項目
- クリストフィードのアルゴリズムのページへのリンク
