科学者らが地図を横断するための最良のアルゴリズムを確立

この物語 のオリジナル版はQuanta Magazineに掲載されました。

長い間同じ通勤ルートを続けていると、おそらく最適なルートに落ち着いているでしょう。しかし、「最適」というのは曖昧な概念です。ある日、事故や道路の通行止めが発生し、最速のルートが最遅のルートになってしまうかもしれません。

このようなシナリオは、コンピュータが問題を解くために用いる段階的な手順であるアルゴリズムを開発する研究者にとっても課題です。特定の問題を解くアルゴリズムは数多く存在し、どれが最適かという問いは、苛立たしいほど曖昧になりがちです。

例えば、2点間の最速ルートを見つけるように設計されたアルゴリズムを想像してみてください。そのようなアルゴリズムを失敗しないように設計する方法は数多くあります。成功するアルゴリズムは、ロンドンで使おうがロサンゼルスで使おうが、ラッシュアワーで使おうが真夜中で使おうが、常に最速ルートを返します。

しかし、これらのアルゴリズムはすべて同じではありません。それぞれのアルゴリズムが正しい答えを見つけるのにかかる時間は、使用される場所や時間によって異なります。また、あるアルゴリズムにとって難しいケースが、別のアルゴリズムにとっては簡単な場合もあります。理想的には、常に他のアルゴリズムよりも高速に実行されるアルゴリズムが望ましいでしょう。

ほとんどの問題において、そのようなユニコーンを見つけることは不可能です。しかし、新たな証明は、典型的な経路探索問題において、あるアルゴリズムが理想に近いことを示しています。最悪の交通パターンを想定すると、あらゆる道路網において最善のアプローチとなります。さらに、このアルゴリズムは70年近くも前から存在し、学部レベルのコンピュータサイエンスのカリキュラムの定番となっています。この新しい研究は、来週開催される2024年コンピュータサイエンス基礎シンポジウムで最優秀論文賞を受賞する予定です。

「素晴らしいですね」とコロンビア大学のコンピューター科学者、ティム・ラフガーデン氏は語った。「学部課程で学生に教えるアルゴリズムの問​​題に関して、これほど説得力のある研究論文は想像できません。」

ヒープとバウンド

この象徴的な経路探索アルゴリズムの物語は、ある回り道から始まりました。1956年、当時26歳だったオランダのコンピュータ科学者、エドガー・ダイクストラは、当時最新のコンピュータ「ARMAC」の性能を披露するプログラムを書きたいと考えていました。アムステルダムで婚約者と買い物をしていた時、休憩のためにカフェに立ち寄りました。そこで、現在彼の名前を冠するアルゴリズムのアイデアを思いつきました。筆記具が手元になかったため、20分かけて頭の中で詳細を練り上げていったのです。

ダイクストラは晩年のインタビューで、自身のアルゴリズムが今もなお人気を博しているのは、その異例の誕生秘話によるところが大きいと述べた。「鉛筆と紙がなければ、避けられるはずの複雑さをほとんど避けざるを得なくなるのです」と彼は言った。

ダイクストラ法は、単に一つの目的地への最速ルートを教えてくれるだけではありません。現在地から、あなたが訪れたいと思う可能性のある他のすべての地点までの移動時間を、順序付けされたリストで提示します。これは、研究者が「単一起点最短経路問題」と呼ぶ問題の解決策です。このアルゴリズムは、グラフと呼ばれる抽象化された道路地図上で動作します。グラフとは、相互に接続された点（頂点）のネットワークで、頂点間のリンクには数値（重み）が付けられています。これらの重みは、ネットワーク内の各道路を通過するのに必要な時間を表す場合があり、交通パターンによって変化する可能性があります。重みが大きいほど、その経路を通過するのに時間がかかります。

ダイクストラ法の仕組みを理解するには、グラフ上を歩き回りながら、出発点から新しい頂点までの移動時間をメモ用紙に書き留めていく自分を想像してみてください。次にどの方向に進むか迷った時は、一番近い、まだ訪れていない頂点に向かいましょう。もし、ある頂点へのより速いルートを見つけたら、新しい時間をメモし、古いルートを消します。最速のルートを見つけたと確信できたら、移動時間をメモから別の、より見やすいリストに移しましょう。

「これは素晴らしいアルゴリズムです」と、マサチューセッツ工科大学のコンピュータ科学者、エリック・デメイン氏は述べた。「非常に高速で、シンプルで、実装も簡単です。」

この手順を実践するには、メモを整理するためのシステム、つまりコンピュータサイエンスの用語で言うデータ構造を決める必要があります。これは些細な技術的な詳細のように聞こえるかもしれませんが、エントリを編集または削除する必要があるたびにメモを検索する時間は、アルゴリズムの全体的な実行時間に大きな影響を与える可能性があります。

ダイクストラの論文では、改善の余地を残したシンプルなデータ構造が用いられていました。その後数十年にわたり、研究者たちはより優れたデータ構造を開発しました。これは「ヒープ」と呼ばれる愛称で呼ばれ、特定の要素が他の要素よりも見つけやすい構造です。ダイクストラのアルゴリズムでは、残っている最も近い頂点のエントリを削除するだけで済むという点が、ヒープの活用に活かされています。「ヒープとは基本的に、この処理を非常に高速に実行できるデータ構造です」と、ブルガリアのソフィアにあるコンピュータ科学・人工知能・技術研究所（INSAIT）の研究者であるヴァーツラフ・ロジョン氏は述べています。

1984年、2人のコンピュータ科学者が巧妙なヒープ設計を開発し、ダイクストラ法が単一ソース最短経路問題を解くのに必要な時間の理論的な限界、つまり「下限」に到達できるようにしました。ある特定の意味では、このダイクストラ法は考え得る最良のものでした。これは、約40年間、この問題の標準的なバージョンに関する最終的な結論でした。状況が変わったのは、少数の研究者が「最良」の意味を詳細に検討した時でした。

最善の行動

研究者は通常、アルゴリズムを比較する際に、最悪のシナリオでのパフォーマンスを研究します。世界で最も複雑な街路網を想像してみてください。そこに、特に複雑な交通パターンを加えてみてください。このような極端な状況で最速の経路を見つけたいのであれば、1984年版のダイクストラのアルゴリズムは間違いなく無敵です。

しかし、願わくば、あなたの街が世界最悪の街路網ではないことを願います。そこで、あなたはこう尋ねるかもしれません。「あらゆる道路網で無敵のアルゴリズムは存在するのか？」この問いに答えるための第一歩は、各ネットワークには最悪の交通パターンが存在するという保守的な仮定を立てることです。そして、アルゴリズムが、あらゆるグラフレイアウトにおいて、最悪の重み付けを想定した最速の経路を見つけられるようにします。研究者はこの条件を「普遍最適性」と呼んでいます。もし、グラフ上のある点から別の点へ移動するという単純な問題に対して、普遍的に最適なアルゴリズムがあれば、世界中のあらゆる都市のラッシュアワーの交通渋滞を回避できるでしょう。

「信じられないほど素晴らしい話だ」とINSAITとスイス連邦工科大学チューリッヒ校（ETHチューリッヒ）に所属するコンピューター科学者、ベルンハルト・ホイプラー氏は言う。

ホープラー氏は、2010年代半ばに助成金申請書を書いている最中に、普遍最適性の可能性に魅了された。多くの研究者は仕事のその部分を退屈に感じるが、ホープラー氏はそれをチャンスと捉えた。「懐疑心を捨て、ただ大きな夢を見ることができるのです」と彼は語った。

2021年、ホイプラーと2人の大学院生が、いくつかの重要なグラフ問題に対して普遍最適アルゴリズムを構築できることを証明したことで、その夢は実現しました。彼は、古典的な単一ソース最短経路問題でも同じ条件が達成可能かどうかを問うことを思いつきませんでした。それは、別の大学院生が大きな夢を抱くまで待たなければなりませんでした。

勝利への最短道

2023年初頭、ロジョンはETHチューリッヒの大学院課程を終えようとしていた。彼は最悪ケース解析を別の文脈でさらに発展させることに関する論文を書き上げたばかりで、共著者で当時コペンハーゲン大学の大学院生だったヤクブ・テテクと共に、新たなアイデアを練り上げていた。ロジョンは、単一ソース最短経路問題に対する普遍的最適アルゴリズムを考案することを提案した。

「『いや、でもそれは無理だ。絶対に無理だ』と言いました」とテテクは振り返る。しかし、ロジョンが彼を説得し、試してみることにした。春には、ロジョンとテテクがチェコ共和国で高校生だった頃に知り合った、チューリッヒ工科大学の大学院生、リチャード・フラディークが加わり、チームは3人に増えた。

3人はダイクストラのアルゴリズムとそれが使用するヒープの様々な側面を改良し、普遍最適解を間に合わせで作り上げた。しかし、結果として得られたアルゴリズムは複雑で、普遍最適性を達成するために実際に必要な条件を正確に特定することはできなかった。包括的かつ厳密な証明が重視される分野において、これだけでは不十分だったのだ。

3人の学生は数学的ネットワークから社会的なネットワークへと話題を移した。ロジョンは、ニューヨークで同僚を訪ねていた際に、ハウプラーとこの問題について議論を始めていた。ハウプラーはそこから休暇でパナマへ飛んだが、まだこの問題を脇に置く準備はできていなかった。

「本当に休暇だったよ」と彼は言った。「でも、考えることは止まらないからね」

ホープラーの旅が始まって数日後、Zoomでの会議中に4人からなるチームは新たなアプローチを決定した。彼らはデータ構造の選択に主眼を置くことにした。すぐに、これで十分かもしれない、ダイクストラのアルゴリズムの残りの部分はそのままでいいのではないかと考え始めた。そして1ヶ月以内に、彼らはそれを証明した。

鍵となる要素は、一部のデータ構造に備わっている特殊な性質、つまり最近追加された項目に素早くアクセスできる性質であることが判明しました。この性質を持つヒープは20年以上前に初めて構築されましたが、その後何年もの間、誰もその特性を十分に活用していませんでした。4人の研究者は、この新しい性質と1984年のヒープの他のすべての特徴を備えたデータ構造を構築するだけでよいことを証明しました。彼らに必要なのは、それを設計することだけでした。

チームに最後に加わったのは、プリンストン大学のコンピュータ科学者で、1984年のあの特別なヒープの発明者の一人であるロバート・タージャンでした。タージャンはこの分野で最高の栄誉とされるチューリング賞を受賞しており、2000年代後半にはホイプラーの指導者でもありました。タージャンが5月にチューリッヒを訪れたとき、ホイプラーは得意料理であるフォンデュに彼を招待し、新しい最短経路プロジェクトについて話しました。タージャンはすぐに参加を決めました。

5人の研究者たちは、必要な特性をすべて備えたヒープデータ構造の開発に着手しました。当初は扱いにくい設計でしたが、少しずつ改良を重ね、最終的に満足のいく構造に仕上げました。「見直すたびに、少しずつシンプルにすることができました」とロジョン氏は語ります。「最終的にこれほどシンプルになったことに、私は本当に驚きました。」

ダイクストラ法のいくつかのバリエーションは、Googleマップなどのソフトウェアで実世界で使用されています。今回の新たな結果は、理論的な最適性の保証以外にも多くの考慮事項があるため、そのような実用的な応用にはおそらくならないでしょう。しかし、研究者が最適性を研究する方法を変え、通常の最悪ケース分析の先を見据えるよう促す可能性があります。多くの場合、アルゴリズムは複雑さを増すことでより強い保証を実現します。今回の新たな結果は、このようなより強い保証を備えた単純なアルゴリズムが、研究者がこれまで考えていたよりも広く普及している可能性があることを示唆しています。研究チームは既に他に2つの例を特定しています。

「全体的なコンセプトは非常に魅力的です」とタージャン氏は述べた。「これをどこまで実現できるかはまだ分かりません。」

オリジナルストーリーは、数学、物理科学、生命科学の研究の進展や動向を取り上げることで科学に対する一般の理解を深めることを使命とする、 シモンズ財団の編集上独立した出版物であるQuanta Magazineから許可を得て転載されました。