なんとなく最短ルートって、昔からほぼ変わらないもんだと思ってたんだけど、清華大学の研究チームが65年ぶりにその常識をちょっとだけ更新したらしいんだよね😮💨
そもそもダイクストラのアルゴリズムって？
「ダイクストラ」って聞いたことある？これはコンピュータとか数学で使われる、ある地点から別の地点までの一番短い道を見つける方法のこと。地図アプリのルート検索にも使われるんだって。
このアルゴリズム、1959年に考えられてからずっと愛されてて、”最短経路問題”の基本だよね✨
で、新しい発見って何？
清華大学のチームは、このダイクストラのアルゴリズムに挑戦して、同じ問題をもっと速く解く方法を見つけたらしいの💡
ポイントは「計算スピードが向上したこと」で、具体的には昔の方法より少しだけ効率よくできるようになったって感じ。
でも、この”少しだけ”がめちゃ大事で、
- めちゃくちゃ大きなネットワークや
- 複雑なグラフの問題とか
で使うと、処理時間がかなり短くなる可能性があるんだよね👍
なんでそんなに注目されてるの？
実は、最短経路問題はずーっと研究されてるのに、ダイクストラのアルゴリズムを超えるものはほとんど見つかってなかったんだ😳
だから、65年も変わらなかった「壁」を破るってことは、地味だけど数学やコンピュータの世界では結構すごい出来事なの💭
どうやって速くなったの？
仕組みをざっくり言うと、
- 計算のための「データの扱い方」を工夫したり
- 一部の無駄な計算を減らしたり
してるらしいんだけど、正直わたしも「うーん？」って感じで💦
でも、こういう細かい改良の積み重ねが、将来的にはAIやビッグデータの解析、交通システムの最適化とかに役立つかもって話なの✨
まとめると…？
- ダイクストラのアルゴリズムは65年以上使われてきた定番の最短経路探索法
- 清華大学が新しくて少しだけ速い代替アルゴリズムを発表した
- この進展は大きなネットワークや複雑な問題で効果を発揮しそう
- 地味だけど長年変わらなかった壁を乗り越えた、結構すごい話
なんとなく数学とかプログラムの世界って難しそうだけど、こういう発見が日常の便利さにつながってるんだな〜って思うと面白いよね🌸
ちょっとした進歩が未来の技術を支えてるって、なんだかいい感じだなって思ったよ💗
はてな
コメント
クリス
論文はコレ：https://arxiv.org/abs/2504.17033 2ヶ月前にRedditで話題に、コメントは「疎グラフならダイクストラより速いけど一般的には遅い」って感じ。
グレース
多くの経路探索アルゴリズムはリストの最初を全部ソートせず、バッチで管理してるし、次に探索するノードも最後に見つけたものを優先することが多い。 大抵はトップ数個だけソートして、他は無視することもある。 これは実装者にはよく知られてる話。
リリー
結局、彼らはビッグO記法の壁を破ったのか、それとも本当に新しいものなのか気になる。
ハンナ
面白いテーマだけど、チャットGPTが作ったASCII表をただ貼るだけは手抜きすぎ。
ハンナ
チャットGPTが作った記事かよ。
ベン
この新しいアルゴリズムには名前あるの？
キンバリー
mとnのどんな値のときにダイクストラと同じになるか、誰か検証してくれない？ 大雑把にはm + n log n = m * log^(2/3) nって感じ。
エマ
（余談だけど、Redditのマークアップが括弧内のべき乗を認識してるの今気づいた…俺の数学脳まだ目覚めてない）
ロバート
かなり疎なグラフでないと意味なさそうだけど、実際どれだけかは計算しづらい。 Big-Oだからオーバーヘッドは含まれてないけど、出発点としてはアリかなと。
エイダン
予想：来年にはLeetCodeの難問になって、FAANG面接では30分で解けって言われるぞ。 /s
レオ
そろそろアップデートの時間だな。
ノーラン
JIAN YANG！ ミドルアウトA*丸パクリだな、クソったれ。
サム
よくやった。 あいつらマジでムカつく。
