Processing math: 100%
[[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)
      • h(v,t)=maxlL(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)dist(a,b)+dist(b,c)である。

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

移項して、dist(b,c)dist(a,c)dist(a,b)

a=ランドマークlb=探索中ノードvc=目的ノードtを当てはめると、
dist(v,t)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を根とする最短経路木Trを構築する
    • ランドマークの1点目はランダムに選ぶ
    • 2点目以降は、以下の処理で決定する
      • 全ノードの“重み”s(v)を計算する
        • Trの部分木Tvvから下の部分)に、既に選択されたランドマークが存在するか調べる
        • 存在すれば、s(v)=0
        • 存在しなければ、s(v)=cTvf(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