A*探索
方向感覚を持ったダイクストラ法です。各場所のコストに残りコストの見積もりを足すので、ゴールに最も近そうな場所から試します。
- 時間 O((V + E) log V)
- メモリ O(V)
- 優先度付きキューを使う
用語の意味
- コスト:移動にかかる値段。迷路では地面が1、泥が3、水が9。グラフでは辺に書かれた数です。
- 優先度付きキュー:先に来た順ではなく、最も安いものから出ていく待ち行列。
- 見積もり(h):残りコストの予想。A*が正確でいられるのは、見積もりが決して高すぎない場合だけです。
- 辺の緩和:今の場所を通ると隣のコストが下がるかを確かめ、下がるならそれを採用すること。
0 / 205 ステップ
- キュー内
- 現在
- 完了
- 最も安い道
- 地面 · 1
- 泥 · 3
- 水 · 9
- 壁
発見: A1 からスタート、コスト0、ゴールまでの見積もり 26。キューにはこれだけです。
スペースキー: 再生・一時停止。左右の矢印キー: ステップ移動。Home キーと End キー: ジャンプ。
試してみましょう: 「開けた野原」を選び、ダイクストラ法とA*を切り替えてみてください。どちらも同じコストの道を見つけますが、A*がキューから取り出すマスはずっと少なくなります。
仕組み
A*はダイクストラ法と同じように動きますが、キューを f = これまでのコスト + h の順に並べます。h は残りコストの見積もりです。迷路では壁や泥を無視したMまでの手数、グラフでは直線距離を10で割った値です。h が決して過大に見積もらない限り、ゴールを取り出した時点で A* が持つ道は、ダイクストラ法と同じく最も安い道です。見積もりが良いほど、調べる場所は少なくて済みます。
向いている場面
ゴールが一つで、その遠さを見積もれるときに使います。ゲームの経路探索、ロボット、地図上のルート検索などです。h = 0 ならダイクストラ法そのものです。過大に見積もりうる見積もりを使うと A* は速くなりますが、最も安い道を逃すことがあります。