🗺️ A* パスファインディング

貪欲最良優先探索はg = 0としてhのみでノードを順位付けし、常にゴールに最も近く見えるノードへ突き進みます。開けた環境では非常に高速ですが、実際の経路コストを無視するため、コストの高い地形や障害物を回り込むことでより長い経路に誘導されることがあります。最悪の場合、最適解より著しく悪い経路を見つけてしまいます。

移動が4方向(上下左右)に制限されている場合はマンハッタン距離を使用してください。これは最小移動回数を正確に数えます。斜め移動が許可され、その移動コストが√2に等しい場合はユークリッド距離が適しています。チェビシェフ距離(|Δx|と|Δy|の大きい方)は、多くの戦略ゲームでよくあるように、全8方向のコストが同じ場合に適した選択です。

重み付きセルは、泥地・浅瀬・悪路など通過しにくい地形を表します。このシミュレーションでは重み付きセルへの進入コストが1ではなく5になるため、A*はしばしば複数の重み付きセルを通り抜けるより、その周囲を迂回する経路を選びます。ダイクストラとA*はどちらも重みを正しく扱いますが、貪欲最良優先探索はコストを無視するため、コストの高い地形をそのまま通り抜けることがあります。

最悪の場合、A*の時間・空間計算量はO(b^d)です。ここでbは分岐係数、dは最適解の深さです。三角不等式を満たす一貫性のあるヒューリスティックを使う場合、各ノードは最大1回しか展開されないため、V個の頂点を持つ有限グラフではO(V log V)となり、これは二分ヒープを使うダイクストラ法と同じ漸近的な計算量です。

迷路生成器は、グリッドを通る通路を削り出すランダム化アルゴリズムを使って完全な迷路を作成し、任意の2つのセル間にちょうど1つの経路しか存在しないことを保証します。迷路は探索アルゴリズムにとって特に厳しい条件です。狭い通路によってA*のヒューリスティックの優位性が失われ、有効な経路が1つしかないため、すべてのアルゴリズムがほぼ同じ数のノードを探索する必要があるからです。

緑はスタートノード、赤はゴールを示します。青色のセルは現在のフロンティア(オープンセット)を形成し、濃い青は訪問済み(クローズド)のノードを示し、黄色は展開中のノードを強調表示します。重み付きセルは茶色で表示されます。経路が見つかると、スタートからゴールまでライムグリーンでトレースされ、統計パネルで正確なコストを確認できます。

はい — A*は、辺のコストが非負であり、許容的なヒューリスティックを与えられるあらゆるグラフで機能します。実世界の応用には、3Dロボットアームの動作計画(コンフィギュレーション空間グラフ)、ネットワークルーティング(遅延をコストとする)、自然言語解析(ビタビ的な格子)などがあります。ここでのグリッドは、この一般的なアルゴリズムの最も視覚的にわかりやすい表現に過ぎません。

展開されたノード数は、アルゴリズムがフロンティアからノードを取り出し、その隣接ノードを処理した回数を数えたもので、A*の効率性を測る主要な指標です。この数値が低いほど、ヒューリスティックが探索をうまく導いていることを意味します。30×30のグリッド(900セル)では、優れたヒューリスティックを使うと100ノード未満の展開で最適経路を見つけられることが多いのに対し、ダイクストラは到達可能なすべてのセルを展開することがあります。