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

P≠NP
17
GIGAZINE(ギガジン) @gigazine

数学の難問「巡回セールスマン問題」の近似解を求める最良のアルゴリズムが数十年ぶりに更新される 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

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

2020-10-12 12:51:47
Hana @O_LionRock_1997

0.0000000000000000000000000000000002%人類が進化したらしい twitter.com/gigazine/statu…

2020-10-12 09:05:53
ギャランドゥ14R @kzzr1400

ソートと言い、研究し尽くされたと思っていたアルゴリズムを雑巾を絞るように考え続けている人達がいるんだ。 自分は無理かなw twitter.com/gigazine/statu…

2020-10-12 14:50:56
古癒瑠璃(こゆるり)@カクヨムにて新作公開予定 @koyururi

『理系が恋に落ちたので証明してみた』でデートコース算出していた奴! デートコース算出していた奴じゃないか!! 数学の難問「巡回セールスマン問題」の近似解を求める最良のアルゴリズムが数十年ぶりに更新される - GIGAZINE gigazine.net/news/20201012-…

2020-10-12 23:49:27
Ikemen Mas Kot @maskot1977

@gigazine わーい!これで出張経費をもっと安くできるね!

2020-10-12 12:36:42
そた🌂 @_sotaatos

@maskot1977 @gigazine 0.0000000000000000000000000000000002%しか安くならない...

2020-10-12 22:29:58

コメント

柏木彰二 @GmailShoji 12日前
>巡回セールスマン問題について、「これは『問題』ではなく『中毒』です」と述べています。 こういう文章、すごく好き
4
まさご叔父さん @masago53 12日前
まぁ要素数が増えると年単位で計算時間かかるとかあるから微量でも確実に改善されるなら意義はあるよね
0
さ​ろ​げ​ー​と @surrogatepair 12日前
数億年単位で考えても誤差どころかゼロに等しい微々たる改善だけど、この「0.0000000000000000000000000000000002%」という数値を計算できたという点にまず敬意を評したい
9
蠢犇 @ugomekihisimeki 12日前
実利では測定誤差以上の改善はないが探索され尽くした分野での進展という点で意義はある
0
緇隰 娉遌齋 @yourenzhu 12日前
英語だとsalesmanではなくsalespersonなのが、今では当たり前なのかもしれないけど、20年以上前には面白いと感じた。
0
あたぎ @totogetter 12日前
多分これが一番早いと思います
0
Ling-mu @Ling_mu 12日前
このわずかの差をちゃんと数値として証明できたのが凄いよなぁ。
0
順三朗 @junzabroP 12日前
SUGEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE!(わかってない)
0
kisara @kisara50 12日前
雑巾を絞る比喩でフィーリングで適当に言ってるわけじゃなく厳密な定量化で水分子1ヶも絞れて無さそうなの初めて見た
6
COSY8SD @COSY8SD 12日前
一方、D-Waveでは量子コンピュータをレンタルしていた
0
Tの人@アホの子 @Aho_The_T 12日前
これ改善できる余地がまだあったっていうのが一番の発見って理解であってる?
2