経路探索アルゴリズムの「ダイクストラ法」と「A*」をビジュアライズしてみた
A* ではゴールへの経路が判明した段階で処理は終了です。 A* はダイクストラ法に比べてゴールに到達するまでに調べるマス目が少ないのが印象的です。 ダイクストラ法と同じように水で例えると、A* では水が少し意思を持っていて、なるべくゴールに近いほうに流れようとするようなイメージです。ここがまさに A* のキモです。ゴールへの近さを加味して、探索するノードの数をなるべく減らそうとします。 A* では、スコアとして f* = g* + h* を用います。各ノードの f* を調べて、f* の値が小さいノードから先に探索していきます。g* はスタート地点からの距離であり、ダイクストラ法で用いるスコアと同じです。h* がゴールへの距離なのですが、実際の最短距離は途中の段階では分からないので、ゴールへの直線距離やマンハッタン距離を利用して計算します。 この、h* の部分がゴールへの近さを加味する部分で
経路探索アルゴリズムの「ダイクストラ法」と「A*」をビジュアライズしてみた - てっく煮ブログ
as詳解 ActionScript 3.0アニメーション ―衝突判定・AI・3DからピクセルシェーダまでFlash上級テクニック を読んでいて、経路探索のアルゴリズムで A* が取り上げられていました。A* については、いろいろ検索して調べたりもしたのですが、やっぱり本に書いてあると理解しやすいですね。せっかくなので自分流に実装してビジュアライズしてみました。ダイクストラ法まずは A* の特別なケースでもあるダイクストラ法から見ていきます。クリックすると探索のシミュレーションが開始します。スタート地点(S)からゴール(G)への探索が始まります。色がついたところが「最短経路が決定した場所」です。スタート地点から少しずつ探索が完了していきます。半分ぐらい完了しました。まだまだ進みます。最後まで終わりました。最短経路を黒色矢印で表示しています。ダイクストラ法は、スタート地点から近いノード(=マス
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://spheresofa.net/blog/?p=1044
