A* (A-Star) アルゴリズム
ダイクストラ法に「ゴールまでの予測」を加えた、賢いアルゴリズムです。ゴールへの近道を推測しながら探索するため、無駄な探索を大幅に削減できます。
評価関数: f(n) = g(n) + h(n)
g(n) (実コスト): スタートからの移動コスト。「実測の関数（'given'）の頭文字」h(n) (推定コスト): 現在地からゴールまでの「予測」距離（'heuristic'）の頭文字- 長所: ヒューリスティックが適切なら、非常に高速に最短経路を発見できる。
- 短所: ヒューリスティックの質が悪いと、逆に非効率になることがある（ステージ⑤）。
ヒューリスティック：マンハッタン距離とは？
このシミュレーターのA*は、推定コスト h(n) の計算にマンハッタン距離を用いています。これは、碁盤の目のようなマップで、斜め移動を禁止した場合の2点間の距離です。
- 計算方法: 2つの点のX座標の差とY座標の差を足し合わせます。
|現在地のX - ゴールのX| + |現在地のY - ゴールのY|
- なぜ有効か: このシミュレーターでは上下左右にしか移動できません。マンハッタン距離は、壁や高コストマスを無視した場合の最短移動ステップ数を正確に示します。これにより、A*はゴールへの最も有望な方向を効率的に予測できます。
- 最短経路の保証: マンハッタン距離は、実際のコスト（壁を迂回するコストなど）を過大評価しないという重要な性質を持っています。このようなヒューリスティックは「許容的(admissible)」と呼ばれ、これを用いることでA*はダイクストラ法のような網羅的な探索をせずとも、最短経路を発見できることが保証されています。