Manoj Gupta氏、1996年から続く最短経路問題の壁を突破

インド工科大学ガンディナガル校(IIT Gandhinagar)のManoj Gupta氏が、1996年から計算機科学の分野で続いてきた制約を克服した。同氏のアルゴリズムは、巨大なネットワーク上の2点間の最短距離を、計算時間を増やすことなく、より正確に見積もれるという。

全点対最短経路問題とは

ネットワークとは、関係で結ばれた点の集合である。点は都市やコンピューター、駅、さらには神経細胞や生物学的構造の要素を表すこともある。ナビアプリや交通システム、インターネットのインフラは、日常的にこの種の計算を行っている。ただし、巨大なネットワークで全ての点の組み合わせの距離を求めるとなると、難易度は一気に上がる。この問題はAPSP(All-Pairs Shortest Paths)と呼ばれる。

密に結ばれた大規模ネットワークで正確な距離を全て求めるには、膨大な計算資源が必要になる。このため研究者は、全経路を調べずに信頼できる結果を得る方法を探してきた。1996年にDor氏、Halperin氏、Zwick氏が、推定値が実際の最短距離の2倍を超えないことを保証するアルゴリズムを示した。これが2倍近似である。

多段階サンプリングで改善

だが、この手法には弱点があった。保証が効きやすいのは遠く離れた点同士で、近い点では誤差が大きくなり得た。実際の経路が2区間なのに推定が5区間となれば、2倍の許容範囲を超えてしまう。

Gupta氏は、距離の推定に使う点の選び方を改良した。従来は比較的小さな代表点の集合に頼っていたが、新アルゴリズムは多段階サンプリングを採用し、ネットワークの構造を複数の階層で分析する。これにより、従来は見落とされ得た短い接続も考慮できる。

最も重要なのは、精度の向上にアルゴリズム全体の計算量の増加が伴わない点だ。実行時間を延ばさずに、より信頼できる結果が得られる。

この成果は、通信、交通、SNS、AIシステムなど、大規模ネットワークの解析を要する分野に影響し得る。要素間の距離を速く確実に見積もれれば、依存関係の分析やシステム全体の最適化に役立つ。