巡回セールスマン問題の効率が0.0000000000000000000000000000000002％改善！

数学の難問「巡回セールスマン問題」の近似解を求める最良のアルゴリズムが数十年ぶりに更新される gigaz.in/3djAmS5

2020-10-12 08:00:14

リンク GIGAZINE 数学の難問「巡回セールスマン問題」の近似解を求める最良のアルゴリズムが数十年ぶりに更新される巡回セールスマン問題とは、「複数の都市を移動するセールスマンが全都市をちょうど一度ずつ巡り、総移動コストが最小の経路を求める」という数学の難問です。長年にわたり「クリストフィードのアルゴリズム」が巡回セールスマン問題の近似度が最も高いアルゴリズムとされてきましたが、新たに「クリストフィードのアルゴリズムを上回る近似度のアルゴリズムがあると証明された」という論文を、コンピューターサイエンスの研究者が発表しています。 249 users 292

しんじ@理科実験あそびプロジェクト復興のためお仕事承り中 @oekakimaestro

10年前に発見された手法が従来最良とされていたアルゴリズムよりも良い近似値を与えると証明するのに年月がかかり、結局はベンチマークではわからないような微微たる改善だったが、まだまだ理解を深める余地があるということがわかったという話 twitter.com/gigazine/statu…

2020-10-12 23:41:47

武内　修 @osamu_takeuchi

彼らは新たなアルゴリズムがより優れていることを「証明する方法を探す」ことに１０年間を費やし、最終的に 0.0000000000000000000000000000000002％だけ改善されることが明らかになった。下手なＳＦよりロマンのある話。（と思える人は研究者に向いてるのかも？） twitter.com/gigazine/statu…

2020-10-12 12:51:47