ネットワークの地理的な疎密性を利用した最短路探索

摘要

最短路問題は代表的な最適化問題の一つであり，現在に至るまで様々な観点から研究され，実生活においても広く利用されている．最短路問題はダイクストラ法を用いて多項式オーダの計算量で解くことができる．しかし，極めて大規模なネットワークにおいては，たとえ多項式オーダの計算量であっても，実用的な時間で解くことが困難である．そこで，大規模ネットワークにおいても，実用的な時間で最短路を求める方法が必要とされている．この問題に対するアプローチとして，ネットワークの特徴を利用して最短路探索を効率する手法が一般的である．道路ネットワークのような頻繁に更新されることがないネットワークに対しては，ネットワークに適切な前処理を施しておくことでクエリに対して高速に最短路を出力するアプローチが有効であることが知られている．また，最短路探索に関しては，最短路の近似解でも十分に有益な場合も多い，そこで，本稿では，ネットワークの地理的な疎密性に着目し，前処理として疎密性を利用したクラスタリングを基にネットワークの規模を縮小し，クエリに対しては疎ネットワーク上の最短路を求めて元のネットワーク上で再構成することで，実用的な最短路の近似解を厳密解よりも短時間で出力するアルゴリズムを設計した．