最短路問題に対する新しいアルゴリズム 階層メッシュ疎化法 (Level-wise Mesh Sparsification: LMS)

Presentation on theme: "最短路問題に対する新しいアルゴリズム 階層メッシュ疎化法 (Level-wise Mesh Sparsification: LMS)"— Presentation transcript:

1 最短路問題に対する新しいアルゴリズム 階層メッシュ疎化法 (Level-wise Mesh Sparsification: LMS)
宇野 毅明（国立情報学研究所） 宮本 裕一郎（上智大学） 久保 幹雄（東京海洋大学）

2 大規模最短路問題に対する アルゴリズム 前処理（preprocessing）とクエリ（query）を分離することによって，高速なクエリを達成
ランドマークを用いた下界の強化 到達限界（reach）を事前に計算しておく方法 多階層のネットワークを作成しておく方法 到達点に最短で行くためには使用しない枝の情報 （ビットベクトル）を利用する方法 前処理（preprocessing）とクエリ（query）を分離することによって，高速なクエリを達成

3 前処理とクエリの分離 前処理（preprocessing） ２０００万点の ネットワーク 補助データ ダイクストラ法たくさん
（数時間；並列で数分） クエリ（query） 補助データ 最短路 ２０００万点の ネットワーク 高速探索 （数ミリ秒）

4 クエリ：通常のダイクストラ法の500倍（4ms）
An Experimental Evaluation of Point-To-Point Shortest Path Calculation on Roadnetworks with Precalculated Edge-Flags Ulrich Lauther (シーメンズ) （１次元）ビットベクトルを用いた高速化 前処理の工夫 再最適化の利用 ビットがすべて０の枝は除く 同じビットベクトルをもつ枝の情報の統合 問題例：600万点，1千600万枝 前処理：約100分，メモリ：１枝あたり6バイト クエリ：通常のダイクストラ法の500倍（4ms）

5 Fast Point-to-Point Shortest Path Computations with Arc-Flags Ekkehard Köhler, Rolf H. Möhring, and Heiko Schilling （ベルリン工科大学） （１次元）ビットベクトルを用いた高速化 前処理法：１つの領域に終点をもつ最短路木の和集合を同時に算出（メモリはくうが高速） 問題例：600万点，1千600万枝 前処理：時間（？），メモリ（１枝あたり250ビッド） クエリ：通常のダイクストラ法の1100倍

6 Highway Hierarchies Star Daniel Delling, Peter Sanders, Dominik Schultes, and Dorothea Wagner （カールスルーエ大） 階層ネットワークによる方法＋ランドマークを用いたA*探索 階層の最上位では距離行列を保管 問題例：ヨーロッパ（1千800万点，4千200万枝）とUSA（2千400万点，5千800万枝） 前処理：ヨーロッパ（21分，1714MB），USA（25分，2013MB） クエリ：ヨーロッパ（0.66ms；20-30倍），USA（0.71ms；15-20倍）

7 Better Landmarks within Reach Andrew V
Better Landmarks within Reach Andrew V. Goldberg, Haim Kaplan, and Renato F. Werneck （マイクロソフト研究所） 到達限界（reach）とA*探索とランドマークを合わせた解法（REAL：Reach+A*+Landmark） 問題例：ヨーロッパ（1千800万点，4千200万枝）とUSA（2千400万点，5千800万枝） 前処理：ヨーロッパ（143分，703MB），USA（142分，1019MB） クエリ：ヨーロッパ（1.8ms），USA（1.5ms）：階層ネットワーク法より若干遅い

8 問題例：西ヨーロッパの道路ネットワーク （1千500万点，3千600万枝） 前処理：8台の並列計算機で24時間 クエリ：最大1000倍程度
High-Performance Multi-Level Graphs Daniel Delling, Martin Holzer, Kirill Muller, Frank Schulz, and Dorothea Wagner （カールスルーエ大） 多レベルグラフを用いた解法 問題例：西ヨーロッパの道路ネットワーク （1千500万点，3千600万枝） 前処理：8台の並列計算機で24時間 クエリ：最大1000倍程度

9 アプローチの利点・弱点 アプローチ 前処理 クエリ スケーラ ビリティ グラフの 疎化 ビットベクトル やや遅い 高速 × ○ 到達限界 中
やや高速 階層ネットワーク 速い ランドマーク 単独では遅い 2次元ビットベクトル 超高速 ◎ 階層メッシュ疎化

10 前提条件，背景など 組合せ最適化問題としての最短路問題が対象 （主に）始点と終点が与えられた場合が対象
キーワード：離散アルゴリズム，グラフアルゴリズム，ネットワーク理論 （主に）始点と終点が与えられた場合が対象 カーナビゲーションやWebでの最短路探索サービスへの適用を主眼に置いている 特徴1：ネットワークのデータは所与（既知） 特徴2：始点と終点が指定されたら高速に最短路を答える 特徴3：近似解ではなく最適解を返す

11 前提条件を加味した考察 全点間最短路をあらかじめ計算し記憶しておけば，メモリにアクセスする時間で最短路を返せる
しかし，ネットワークが大きい場合，全点対を覚えることすら不可能 例：U.S.A.の道路ネットワークの点数は約2000万→全点対数は2000万×2000万＝400×1012 全点間最短路そのものではなく，全点間最短路の中間データのようなものを生成し，始点と終点の問い合わせが来たら中間データから最短路を生成する 生データから最短路を計算するよりも高速に応答できる反面，あらかじめ中間データを生成しておく必要がある 前処理にかける時間が必要 記憶領域も余分に必要（であることが多い）

12 始点と終点が指定された 最短路問に関する考察
遠いところ同士を結ぶ最短路は決まった道を通ることが多い 最短路の計算には基本的にDijkstra法が使われることが多く，Dijkstra法の計算時間はほぼ枝数に比例する よく使われる道（例えば高速道路のようなもの）をあらかじめ抽出し，少ない枝数のネットワークで最短路を計算すれば速い

13 LMSの概要 組合せ最適化問題としての最短路問題に対応
ネットワークデータが与えられた後，数時間かけて中間データを生成，中間データの大きさは元のネットワークデータの数倍程度 【中間データの持ち方が新しい，汎用性もあり】 中間データを記憶した状態で始点と終点が与えられたら，高速（市販のパソコンで数msec）に最短路を返答 【既存の手法と同等以上のスピード】 市販のパソコンで計算できる手軽さ（メモリ使用量など）

14 基本的な考え方1 オレンジ枠の外側に始点および終点がある最短路をすべて求める（黒線）
赤枠の内側で最短路に使われている道をすべて覚える（黒太線） 直感的解釈：覚えた道は赤枠から遠いところ同士を結ぶ最短路で使われる道

15 基本的な考え方1 オレンジ枠の外側に始点および終点がある最短路を求める場合には
赤枠の内側では覚えた線（黒太線）のみを使っても最短路を求めることができる →最短路計算で使われるデータが少なくなる

16 基本的な考え方2 位置をずらした枠で同様に，遠いところ同士の最短路に使われる道を覚えておけば 最短路計算で使われるデータがさらに少なくなる

17 基本的な考え方2 たくさんの枠で同様に，遠いところ同士の最短路に使われる道を覚えておけば 最短路計算で使われるデータがさらに少なくなる

18 基本的な考え方3 枠の大きさは大きくても小さくてもよい 大きい枠→覚える道は少ない : 始点や終点の近くでは使えない
大きい枠→覚える道は少ない : 始点や終点の近くでは使えない 小さい枠→覚える道は多い : 始点や終点の近くでも使える

19 基本的な考え方（まとめ） いろいろな大きさの枠で，遠いところ同士の最短路で使われる道を覚え，
始点と終点が指定されたら，なるべく道数の少ないネットワークを構成し （大きい枠を優先的に使う），最短路を計算する

20 West Virginiaへの適用例 300146ノード，657716アーク Dijkstra法＋binary heapで約1秒かかる

21 LMSで用意するネットワーク（の一部）

22 始点と終点が指定された場合（１） ピンクの線が最短路 アークの数は約10000（元のグラフの約1/60）
計算時間は約15ミリ秒→約60倍の高速化

23 始点と終点が指定された場合（２） 指定される始点と終点が異なれば，計算に使われるネットワークも異なる

24 今後 以上は基本アイディアを説明しただけであり，細かい工夫はさらにいくつか入っている，特に前処理（中間データとしてのネットワークを作る処理）に関しては説明を省いた 計算実験結果に関して，まだパラメータチューニングをしておらず，すでに考えてある細かいアイディアも入れてないので，計算速度はさらに数倍速くなる可能性がある