Hub-Labeling

経路探索に速さを求めて行き着いた先

潤沢なメモリが利用できるなら、どんなノード間でも数nsで最短距離を算出可能

概要

事前計算とクエリに分かれる。「Hubノード」という概念を利用する。

  • 事前計算
    • 「Hubノード」を適切に選ぶ
    • 全ノードに対し、いくつかの「Hubノード」までの最短距離を持たせる
  • クエリ
    • $s$ から $t$ までの最短経路の距離を求めるとする
    • $s$ と $t$ で共通して持っている「Hubノード」を探し、距離を合算
    • その中で最小のものが最短距離
  • そのため「Hubノード」は以下の条件を満たすように選ぶ
    • 全ての2ノードの組で必ず1つは共通Hubノードがある
    • その合計が最短距離となる
(s) s が持つHubノードID  15  23  25  41  ...
    Hubノードまでの距離  10  11   9   6  ...

(t) t が持つHubノードID  11  23  26  41  ...
    Hubノードまでの距離   8  19  11  19  ...
                             ~~      ~~  共通ノードは23,41
                             ↓      ↓  距離を合算
    最短距離は25             30      25

要求スペック

(Hub Labeling Algorithmsより引用)

西ヨーロッパのネットワーク、1800万ノード・2400万リンクで、

  • 事前計算に時間のかからない簡単な実装で
    • ノード1つ当たりに持たせる平均Hubノード数: 98
    • メモリ: 22.5GB
    • 計算時間: 700ns
  • 頑張ってHubノードを厳選すれば、
    • ノード1つ当たりに持たせる平均Hubノード数: 69
    • メモリ: 17.7GB
    • 計算時間: 508ns

多少重いが、今どき用意できないスペックなんてことは全然無い

programming_algorithm/route_search/hub_labeling.txt · 最終更新: 2018/10/15 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0