$\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)$
|<-------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)$が同じ複数のノードが優先キューにある場合、取りだし順はどうするか。
[AAAI-16] Tiebreaking Strategies for A* Search: How to Explore the Final Frontier
（別にA*に限ったことではないが）小数の比較には注意という話。
精度の良い評価関数を使っている場合など、$f(n)$の値が多くのノードで近い値になることがある。
その場合、打ち切り誤差の蓄積のために、真の最短経路より少しだけ長い2番目以降の経路が、先に探索されてしまうことがある。
コストを10^x倍して整数値として扱う、許容誤差$\epsilon$を定義して差がこの値以下の2数は同値として扱うなどで対処する。
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')