巡回セールスマン問題

巡回セールスマン問題とは「複数の都市を移動するセールスマンが全都市をちょうど一度ずつ巡り、総移動コストが最小の経路を求める」という数学の難問です。

1976年に発見された「クリストフィードのアルゴリズム」が巡回セールスマン問題の近似度が最も高いアルゴリズムとされてきました。

44年ぶりに「クリストフィードのアルゴリズムを上回る近似度のアルゴリズムがあると証明された」という論文を、コンピューターサイエンスの研究者が発表しています。

Computer Scientists

https://www.quantamagazine.org/computer-scientists-break-traveling-salesperson-record-20201008/

ただし、分析の結果、新たなアルゴリズムがクリストフィードのアルゴリズムを上回っているのは、ほんの「0.2 billionth of a trillionth of a trillionth of a percent(0.0000000000000000000000000000000002％)」と判明したそうです。

日々、様々な研究者が、様々な難問を解く努力をしているんだな～と思わされました。すぐに身近に感じられることではないでしょうが、この積み重ねで、世の中が便利になっていくんだと思います。