最短路を ものすごくはやく 答える方法.

Presentation on theme: "最短路を ものすごくはやく 答える方法."— Presentation transcript:

1 最短路を ものすごくはやく 答える方法

2 背景 目的 ★ カーナビゲーションシステム ★ Web上の検索システム
★ DIMACS Challenge 9 (shortest path) 目的 （始点・終点が指定された）最短路を高速に答える 仮定1：ネットワークは滅多に変化しない 仮定2：最短路の問い合わせは頻繁 →最短路高速検索のための理論・データ構造の構築 ★ ネットワークデータに対して何時間も前処理して良い ★ 最短路を答える際の負荷（時間・メモリ）は小さくしたい

3 google mapの検索例 応答時間は1秒未満

4 （始点終点が指定された）最短路問題 入力：有向グラフG=(V,E)，枝長さ関数d:E→R+始点s，終点t 出力：グラフG上のs-tパス 目的：最短のs-tパスを見つける Dijkstra法 ポテンシャルyの初期設定 S := V while S ≠ φ do yvが最小の点v∈Sを選択 S := S＼{v} for all w:vw∈E and w∈S do if yv + cvw < yw then yw := yv + cvw 計算時間O(m log n)， メモリ使用量O(n + m)

5 最短路応答時間と メモリ使用量の trade off 応答時間 前処理なし →Dijkstra法を適用 このあたりを 狙いたい
あらかじめ全点間最短路を 計算し記憶 →覚えた最短路を答えるだけ メモリ使用量

6

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

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

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

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

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

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

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

14 最短路応答時間 応答時間 テキサス州 平均約36ms 元のデータの大きさ 州ごとに1000対の始点・終点をランダムに選出
応答時間の平均値をプロット 一番大きいテキサス州で平均約36msの応答時間 （Dijkstra法に比べ約100倍の高速化）

15 抽出された道路データの大きさ 付加データの大きさ テキサス州 元データ：約512万 付加データ：約507万 元のデータの大きさ
データの大きさ＝道路の数 抽出されたデータの大きさは，元の大きさとほぼ同じ

16 前処理（道路の抽出）時間 前処理時間 テキサス州 元データ：約512万 前処理時間：約8時間 元のデータの大きさ
最も大きいテキサス州で約8時間

17 結論 今後の課題 最短路検索を高速に行うためのグラフ疎化法を開発 利点：他の探索法との組み合わせが容易，単純
欠点：これ単独ではたいした高速化ではない（高々1000倍程度） 今後の課題 ★ さらなる高速化，目標は1,000,000倍 ★ 他の探索手法との組み合わせ ★ 単純な最短路から拡張 →多目的最短路 →条件付き最短路

18 応答時間：通常のダイクストラ法の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）

19 関連研究【 Highway Hierarchies 】 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倍）

20 関連研究【A. +ランドマーク】 Better Landmarks within Reach Andrew V
関連研究【A*+ランドマーク】 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）：階層ネットワーク法より若干遅い