A* 経路探索

A* は f(n) = g(n) + h(n) で探索候補を並べる。g は既に支払った経路コスト、h は残りのコストの推定値だ。本レッスンのように閉じたノードを再び開かない実装では、一貫性のあるヒューリスティックによって最適経路を保証でき、通常は Dijkstra 法より少ないマスを展開する。

g が実際のコストを記録し、h が目標の方向を示す。h だけを見る貪欲探索は高価な経路を選びうる。h = 0 とすれば A* は Dijkstra 法になる。地図、ゲーム、ロボットの格子、経路計画では、残距離の下界を安価に求められることが多い。

ヒューリスティックを過大にしたプリセットは h = 4 × マンハッタン距離 を使う。残りのコストを過大評価し、安い迂回路を調べる前に目標を取り出すため、最適でない経路を返す。保証にはヒューリスティックの条件が必要だ。

A* 経路探索の仕組み

三つの状態を保持する。g[cell] は始点からそのマスまでに見つかった最小コスト、came_from[cell] はそのコストを与えた親マス、オープン集合は f = g + h 順の優先度付きキューになる。

最小 f の項目を取り出す。既に閉じたマスなら古い項目として捨てる。目標なら経路を復元して終了する。それ以外は閉じ、通行可能な隣接マスを調べる。tentative_g = g[cur] + move_cost が隣接マスの古い g より小さければ、親、g、f を更新し、新しい項目をオープン集合へ入れる。

本実装は閉じたマスを再び開かないため、一貫性が必要になる。全ての辺で h(u) <= cost(u, v) + h(v)、かつ h(goal) = 0 を満たすことだ。一貫性は、真の残コストを過大評価しない許容性を含意する。許容的でも一貫性がなければ、閉じたノードを開き直す必要があり、現在の実装の保証をそのまま適用できない。

一貫性があれば、目標を初めて取り出したときのコストは最適となる。目標の f はオープン集合で最小で、未完了経路の下界から、より安い目標コストは現れない。本レッスンの通常の格子ではマンハッタン距離がこの条件を満たす。

A* 経路探索のステップ

既定の迷路は 4 行 7 列。始点は r1c0、目標は r1c6。列 3 の行 0、1、2 は壁で、最下段の隙間から渡り、上へ戻る必要がある。

以下は最終経路に沿った説明で、実際には他の候補も展開する。通行可能な 25 マスのうち A* は 15 マス、同じ迷路の Dijkstra 法は 23 マスを閉じる。

1. g[r1c0] = 0 で開始する。マンハッタン距離は 6 なので f = 0 + 6 = 6。
2. r1c0 を取り出して閉じる。右の r1c1 は g=1, h=5, f=6 になる。上下のマスも入るが、目標の行から離れるため f が大きい。
3. r1c1、r1c2 の順に取り出す。直線上では f=6 のままだが、r1c2 の右は壁なので列 3 に入れない。
4. r2c2、r3c2 と下り、r3c3 の隙間を通って r3c4 へ進む。緩和が成功するたびに親ポインターと g/h/f を記録する。
5. r3c4 から r2c4、r1c4、r1c5、r1c6 と進む。始点の後に十マスへ入り、コストは 10 となる。
6. 目標を取り出す時点では、それより小さい f のオープン項目はない。一貫したマンハッタン距離により停止できる。復元経路は r1c0 -> r1c1 -> r1c2 -> r2c2 -> r3c2 -> r3c3 -> r3c4 -> r2c4 -> r1c4 -> r1c5 -> r1c6。

過大なヒューリスティックのプリセットでは、上段の直進経路をコスト 13 で返すが、下段の迂回路は 6 で済む。拡大した推定値が、目標を早く信頼させてしまう。最終比較の赤い数値は停止前に実際に記録したコスト、緑の opt は参照用の最適経路に沿った真の累積コストを示す。

A* と Dijkstra 法の探索量

既定迷路では両方とも経路コスト 10 だが、閉じるマスは A* が 15/25、Dijkstra 法が 23/25。ヒューリスティックは優先順位を変え、最悪時の漸近計算量は改善しない。マンハッタン距離が目標へ引き寄せる一方、g は壁を迂回する実コストを記録する。Dijkstra 法は支払済みコストだけで外側へ探索を広げる。

時間計算量と空間計算量

V はマスまたは頂点の数、E は辺の数。四近傍の格子では E は高々約 4V なので、O(V log V) とも表せる。挿入、最小値の取り出し、辺の緩和は Dijkstra 法と共通だ。遅延削除のヒープには古い項目も残るため、空間には E を含める。

安価で一貫した推定があれば本実装を使い、適切な推定がなければ Dijkstra 法を使える。ノードを開き直す方式に変える場合は、対応する条件と探索コストを改めて検討する。

境界ケース

• h=0 は有効で Dijkstra 法と同じ。最適性を保つが、目標方向の手掛かりはなくなる。
• 目標を取り出す前にオープン集合が空なら経路はない。全プリセットには経路があるが、コードは経路なしで (None, INF) を返す。
• f が同じなら小さい h、次に行、列で比較し、再生順を固定する。
• 重み付き地形の実移動コストは g に加える。ヒューリスティックは条件を満たす残コストの推定を与える。
• h が過大評価すると、目標の取り出しは最適性の証明にならない。過大設定のプリセットが反例になる。
• 迂回プリセットでは、あるマスがコスト 4 で登録され、後で 2 に改善される。古い項目は後で取り出されてスキップされる。これが遅延削除だ。

よくある間違い

1. h だけで並べ、貪欲最良優先探索にしてしまう。A* は g + h を比べるので、目標に近くても支払済みコストが高ければ後になる。
2. ヒューリスティックの条件を省く。再び開かない現在のコードには一貫性が必要で、マンハッタン距離を膨らませると証明が崩れる。
3. キューへ入れる時点で閉じる。取り出す前に安い経路が見つかる可能性があるため、閉じるのは取り出したとき。
4. 古いヒープ項目を忘れる。通常の遅延更新では新項目を追加し、旧項目は後で取り出したときに捨てる。
5. 画面上の距離をコストと考える。アルゴリズムが足すのは格子やグラフの移動コストで、描画位置はその状態の表現にすぎない。

表示上の簡略化

オープン集合は優先規則を読み取れるよう、完全に整列した帯として描く。実際の二分ヒープが保証するのは次に最小項目を取り出せることだけで、全体は整列されていない。移動は四方向、入力は固定プリセット、コストは小さな整数に限る。対角移動、動的障害物、経路の平滑化、ゲーム専用の同点処理は扱わない。