巡回セールスマン問題とは、「複数の都市を移動するセールスマンが全都市をちょうど一度ずつ巡り、総移動コストが最小の経路を求める」という数学の難問です。長年にわたり「クリストフィードのアルゴリズム」が巡回セールスマン問題の近似度が最も高いアルゴリズムとされてきましたが、新たに「クリストフィードのアルゴリズムを上回る近似度のアルゴリズムがあると証明された」という論文を、コンピューターサイエンスの研究者が発表しています。 [2007.01409] A (Slightly) Improved Approximation Algorithm for Metric TSP https://arxiv.org/abs/2007.01409 Computer Scientists Break Traveling Salesperson Record | Quanta Magazine https://www
![数学の難問「巡回セールスマン問題」の近似解を求める最良のアルゴリズムが数十年ぶりに更新される](https://cdn-ak-scissors.b.st-hatena.com/image/square/4068edefec82fd02541a46eb42fa14dcc2a57bcc/height=288;version=1;width=512/https%3A%2F%2Fi.gzn.jp%2Fimg%2F2020%2F10%2F12%2Fbreak-traveling-salesperson-record%2F00_m.jpg)