A*
- Dijkstraは、始点からの距離が近い方から探索する
- 目的地と真逆の方向でも気にせず探索するため、探索数が増える
- A*は、「全体的な距離が近そう」なノードを優先的に探索する
- Dijkstraより速く到達できそう！
- 「近そう」かどうかは、それっぽい評価関数を与えて、予測する
- …というと適当っぽく見えるが、条件が整えば理論的に最短距離が保証される
定義
- $s,t$:出発ノード、目的ノード
- $g(v)$:sからvまでの暫定最短距離
- $g^*(v)$:sからvまでの確定最短距離
- $h(v)$:vからtまでの予測最短距離
- $h^*(v)$:vからtまでの真の最短距離
- $f(v)=g(v)+h(v)$:sからtまでの、vを経由したときの全体の予測最短距離(優先キューで比較する値)
評価関数の制約
- 予測値$h(v)$は、常に非負
- 予測値$h(v)$は、実際の値$h^*(v)$より常に小さい
- さもなくば、最短が保証されない
- この条件を満たす性質を「許容的」(Admissible)という
- 全体の予測値$f(v)$は、任意の経路上において単調増加である
- さもなくば、探索に時間がかかる場合がある
- この条件を満たす性質を「無矛盾」(consistent)という
- まぁ…時間がかかるだけで正確な値は出るので、絶対満たさなければいけないわけでは無い。問題によっては無矛盾な予測値を得るのが難しいこともある
許容的
$\forall v\in V, \ \ 0 \le h(v) \le h^*(v)$
許容的で無い場合
どういうことが起こるかというと、
1 1
s ----- v(99) ----- t
`----- u( 1) -----'
2 2
(※リンクの傍に書かれた数字がリンクの距離、ノードの横の括弧内の数字が予測値)
上の例では、最短経路は明らかに上のs-v-tの道。だが、vの予測値$h(v)$が“許容的”でない99という値となっている。
どのように探索が進むか、見ていく。
○sから探索ノードを広げる。隣接するノードはv,u。各f(n)を計算する。
f(u) = g(u) + h(u) = 2 + 1 = 3
f(v) = g(v) + h(v) = 1 + 99 = 100
優先キューにノードを積む。ノードは(f(n), n)で表記する。
[(3, u), (100, v)]
○f(n)の小さいuが先に調べられ、uに隣接するtが優先キューに積まれる
f(t) = g(t) + h(t) = 4 + 0 = 4
[(4, t), (100, v)]
○tが先に調べられる。これが目的ノードなので探索終了
○結果、最短経路はs-u-t、最短距離は4ということになってしまう
「あと1個調べたらvが出てきて正しい距離が求まるんだから、もうちょっと先まで調べたらいいじゃん」と思うかも知れないが、例が単純だからあと1個で済むのであって、実際のネットワークなら“もうちょっと先”がどこまでかわからない。結局、最適解であることを保証するには、優先キューが空になるまで探索し続けないといけないため、高速化も何も無い。
ただし、非許容的な予測値が絶対ダメかというと、「最適解が出なくてもそこそこ近いのが出ればいい」「許容的な予測値は計算に時間がかかるが、非許容的なら高速に行える」場合、速度や精度との兼ね合いで選択されることもある。
無矛盾
$\forall v\in V, \ \ \forall w\in children(v), \ \ h(v) \le len(v,w) + h(w)$
- children(v): vから伸びるリンクのもう一方の端点の集合
- len(v, w): リンク(v,w)の長さ
|<-------h(v)---->| こっちより
...-- v --- w ---...--- t
|lenvw|<---h(w)-->| こっちの方が大きい(いかなる箇所においても)
評価関数が“無矛盾”ならば、“許容的”である。
無矛盾である場合、ノード$v$が優先キューからpopされた時点で、$g(v)=g^*(v)$であることが保証される
逆に無矛盾で無い場合、後からより短く$v$に到達できる経路が見つかるかも知れないということである。そうなったら再計算が必要になり、探索に時間がかかってしまう。
無矛盾で無い場合
s -------5----------- v(1) --6-- t |`---3------ w(4) -1-' 1- x(7) -1-'
（リンク上の数字はリンクの距離、ノードの横の括弧内の数字はそのノードの予測値）
このネットワークは、“許容的”だが、“無矛盾”では無い。例えばxを見ると、$h(x) \gt len(x,w) + h(w)$となっている。
無矛盾でないネットワークでは、既に探索済みのノードが何度も再計算される可能性がある。順を追ってみる。
○sから隣接するノードを広げた後の優先キューの状態。(f(n), g(n), n) [(6, 5, v), (7, 3, w), (8, 1, x)] ○(6,5,v)が取り出される。s-vの暫定最短距離は5。 vに隣接するノードtが、f(t) = g(t)+h(t) = (5+6)+0 = 11 で積まれる。 [(7, 3, w), (8, 1, x), (11, 11, t)] ○(7,3,w)が取り出される。s-wの暫定最短距離は3。 wを経由することで、s-vの暫定最短距離が4に更新されたため、vが再度積まれる [(5, 4, v), (8, 1, x), (11, 11, t)] ○vが取り出される。優先キュー上のtの値が11から10に更新される [(8, 1, x), (10, 10, t)] ○xが取り出される。xを経由することで、s-wの暫定最短距離が2に更新されたため、wが再度積まれる [(6, 2, w), (10, 10, t)] ○wが取り出される。x,wを経由することで、s-vの暫定最短距離が3に更新されたため、vが再度積まれる [(4, 3, v), (10, 10, t)] ○vが取り出され、tの値が10から9に更新される [(9, 9, t)] ○tが取り出されたため、探索終了。最短距離は9。
vは3回、wは2回取り出され、再計算されている。この例は特に意地悪ではあるが、無矛盾でない評価関数はこのような更新が発生するため計算時間がかかることがある。
実装の面での留意点
同一コストの優先順位
全体の予測値$f(n)$が同じ複数のノードが優先キューにある場合、取りだし順はどうするか。
- 予測値$h(n)$が小さい方を優先する
- 経験上、探索が速く終了するらしい
- 予測値も同じ場合、Random Depthがいいよって言われてる。まぁ稀だし、普通にランダムでいいかも。
[AAAI-16] Tiebreaking Strategies for A* Search: How to Explore the Final Frontier
コストが小数になる時の打ち切り誤差
（別にA*に限ったことではないが）小数の比較には注意という話。
精度の良い評価関数を使っている場合など、$f(n)$の値が多くのノードで近い値になることがある。
その場合、打ち切り誤差の蓄積のために、真の最短経路より少しだけ長い2番目以降の経路が、先に探索されてしまうことがある。
コストを10^x倍して整数値として扱う、許容誤差$\epsilon$を定義して差がこの値以下の2数は同値として扱うなどで対処する。
優先キューの更新コスト
- A*では、ノードの暫定最短距離が更新されることがある（無矛盾で無い評価関数を用いる場合）
- 更新された前のノードがまだ優先キューに残っている場合、値の更新が必要になる
- 優先キュー上の値の更新は、時間がかかる
- 優先キュー上で、更新されたノードの位置を見つけるコスト: O(Np)
- 更新されたノードを正しい位置に再配置するコスト: O(logNp)
更新手順1
- 更新の必要性の確認のため、ノード毎の現在の暫定最短距離は記録しておく
- popしてノードへの距離が求まったとき、暫定最短距離と比較する
- 新しい距離の方が長い、または同じ場合は、何もしない。次のノードをpop
- 新しい距離の方が短い場合
- 暫定最短距離を更新
- 優先キュー上でのノードの位置を探索する
- 存在すれば、値を更新し、再配置する
- 存在しなければ、優先キューにpush
- ○持つ情報は暫定最短距離だけで良い
- ×更新があった場合は毎回優先キューの探索コストO(Np)が発生する
- あまり更新が多くないと予想される場合に
更新手順2
- 更新の必要性の確認のため、ノード毎の現在の暫定最短距離を記録しておく
- また、ノードが優先キュー上にあるかのフラグも記録しておく（push時にON, pop時にOFF）
- popしてノードへの距離が求まったとき、暫定最短距離と比較する
- 新しい距離の方が長い、または同じ場合は、何もしない。次のノードをpop
- 新しい距離の方が短い場合
- 暫定最短距離を更新
- ノードが優先キュー上にあるかのフラグを確認
- 存在すれば、優先キュー上でのノードの位置を探索、値を更新し、再配置する
- 存在しなければ、優先キューにpush
- ×ノードのpush, pop時に毎回O(1)のコストがかかる
- ○無駄な優先キューの探索は減らせる
- 更新が多くなると予想される場合に
更新手順3
- 各ノードはインスタンス（値の書き換えが可能なデータ構造）として管理する
- ノードには、自身が有効か無効かのフラグを持たせる
- 優先キューからのpop時、無効なノードは飛ばす
- 更新の必要性の確認のため、ノード毎の現在の暫定最短距離と、そのノードインスタンスを記録しておく
- popしてノードへの距離が求まったとき、暫定最短距離と比較する
- 新しい距離の方が長い、または同じ場合は、何もしない。次のノードをpop
- 新しい距離の方が短い場合
- 古いノードインスタンスを無効化
- 暫定最短距離とノードインスタンスを更新
- 新しいノードインスタンスをpush
- 同じノードを示すインスタンスが優先キューに複数存在することになるが、最初にpopされるのがその時点での暫定最短距離であり、残りは無効になっている
- ×優先キューが肥大化しやすくなり、メモリを圧迫する
- といっても更新の割合は通常そこまで大きくならないので、無視できる程度
- ○優先キューの探索や再配置をしなくて済む
- リスト探索や数値比較の遅いスクリプト言語などでは、速くなる可能性がある
- Algorithms with Python / ヒューリスティック探索(ページ中盤「A*アルゴリズム」「プログラムの作成」)
計算コスト
- いくら予測値の精度が高い優秀な評価関数でも、その計算に時間がかかるようなら、単純なDijkstraの方が速い場合もある
- もちろんDijkstraは、グラフの規模が大きくなるにつれて性能が落ちるため、どこかでは逆転するはずだが、使いもしないような巨大グラフでないと逆転が見られないようなら、Dijkstraで十分ということになる
- 解きたい問題の規模を考えて、精度と計算コストのバランスのとれた評価関数を選択する
実装例
Python3
from heapq import heappop, heappush
def get_estimate_func(target):
tx, ty = xy[target]
# 適当な評価関数
# ここでは例えば直線距離の2乗（xyに各ノードの座標が入っているとする）
def estimate(v):
vx, vy = xy[v]
return (tx - vx) ** 2 + (ty - vy) ** 2
return estimate
def a_star(s, t):
get_estimate = get_estimate_func(t)
# [予測値, 実コスト, ノードID, 無効フラグ]
st = [get_estimate(s), 0, s, False]
queue = [st]
available = [None] * n
available[s] = st
while queue:
node = heappop(queue)
estimated, temp_cost, node_id, closed = node
if closed:
continue
if node_id == t:
return temp_cost
available[node_id] = node
node[3] = True # close
for next_node_id, next_cost in links[node_id]:
new_cost = temp_cost + next_cost
preceding = available[next_node_id]
if preceding is not None:
if new_cost >= preceding[1]:
# 現在のノードの方がコストが高いので、何もせず飛ばす
continue
# 先客の方がコストが高いので無効化し、現在のノードを新しく追加する
preceding[3] = True #close
new_estimate = new_cost + get_estimate(next_node_id)
new_node = [new_estimate, new_cost, next_node_id, False]
available[next_node_id] = new_node
heappush(queue, new_node)
# 到達できなかった
return float('inf')
