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エリア数になるまで行う
  • カット (グラフ理論) - Wikipedia

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

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

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