ポイント：賢い探索とは「調べるマスを減らしつつ、最短の経路を見つける」こと。幅優先は必ず最短だが調べすぎ、深さ優先は速いが遠回り、貪欲法は速いが最短の保証なし。A*はゴールまでの推定距離を使って、最短を保証しつつ調べるマスを減らします。カーナビ・ゲームのキャラ・配送計画はほぼA*の仲間です。
4つのアルゴリズム
| アルゴリズム | 探し方 | 長所 | 短所 |
|---|---|---|---|
| 幅優先探索（BFS） | スタートから近い順に全部調べる | 必ず最短 | 調べるマスが多い |
| 深さ優先探索（DFS） | 行けるところまで進み、行き止まりで戻る | メモリが少なくて済む | 最短でないことが多い |
| 貪欲法（Greedy） | ゴールまでの直線距離が近いマスを優先 | 調べるマスが少ない | 壁に阻まれると遠回りに |
| A*（エースター） | 「ここまでの距離＋ゴールまでの推定」が小さい順 | 最短を保証しつつ効率的 | 推定（ヒューリスティック）の設計が要 |
A*が「賢い」理由
A*は各マスに f = g + h という点数を付けます。g はスタートからの実距離、h はゴールまでの推定距離（迷路ならマンハッタン距離）。h が「実際の距離を超えない」推定なら、A*は必ず最短経路を見つけることが証明されています。1968年にスタンフォード研究所のロボット「シェーキー」の経路計画のために開発されました。
現実での使われ方
| 分野 | 使い方 |
|---|---|
| カーナビ・地図アプリ | 道路をグラフとみなし、A*やその改良版（ダイクストラ法＋前処理）で最短ルート |
| ゲームのキャラクター | 敵キャラが壁を避けてプレイヤーに向かう移動はほぼA* |
| 配送・物流 | 倉庫ロボットの走行経路、配送順の決定 |
| ネットワーク | インターネットのパケットの経路選択（ダイクストラ法） |
観察のコツ
「抜け道の多さ」を上げると迷路に複数の経路が生まれ、深さ優先と貪欲法が遠回りする様子がはっきり見えます。抜け道0%（完全迷路）では経路が1本しかないため、どのアルゴリズムも同じ経路にたどり着き、違いは「調べたマスの数」だけになります。
引用・転載について
本ページのシミュレーション結果・数値は、出典を明記いただければブログ・ニュース記事・SNS・授業や社内資料への引用を歓迎します。事前連絡は不要です。
推奨クレジット表記：
出典：シミュラボ「迷路をAIが解く 探索アルゴリズム対決」 https://shimulabo.com/sims/maze-ai/よくある質問
- 迷路はどう作っている？
- 「再帰的バックトラック」という方法で、スタートから壁を掘り進み、行き止まりで戻る操作を繰り返して完全迷路（経路が1本）を作ります。「抜け道の多さ」の分だけ、あとから壁をランダムに壊しています。
- A*が幅優先より調べるマスが少ないのはなぜ？
- 幅優先はゴールの方向を知らないため、全方向に均等に広がります。A*はゴールまでの推定距離で「見込みのない方向」を後回しにできるため、無駄な探索が減ります。
- 貪欲法が遠回りする理由は？
- 「ゴールに近そう」だけで選ぶため、壁の裏側の行き止まりに引き込まれます。戻って別の道を探す間に、経路が長くなります。