[[ALT]]

ALT

2点間の最短経路探索を高速化する。

ベースはA*。A*はDijkstraを一般化したアルゴリズム。

  • Dijkstraは「出発点からここまでの距離」が小さい方から探索する
  • A*は、「出発点からここまでの距離」+「ここから目的地までの予測距離」で比較する
    • 予測距離にはヒューリスティック関数を用いる
    • より良い関数を用いると、より速く探索できるようになる
  • ALTは、A*で用いるヒューリスティック関数についてのアルゴリズム
  • Goldberg, Andrew V., and Chris Harrelson. “Computing the shortest path: A search meets graph theory.” Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2005.

概要

「ランドマーク」というものを用いる。ランドマークとは、ノードの中から(何らかの方法で)選ばれた、4~10個程度のノードの部分集合である。

アルゴリズムは、事前計算とクエリに分かれる。クエリとは、与えられた始点と終点に対し、最短経路と距離を計算する処理(つまりメインの目的)である。クエリを高速化するために必要な情報を事前計算で計算し、保存しておく。

以下の手順で行う

  1. 事前計算
    1. ランドマークの選定
      • グラフからノードをいくつか選定し、ランドマークとする
    2. ランドマークからの最短距離の計算
      • ランドマークから全ノードへの最短距離を計算し、保存する
  2. クエリ(与えられた始点と終点に対し、距離を計算する)
    • A*アルゴリズムで探索
    • ノード$v$から目的地$t$までの距離の予測値$h(v,t)$は、以下の値を用いる
      • $h'(l,v,t)=dist(l,t)-dist(l,v)$
      • $\displaystyle h(v,t)=\max_{l \in L}(h'(l,v,t))$、ただし負になった場合は0
        • $L$:全ランドマークの集合
        • $l$:ランドマークの任意の1つ
        • $dist(a,b)$:ノードaからbまでの最短距離

この予測値は、後述する三角不等式を利用している。

なぜこの予測値がいいのか

A*アルゴリズムの予測値には、いくつか制約があった。

非負

満たす(0で下限切ってるだけだが)

真の最短距離以下

A*は、予測値が真値以下でないと、最初に目的ノードに到達した経路が最短である保証が無くなってしまう。

ALTの予測値は、真値を超えない。以下にそれを示す。

三角不等式というのがある。三角形の1辺は、残りの2辺の和より絶対短い。

これを経路にも適用する。3点a,b,cがあったら、$dist(a,c) \le dist(a,b)+dist(b,c)$である。

もし$dist(a,b)+dist(b,c)$の方が短いことがあったら、普通にbを経由してcまで行った方が近いわけで、$dist(a,c)$最短じゃねえじゃん、ってなる。

移項して、$dist(b,c) \ge dist(a,c)-dist(a,b)$

$a=$ランドマーク$l$、$b=$探索中ノード$v$、$c=$目的ノード$t$を当てはめると、
$dist(v,t) \ge dist(l,t)-dist(l,v) = h'(l,v,t)$

なので、$h'(l,v,t)$は、真の最短距離$dist(v,t)$より大きくならない。

ALTを利用するときに決めること

ランドマークの個数

少なすぎても多すぎてもよくない。全体のノード数にも依るが、4~9個あたりがよく使われる模様。

少なすぎる場合

予測値は、l、v、tの位置関係がある程度理想的で無いと、あまり有効に機能しない。

一番いいのはlからtへの最短経路上にvがあることで、この場合、予測値は真値と一致する。そうでなくても、ある程度l、v、tが、この順で直線的に並んでくれてた方が近い値になりやすい。

そのようになる範囲を増やすため、ランドマークはある程度の個数があった方がよい。

多すぎる場合

単純にマシン負荷の問題。

  • ランドマークの数だけ最短距離までの情報を保持する=メモリが線形に増加
  • ランドマークの数だけ予測値の計算を行う=計算時間が増加

理論上の計算量がいくら小さくても、負荷が高ければ、計算量が多いが単純なアルゴリズムに負けることもある。

ランドマークの選定

ランダムでもそこそこ機能するが、できるだけ散らばってた方が、より広い範囲の2点間で正しい予測値を算出できる。

  • Farthest
    • 1点目はランダム
    • 2点目以降は、選択済みのランドマーク群から最も遠い点を選択
  • Avoid
    • ランダムにノード$r$を選ぶ
    • $r$を根とする最短経路木$T_r$を構築する
    • ランドマークの1点目はランダムに選ぶ
    • 2点目以降は、以下の処理で決定する
      • 全ノードの“重み”$s(v)$を計算する
        • $T_r$の部分木$T_v$($v$から下の部分)に、既に選択されたランドマークが存在するか調べる
        • 存在すれば、$s(v)=0$
        • 存在しなければ、$s(v)=\sum_{c \in T_v}f(c)$
          • ただし、$f(v)=dist(r,v)-h(r,v)$(現段階でのランドマークから求めた予測値と、真値との差)
          • 自身以下の全てのノードの真値と予測値の差の合計が、そのノードの重みとなる
      • 計算し終えたら、$r$から、常に$s(v)$が最大の子ノードをたどって探索を行う
      • 葉ノードまで探索し終えたら、それが新しいランドマーク
    • 希望するランドマーク数になるまで繰り返す
  • MaxCover
    • Avoidアルゴリズムを用いて、ランドマーク数の予定の2~3倍程度の候補群を抽出する
    • 各ランドマーク、各リンク(v,w)につき、$h(v,w)=dist(v,w)$(予測値と真値が一致する)ようなリンクを調べる
    • できるだけ「どれかのランドマークから正しい距離が出せるリンクが多くなる」ような、ランドマークの組み合わせを得る
      • 組み合わせの総当たりだと非常に計算量が大きくなるので、局所探索的に行う
programming_algorithm/route_search/alt.txt · 最終更新: 2017/10/08 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0