A* 探索
ダイクストラ法はゴールまでの最短の道を見つけますが、ゴールから離れる方向も含め、全方向を同時に探します。A* 探索は、ゴールまであとどれくらいかという推定を一つ加えるだけで、探索が一気にゴールへまっすぐ向かうようになります。
考え方
地図で道順を探すとき、目的地から離れる道を、目的地へ向かう道と同じほど念入りには調べません。A* 探索も同じです。各ノードにスコアが付きます。スタートからのその時点での距離 g に、残りの距離の推定 h を足したものです。探索は常にスコアが最も低いノードから続くので、ゴールの方向にあるノードが先に来ます。
手順
スタートの距離を 0 にし、スコア h(start) でキューに入れます。次を繰り返します。スコアが最も低いノードを取り出し、その距離を確定させます。それがゴールなら終了です。記録したノードを逆にたどると経路になります。そうでなければ、確定していない各隣接ノードについて、このノードを通った場合の距離を求めます。それがその時点での距離より短ければ、距離を下げ、そこへの道としてこのノードを記録し、新しい距離に推定を足したスコアを隣接ノードに付けます。スコアが等しいときは、推定の小さいノードを先に取り出すと、たいていゴールに早く着きます。
例
スタートを A、ゴールを D とします。A–B の長さは 2、B–D は 2、A–C は 1、C–D は 5 です。D までの直線による推定は、A から 3、B から 2、C から 3 です。A のスコアは 0 + 3 = 3 から始まります。A を取り出すと、B のスコアは 2 + 2 = 4、C のスコアは 1 + 3 = 4 になります。同点なので、A* は推定の小さい B を取り出し、B は D にスコア 4 + 0 = 4 を与えます。これで D のスコアが最も低く推定も最小なので、D が取り出されます。最短経路は A → B → D で長さは 4、逆方向へ向かう C は一度も確定しません。ダイクストラ法なら、A に最も近いノードである C を先に確定していたはずです。
良い推定
推定はゴールまでの実際の距離より長くなってはいけません。このような推定を許容的といい、これがあれば A* は必ず最短経路を見つけます。直線は許容的です。どんな経路も直線より短くはないからです。さらに、あるノードから次のノードへ推定がエッジの長さより大きく下がることがなければ、推定は無矛盾であり、確定したノードを見直す必要は一切ありません。推定が真の値に近いほど、A* が必要とするノードは少なくなります。推定 0 は許容的ですが役に立ちません。A* がダイクストラ法になるだけです。大きすぎる推定は A* を速くしますが、最短経路を見逃すことがあります。
歴史と用途
スタンフォード研究所のピーター・ハート、ニルス・ニルソン、バートラム・ラファエルは、最初期の移動ロボットの一つであるシェーキーの研究中に、1968 年に A* を発表しました。それ以前の版は A1、A2 と呼ばれ、スターは最適であることを証明した版の印でした。今日の A* は、ビデオゲームでキャラクターに障害物を避けて移動させ、道順やロボットの動きを計画し、15パズルなどのパズルを解きます。15パズルでは、推定は各タイルが本来の位置からどれだけ離れているかを合計します。
試してみよう
アプリを開いて「ステップ」を押してください。エッジの数字はその長さで、ここでは描かれた長さと一致します。破線はゴールまでの直線による推定を示します。グラフの下のキューは、ノードをスコアの低い順に並べます。ゴールが確定すると、ステータス行で A* が確定したノード数と、ダイクストラ法なら必要だったノード数を比べます。大きなグラフで遠い隅にゴールを置くと、差が最も大きくなります。
よくある質問
A* のスターは何を意味しますか?
ハート、ニルソン、ラファエルは最初に、A1 と A2 と呼ぶアルゴリズムを示しました。A*(「A スター」)は、推定が無矛盾なとき、同じ推定を使う同等のアルゴリズムの中で、展開するノードが最も少なく最短経路を見つけることを彼らが証明した版です。
A* の時間計算量は?
最悪の場合、つまり推定が役に立たないとき、A* はダイクストラ法と同じ処理を行います。二分ヒープを使うと O((V + E) log V) です。良い推定があれば、確定するのはノードのごく一部だけなので、実際には高速です。
A* に良いヒューリスティックとは?
計算が速く、実際の距離を過大評価せず、できるだけ実際の距離に近いことです。上下左右にしか動けないグリッドではマンハッタン距離、地図では直線距離がよく使われます。
ヒューリスティックが過大評価するとどうなりますか?
A* が最短ではない経路を返すことがあります。より良い経路を調べる前に終了してしまう場合があるからです。わざとそうするプログラムもあり(重み付き A*)、経路の質を少し犠牲にして大幅に速くします。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
A* 探索を試す