前処理(ALT) v.s. そのまま解く

前処理アルゴリズムは複数存在するが、その多くは前処理後の性能を向上するために長時間の前処理が必要となる。またメモリ要求量が大きく扱いづらいと行った弱点も見られる。

そこで比較的シンプルなアルゴリズムである ALT に注目してみた。
Goldberg によるスライド(PDF)の32ページ目を貼付けてみる。



ここで Bidirectional-Dijkstra と ALT を比較してみよう。

               [Bi-DIJK]     [ALT]
 query-time    340.74 ms  → 12.05 ms   (x 28.28 )
prepro-time         0 min →     4 min  (+ 4 min.)
     memory        28 MB  →   132 MB   (+ 104 MB)

必要なメモリ要求量は Landmarks x #nodes x 4 で求められる。
(132 [MB] - 28 [MB]) / 16 [Landmarks] / 1.6M [nodes] ≈ 4

また、前処理にはクエリの数百倍(4 [min.] / 340.74 [ms] ≈ 700)の処理時間がかかるようだ。

ある一定時間以内の枝長の変化を考慮しての経路探索する際にどちらを選択するべきかを単純化してグラフ化すると次のようになる。例えば、10分で処理できるクエリ数は Bidirectional-Dijkstra の 1800 程に対して、ALT では 30000 にも及ぶ。


実際には結果を加工する時間が必要となるので、これほどまでの差にはならないだろう。