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