「巡回セールスマン問題」とは、
都市の集合と各2都市間の移動コスト（たとえば距離）
が与えられたとき、全ての都市をちょうど一度ずつ巡り
出発地に戻る巡回路のうちで総移動コストが
最小のものを求めるという問題を指します。
巡回セールスマン問題｜Wikipedia
https://ja.wikipedia.org/wiki/巡回セールスマン問題
この問題の最良のアルゴリズムは、
1976年に発見されたクリストフィードのアルゴリズムだと
言われてきたそうです。
2010年、ジョージア工科大学の研究チームは、
クリストフィードのアルゴリズムを改善した
新たなアルゴリズムを開発。
今度は、この新たなアルゴリズムがクリストフィードの
アルゴリズムより優れていることを証明することが
難問として立ちはだかったそう。
この研究チームの一人の研究者が移ったことで
ついに証明ができたのだそうですが、
そのきっかけとは？
そして、その証明の結果とは？
詳しくはリンク記事でご確認ください。
巡回セールスマン問題とは、「複数の都市を移動するセールスマンが全都市をちょうど一度ずつ巡り、総移動コストが最小の経路を求める」という数学の難問です。長年にわたり「クリストフィードのアルゴリズム」が巡回セールスマン問題の近似度が最も高いアルゴリズムとされてきましたが、新たに「クリストフィードのアルゴリズムを上回る近似度のアルゴリズムがあると証明された」という論文を、コンピューターサイエンスの研究者が発表しています。
情報源: 数学の難問「巡回セールスマン問題」の近似解を求める最良のアルゴリズムが数十年ぶりに更新される
[PR]