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)$より大きくならない。

少なすぎても多すぎてもよくない。全体のノード数にも依るが、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)$（予測値と真値が一致する）ようなリンクを調べる
  • できるだけ「どれかのランドマークから正しい距離が出せるリンクが多くなる」ような、ランドマークの組み合わせを得る
    • 組み合わせの総当たりだと非常に計算量が大きくなるので、局所探索的に行う