約70 年後、最短経路問題を解くために使用される古典的なアルゴリズムであるダイクストラのアルゴリズムが新たな進歩を遂げました。

普遍的な最適性を持つことが証明されています。

どういう意味ですか？

つまり、グラフ構造がいかに複雑であっても、最悪の場合でも理論的には最適なパフォーマンスを実現できるということです。

さらに、この概念が学術界のあらゆるシーケンスアルゴリズムに適用されたのは今回が初めてです。

△画像出典：Quantamagzine

ダイクストラのアルゴリズムは、すべての学部コンピュータサイエンスの学生にとって必須科目であるため、おそらく多くの人がこのアルゴリズムをよく知っているでしょう。

さらに、ダイクストラ法は誕生以来、私たちの日常生活で広く利用されています。例えば、 GoogleマップやAppleマップでは、ユーザーの現在地から目的地までの最適なルートを計算するためにダイクストラ法が使用されています。

コンピュータ ネットワークでは、ルーティング プロトコルで広く使用されています。たとえば、Open Shortest Path First (OSPF) プロトコルは、ダイクストラのアルゴリズムに基づいて、ネットワーク内のデータ パケットの最適な伝送パスを計算します。

通信ネットワーク設計、ロボットの経路計画、物流輸送の最適化などの分野でも見られます。

（関連チュートリアルについては、https://www.youtube.com/watch..._E6eHU を参照してください）

ETH チューリッヒ、CMU、プリンストンなどのトップ大学の研究者を集めたこの研究により、この古典的なアルゴリズムは前例のないレベルにまで高められました。

コロンビア大学のコンピューター科学者ティム・ラフガーデン氏は、この論文を読んだ後、次のように述べた。

これは素晴らしいです。これ以上に魅力的な研究は想像できません。

この論文は、来週開催されるトップクラスの理論コンピュータサイエンス会議であるFOCS 2024（Foundations of Computer Science）で最優秀論文賞を受賞したと伝えられています。

つまり、ダイクストラのアルゴリズムは、単一ソースの最短経路問題を解決するための「ほぼ理想的な」方法であることが証明されました。

それで、この研究はどのように証明され、最適化されたのでしょうか?

70年にわたる古典的アルゴリズムにおける新たなブレークスルー

まず、例を通してダイクストラのアルゴリズムを簡単に見てみましょう。

下の図に示すように、最短経路を見つけるためのダイクストラのアルゴリズムは、おおよそ 4 つのステップに分けられます。

1. 原点から開始: 原点 A を選択します。A から隣接するポイントまでの距離を計算します。たとえば、B までの距離は 1 で、C までの距離は 5 です。より短いパス、つまり最初に B に進むパスを選択します。
2. 探索を続ける：新しい点（B）から、隣接する点までの距離を求め続け、それらの距離をAからBまでの距離に加算します。例えば、AからBまでの距離は1、BからDまでの距離は1なので、AからDまでの合計距離は2（1 + 1 = 2）です。既知の最短経路を更新します。
3. 新しい最短経路を記録する：探索中に短い経路が見つかった場合、記録を更新します。例えば、AからCまでの元の距離は5ですが、BとDを経由してCまでの合計距離は3（1 + 1 + 1 = 3）となり、元の距離よりも短くなるため、AからCまでの距離を3に更新します。
4. すべてのポイントがカバーされるまで手順を繰り返します。アルゴリズムは、すべてのノードへの最短経路が決定されるまで、探索を続けます。そのたびに、最短経路が次の計算で優先され、各ポイントへの最短経路を見つけるために段階的に最適化されます。

△画像出典：Quantamagzine

最終的に、ダイクストラのアルゴリズムは、開始点からネットワーク内の他のすべてのノードまでの最短パスをすばやく見つけることができます。

ダイクストラのアルゴリズムに関する最初の論文では、シンプルだが重要なデータ構造であるヒープが使用されており、後のコンピューター科学者による改良の余地を残していました。

たとえば、1984 年に 2 人のコンピュータ科学者が巧妙なヒープ データ構造を設計し、これによりダイクストラのアルゴリズムは、単一ソースの最短経路問題を解くのに必要な時間に関して理論上の限界、つまり「下限」に到達できるようになりました。

ある意味では、このバージョンのダイクストラ アルゴリズムは最高のものと言えるもので、40 年近くにわたって「標準」となっています。

この最新の論文では、研究者の画期的な発見は依然としてこのヒープ データ構造にあります。

研究者らは、フィボナッチヒープのような一般的に使用されるデータ構造は、理論的には最悪ケースの時間計算量に優れているものの、グラフのローカルな構造特性を十分に活用できないことが多いことを発見しました。

その結果、特定の種類のグラフを処理するときに計算コストが高くなります。

ただし、1984 年のヒープ設計に、最近挿入された項目にすばやくアクセスする機能を追加すると、アルゴリズムの効率が大幅に向上します。

これを解決するために、研究者は特別な「ワーキング セット プロパティ」を備えた新しいヒープ データ構造を提案しました。

いわゆる「ワーキング セット プロパティ」とは、ヒープが操作の局所性を最大限に活用し、最後に挿入された要素の処理を優先して、最小の要素を抽出するコストを削減する能力を指します。

この概念は、ToDo リストを管理するときに新しく追加された緊急タスクを優先順位付けして、作業をより効率的に完了する方法に似ています。

式で表現すると、下の図のようになります。

ヒープ内に挿入され、その後削除される任意の要素 x の場合、その作業セット Wx には、x が挿入された後および x が削除される前に挿入されたすべての要素と、x 自体が含まれます。

この「ワーキング セット プロパティ」を活用することで、新しく設計されたヒープ データ構造は、特に局所性特性を持つグラフ上で、ダイクストラ アルゴリズムの全体的なパフォーマンスを大幅に向上させることができます。

これにより、ダイクストラのアルゴリズムは、最悪の場合だけでなく、あらゆるグラフ構造で良好なパフォーマンスを発揮し、普遍的に最適化されるようになりました。

さらに、この研究は正確な複雑性分析を提供します。

たとえば、著者らは、ワーキングセットプロパティを持つヒープ上でダイクストラアルゴリズムによって実行される比較の数は、O(OPTQ(G)+n+max⁡w∈WG∣FG,w∣) であることを証明しました。

ここで、OPTQ(G) は距離ソート問題を解決するための最適アルゴリズムに必要な比較回数、n は頂点数、|FG,w| は前方エッジの数です。

これにより、アルゴリズムのパフォーマンスの境界がより正確になります。

結論として、これらの成果はグラフアルゴリズムの研究を進歩させただけでなく、実際のアプリケーションにおけるアルゴリズム設計に新たな視点とツールを提供しました。

コーヒーを飲みながら生まれたアルゴリズム

ダイクストラのアルゴリズムの物語は、実は予期せぬひらめきから始まりました。

1956年、26歳のオランダ人コンピュータ科学者、エドスガー・ダイクストラは、新しいコンピュータARMACの計算能力を実証するためのプログラムを作成しようとしていました。

ある日、婚約者とアムステルダムで買い物をしていたダイクストラは、カフェに立ち寄りました。短い休憩中に、ダイクストラは突然ひらめき、最短経路を計算するアルゴリズムを思いつきました。

彼は紙とペンを使わずに、アルゴリズムの詳細を頭の中で導き出すのに約20分を費やした。

彼は晩年のインタビューでこう語っている。

紙とペンがなければ、避けられる複雑さをすべて避けざるを得なくなります。

まさにこのシンプルさと優雅さこそが、その後数十年にわたってダイクストラのアルゴリズムをコンピューター サイエンスの分野で古典として定着させたのです。

エドガー・ダイクストラは極めて影響力のあるコンピュータ科学者であり、最短経路アルゴリズムだけでなく、コンピュータサイエンスの多くの基礎分野への先駆的な貢献でも知られています。

ダイクストラは1930年に化学者の父親と優秀な数学者の母親のもとに生まれました。

1951年、ダイクストラは父親の勧めでケンブリッジ大学に行き、3週間のプログラミングコースを受講しました。この経験が彼のキャリアの方向を変えることになりました。

この間、彼は著名な数学者でありコンピューター科学者でもあるアドリアーン・ファン・ウィーンハーデンと出会い、アムステルダムの数学センターでの仕事の機会を得ました。

ダイクストラはオランダで初めて「プログラマー」として雇用された人物でした。1956年に学業​​を終えた後も数学センターで働き続け、1959年に有名な論文『グラフに関する二つの問題に関する覚書』を発表しました。

この論文では彼が提案した最短経路アルゴリズムが紹介され、後にコンピューターサイエンス分野で最も引用される論文の 1 つとなりました。

ダイクストラのアルゴリズムは非常に洗練されていましたが、当時はコンピュータサイエンスの学術誌がほとんど存在しなかったため、出版プロセスは非常に困難でした。最終的に彼は、創刊間もないNumerische Mathematik誌に論文を発表することを選択しました。

ダイクストラはキャリアを通じて輝かしい名声を獲得し、1972 年にコンピュータ サイエンス界で最も権威のある賞であるチューリング賞を受賞しました。

彼は、プログラミング言語、オペレーティングシステム、並行制御に多くの基本的な貢献をしただけでなく、プログラミング方法論に関する深い考えでも知られています。

彼は、プログラムはデバッグによって修正されるのではなく、最初から正しく設計されるべきだと信じ、プログラムの正確性を重視しました。

しかし、ダイクストラの性格も非常に独特で、賞賛と批判の両方を受け、物議を醸す人物でもありました。

彼はコンピュータサイエンスの教育と研究に関して強い意見を持っており、非常に挑戦的な発言をすることもよくあります。

たとえば、彼は goto ステートメントの使用に反対し、1968 年に有名な記事「Go To ステートメントは有害であると考えられる」を発表しました。これは大きな論争を巻き起こしましたが、彼の見解は最終的に広く受け入れられました。

ダイクストラのアルゴリズムは、出発点から目的地までの最短経路を計算できるだけでなく、出発点からのその他のすべてのノードのソートも提供できます。これはまさに、単一ソースの最短経路問題の解決策です。

その基本的な考え方は、すべてのノードの距離が決定されるまで、現在の距離で最短経路を継続的に探索し、各ノードの最短距離を更新することです。

このアルゴリズムはシンプルかつ効率的であるため、古典的なパス計画ツールとなっています。

MIT のコンピューター科学者エリック・ディメインはかつて次のようにコメントしました。

これは素晴らしいアルゴリズムです。非常に高速で実装も簡単です。

しかし、このアルゴリズムの成功は、その中核となるアイデアだけでなく、データ構造の選択とも切り離せない関係にあります。数十年にわたり、研究者たちはヒープデータ構造を継続的に改良し、アルゴリズム全体のパフォーマンスを継続的に向上させてきました。

今回、改良されたヒープデータ構造が、またしても大きな貢献を果たしたと言えるでしょう。

論文リンク: https://arxiv.org/abs/2311.11793

参考リンク: [1] https://www.quantamagazine.or... [2] https://inference-review.com/...