クリストフィードのアルゴリズム
Sign in to savealgorithm that approximates solutions to the travellng salesman problem on a metric space, guaranteeing that its solutions will be within 1½ of the optimal solution length; discovered by Nicos Christofides in 1976
Wikidata facts
- Instance of
- algorithm
Show 1 more fact
- facet of
- travelling salesperson problem
Sources (2)
via Wikidata · CC0
Article · 日本語
クリストフィードのアルゴリズム（英: Christofides algorithm）は三角不等式を満たす距離を持つグラフにおいて、巡回セールスマン問題の近似解を見つける近似アルゴリズムである。この近似アルゴリズムの出力は、最適解の重みの3/2以下になることが保証されている。1976年に発案者され、発案者であるNicos Christofidesにちなんで命名された。2015年現在、距離空間における巡回セールスマン問題に対する多項式時間アルゴリズムの中では、近似度が最良であるアルゴリズムである（一部の特殊な場合では、より良い近似度が存在する事も知られている）。
Abstract from DBpedia / Wikipedia · CC BY-SA