目次

ALT

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

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

概要

「ランドマーク」というものを用いる。ランドマークとは、ノードの中から（何らかの方法で）選ばれた、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点間で正しい予測値を算出できる。