アルゴリズム・データ構造図鑑 · 基礎から応用へ

A*探索:既知の費用と残りの見積もりを足す

g+hの優先度で経路を探し、許容性・整合性・再オープンの条件と最適性の関係を整理する。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 現在までの費用と残りを分ける
  2. 二つの候補を比べる
  3. 許容性と整合性の役割
  4. 探索量の改善は入力次第
  5. この記事をロゲイアに質問する理解を確かめる

現在までの費用と残りを分ける

A*は、始点から頂点vまでに見つけた費用g(v)と、vからゴールまでの見積もりh(v)を足したf(v)=g(v)+h(v)を優先度に使います。辺の重みを非負とし、ここでは有限グラフの最短路を考えます。hを全て0にするとDijkstra法に対応します。見積もりは実際に通った費用とは別なので、gの代わりに使ってはいけません。ゴールが初めて隣接頂点として現れた時点で終了する方法も、優先度付きキューから適切に取り出す終了条件とは異なります。

二つの候補を比べる

始点SからAへ2、Bへ4、AからGへ5、BからGへ1とします。h(A)=5、h(B)=1ならAのfは7、Bのfは5となり、B側を優先して費用5のゴールへ進みます。見積もりが0ならgだけでAを先に展開することがありますが、最終的な最短距離は変わりません。一方、h(B)を過大な100へ変えると、より安いB経由を後回しにして費用7を答えてしまうおそれがあります。探索を速めるための情報が、保証を壊す情報にもなり得る例です。

許容性と整合性の役割

許容的なヒューリスティックは真の残り費用を過大評価しません。整合性は、各辺u→vでh(u)≤w(u,v)+h(v)が成り立ち、ゴールでh=0となる条件です。整合性があれば取り出した頂点を確定する標準的なグラフ探索を説明しやすくなります。許容的でも整合的でない見積もりでは、よりよいgが後から見つかった頂点を再び開く必要がある場合があります。閉じた頂点を二度と処理しない実装に、許容性だけを根拠として最適性を主張しないようにします。

探索量の改善は入力次第

ヒューリスティックが有用なら展開頂点数を減らせますが、最悪でも常にDijkstra法より速いという保証ではありません。hを計算する費用、キュー内の古い候補、到達した頂点の記録に必要なメモリも数えます。例えば四近傍の単位費用格子でマンハッタン距離は障害物を無視した下界ですが、斜め移動や異なる費用を追加すると条件を見直します。状態空間が無限の場合の完全性には追加条件が必要で、有限グラフについての説明を無条件に拡張できません。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 11

学習コースから次を選ぶ