[[Arc-Flag]]

Arc-Flag

Arcflagsは、2点間の最短経路探索を高速化する1手法。

概要

  • 事前計算をし、その情報を利用して経路探索を高速に行う
    • つまり、常に変化する(ダイナミックな)グラフには不適当
  1. グラフをいくつかのエリアに分割する
  2. 各リンクに、「自身がエリアAに含まれるノードへの最短経路に利用されることがあるか」という情報をエリア毎に持たせる
  3. sからtへの経路探索を行う場合は、tの属するエリアのフラグが立ったリンクのみを探索する
                  | AreaA
 s --- v ---...---|- 
  `--- u ...      |   t

 * リンク<s-v>は、目的ノードtが存在するエリアA内の、
   どれかのノードへの最短経路に使われることが事前計算によりわかっている
 * リンク<s-u>は、エリアA内のどのノードへの最短経路にも使われないことがわかっている
 * sから探索を広げる際、<s-u>は探索しない
  • アルゴリズムは比較的単純
    • 特にクエリ部分は、Dijkstraに条件分岐を1つ付け加えるだけでよい
  • 全てのリンクに情報を持たせるため、メモリがそこそこ必要
  • 事前計算時間もそこそこ必要

各段階での処理

エリアの分割方法

できるだけ、1つのエリア内のノードへ至る経路は類似していた方がいい。

あるエリア内の2つのノードvとw、それとは離れた場所の2つのリンクlとmについて、vに行くにはlを通る経路が、wに行くにはmを通る経路が最短となってしまうと、クエリ時に探索するリンクが増えて時間がかかってしまう。

エリアAに属するノードへの最短経路で類似度の低いものが複数あると、
探索時にはその全てを探索しなければならないことになる。
この例のように2通りだけならまだいいが、候補がもっと増えると、計算時間に影響が出る。
  AreaA|
v -----|---...-o---- s
       |            /
  w ---|---...-o---'

エリア内や、できるだけ近い箇所で分岐するようなノードばかりのエリアで分割できれば、
1本道(や、ごく少数)の探索で済むため、高速化の効果は大きい
v -----|---...-o---- s
    /
  w

避けられない部分もあるが、できるだけ望ましいエリア分割をおこなうにはどうするか。

基本的に道路ネットワークであれば、地理的に近いノードは最短経路も似通いやすいため、それで評価しても十分実用的。

  • グリッドで分割
    • 最も単純
    • 1つのエリアに含まれるノード数がまちまちになりやすい
  • 四分木で所定のノード数以下になるまで分割
    • ノード数がやや均一になる
  • kd木で分割
    • ノード数が均一になる
  • グラフの最小カットを、任意のサイズorエリア数になるまで行う

FIXME まだあまり深く調べられてない。

事前計算方法

  1. 逆グラフを作る(有向リンクの方向が逆向きのグラフ)
  2. 逆グラフ上で、各エリアにつき、そのエリアから他のエリアに出るリンクを始点とし、エリア外の全ノードがFIXされるまでDijkstra等で最短経路探索を行う
  3. 最短経路として使われたリンクが、元のグラフで、そのエリアへの最短経路に用いられるリンクである

FIXME まだあまり深く調べられてない。

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