- 現在
- キュー内
- 確定
- 経路
- 直線による推定
A* 探索
A* 探索は、ダイクストラ法と同じくスタートからゴールまでの最短経路を見つけますが、ゴールのおおよその位置を知っています。各ノードに残りの距離の推定(ゴールまでの直線)が付き、探索は常に、その時点での距離+推定が最も小さいノードから続きます。ノードをクリックしてスタートにし、ゴールを選んでステップを進めると、探索がゴールへ向かい、グラフの片隅がまるごと手つかずで残る様子がわかります。 「再生」で探索を見るか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。ノードをクリックするとスタートになります。クリックを「ゴール」に切り替えて別のノードをクリックすると、そこがゴールになります。各エッジの数字はその長さ、各ノードの数字はその時点での距離、破線は残りの距離の直線による推定です。グラフの下の列がキューで、スコアの低い順に並び、各スコア(その時点での距離+推定)が表示されます。「新しいグラフ」で別のグラフを作ります。ノード数とエッジ数を選べます。ボードを選択した状態では、矢印キーでステップ、スペースキーで再生と一時停止、Home と End で最初と最後に移動します。
使い方
- ノードをクリックしてスタートにします。クリックを「ゴール」に切り替えて別のノードをクリックし、ゴールにします。
- 「再生」を押すか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると探索の好きな位置に移動できます。
- キューのスコアと、破線で示す直線による推定に注目しましょう。最後に、A* が必要としたノード数をダイクストラ法と比べます。
A* 探索の仕組み
スタートの距離を 0 にしてキューに入れます。キュー内の各ノードにはスコアがあります。その時点での距離に、残りの距離の推定を足したものです。次を繰り返します。スコアが最も低いノードを取り出し、その距離を確定させます。それがゴールなら終了です。そうでなければ、確定していない各隣接ノードについて、エッジの長さをノードの距離に足します。それが隣接ノードのその時点での距離より短ければ、距離を下げ、そこへの道としてノードを記録し、新しいスコアで隣接ノードをキューに入れます。
推定が長すぎてはいけない理由
推定がゴールを実際より遠いと言わない限り、A* は最短経路を見つけます。このような推定を許容的といいます。直線はその一つです。2地点を結ぶどんな道も直線より短くはないからです。長すぎる推定は A* に最良の経路を見逃させることがあります。どこでも推定が 0 なら A* はダイクストラ法になり、安全ですが全方向を調べます。推定が良いほど、A* が必要とするノードは少なくなります。このアプリでは各エッジの長さが描かれた長さ(切り上げ)と同じなので、直線は安全な推定です。
よくある質問
A* 探索とは何ですか?
スタートからゴールまでの最短経路を見つける経路探索アルゴリズムです。ダイクストラ法と同じように動きますが、キューをその時点での距離+残りの距離の推定の順に並べるので、全方向に広がらずゴールへ向かいます。
許容的ヒューリスティックとは何ですか?
ゴールまでの距離の推定のうち、実際の最短距離より長くならないものです。許容的な推定なら、A* は必ず最短経路を見つけます。地図上の直線距離が代表的な例です。
A* はダイクストラ法より速いですか?
1つのゴールへの道が必要で、良い推定があれば、たいていは速いです。ゴールから離れたノードはスコアが高くなるので、A* が確定するノードは少なくて済みます。推定が 0 なら、ダイクストラ法とまったく同じ動きをします。すべてのノードへの距離が必要なときは、ダイクストラ法のほうが適しています。
A* はどこで使われていますか?
ビデオゲームでキャラクターに障害物を避けて移動させるため、経路案内、ロボットの動作計画、そして15パズルなどのパズルソルバーで使われます。15パズルでは、推定はタイルが本来の位置からどれだけ離れているかを数えます。
グラフはどこかに送信されますか?
いいえ。グラフの作成と探索はブラウザ内で行われ、最後の設定はこのブラウザのローカルストレージに保存されます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
エディターへ