A*（エースター）アルゴリズムとは：ヒューリスティックで解く最短経路探索入門

A*（エースター）アルゴリズム入門：ヒューリスティックで効率的に最短経路を探索する仕組みと実装ポイントをやさしく解説。

著者: Leandro Alegsa

A*は、コンピュータが2つの場所の間を高速で移動する方法を見つけ出すために使用できる一連の手順（アルゴリズム）です。与えられた地図（ノードと辺の集合）で、ある地点から別の地点へ行くのに必要なコスト（距離や時間）が分かっている場合、A*は最短経路を効率よく見つけ出します。これは、探索のたびに「賢い推測（ヒューリスティック）」を使う点で、単純な幅優先探索やコストにのみ基づくダイクストラのアルゴリズム（ダイクストラのアルゴリズムに）と似ていますが、不要なノードの探索を減らせるため多くの場合さらに速く動作します。単に1対1の最短経路を求めるには非常に有用ですが、同じ地図から全点対全点の経路をまとめて求めたい場合はフロイド・ワーシャルのようなアルゴリズムの方が向いています。また、A*は一回の旅行で多数の都市を順に訪れるような最適巡回経路（巡回セールスマン問題）を直接解くものではありません。

基本概念

A*は各ノードnについて次の値を計算して探索を進めます：

  • g(n)：スタートからノードnまでに確定している最小コスト（実際にかかったコスト）
  • h(n)：ノードnからゴールまでの推定コスト（ヒューリスティック、推測値）
  • f(n) = g(n) + h(n)：ノードnを経由したときの総費用の見積もり（これを評価値としてノードを選ぶ）

ヒューリスティックh(n)が許容的（admissible）（つまり実際の最小コストを過小評価しない）であれば、A*は最短経路を保証します。さらに、hが一貫性（consistent）（三角不等式を満たす）であれば、実装は単純になり、ノードが一度確定（クローズドセットに移る）すると、その最短コストは変わりません。

アルゴリズムの流れ（概要）

  • 開始ノードをオープン集合に入れ、g(start)=0、f=startのh値に設定する。
  • オープン集合が空でない限り繰り返す：
    • f値が最小のノードcurrentをオープンから取り出す（通常プライオリティキューを使う）。
    • currentがゴールなら経路を復元して終了。
    • currentをクローズド集合に移し、隣接ノード（近傍）をすべて調べる。
    • 各隣接ノードについて、current経由のg値を計算し、既知のgより小さければ更新してparentをcurrentに設定、オープン集合に入れる／更新する。

ヒューリスティックの例（格子地図）

  • マンハッタン距離：上下左右のみ移動可能な格子のとき。h = |dx| + |dy|。
  • ユークリッド距離：斜め移動も可能で距離が直線に比例する場合。h = sqrt(dx^2 + dy^2)。
  • オクタイル距離：斜め移動に別コストがある場合に使う近似。

ヒューリスティックは実際のコストを超えないように設計する（許容的）ことが重要です。過小評価であれば最適性を保て、過大評価だと高速化はできるが最適解を失う可能性があります（場合によっては許容された誤差を入れて速度を優先する手法もある）。

性能と制約

  • 最良の場合、ヒューリスティックが正確にゴールまでの残りコストを示せると、探索ノードは非常に少なく済みます。
  • 最悪の場合（ヒューリスティックが無意味な場合）、A*はダイクストラと同様に動作し、時間・メモリが大きくなる（指数的になることがある）。
  • メモリ消費が大きくなる点に注意。すべての展開ノードを保持するので、大規模問題ではメモリ不足になることがある。メモリ節約のためにIDA*（反復深化A*）やビームサーチ、近似アルゴリズムを使う選択肢がある。
  • 複数の目的地を一度に最適に巡回する問題（TSP）はA*単体では解けない。TSPなどには別の手法やA*を組み合わせた状態空間の拡張が必要。

実装上のヒント

  • オープン集合は優先度付きキュー（ヒープ）で管理し、f値でソートする。fが同値のときのタイブレーク（例えばgが大きい方を優先する）は、探索の効率や経路の品質に影響することがある。
  • ヒューリスティックが一貫していれば、ノードをクローズした後に再度更新する必要がなくなり、実装が簡単かつ高速になる。
  • 動的グラフ（障害物の追加・削除がある場合）は、再探索や増分更新の手法（D*など）を検討する。
  • 実用的には、まず簡単なヒューリスティック（マンハッタン、ユークリッド）で試し、必要に応じて問題固有の情報を使った強いヒューリスティックを作ると良い。

派生・改良手法

  • Weighted A*：f = g + w·h（w > 1）とすることで高速化を図る手法。ただし最適性が失われる可能性がある。
  • IDA*（反復深化A*）：メモリ使用を抑えるために深さ制限を段階的に上げる探索。
  • 双方向A*：スタート側とゴール側から同時に探索して中央でぶつけることで探索空間を削減する方法。
  • ヒューリスティック整備：複数のヒューリスティックを組み合わせる（例えば支配関係のあるヒューリスティックを最大値で取る）などの工夫で効率が上がる。

まとめると、A*は「実コスト（g）」と「推定コスト（h）」を組み合わせて効率よく最短経路を探索する強力な手法です。ヒューリスティックの設計が鍵であり、問題の性質に合わせて適切なヒューリスティックや派生手法を選ぶことで、実用的で高速な経路探索が可能になります。

ステップ

A*はまず、あなたが行くことができるすべての場所のリストを必要とし、次にそれぞれの場所間の道のりのリストを必要とします。そして、A地点からZ地点に行くのに一番速い方法を教えてくれます。

AからZに行くには、A-B-D-Z, A-C-D-Z, A-B-E-Z, A-C-E-Zの4通りの行き方があります。A*を使うコンピュータは、まずAからB、AからCに行くのがどれだけ大変かを調べます。これは、それらの場所の「コスト」です。ある場所のコストとは、Aからその場所に行くのがどれだけ大変かということである。両方のコストを書き出した後、コンピュータはBからDに行くのがどれだけ大変かを調べ、Bのコストにこれを加える。これをDの費用として書き留めます。次にコンピュータは、CからDに行くのがどれだけ大変かを調べ、Cの費用にこれを加えます。これはDの別のコストであり、もしそれがすでに持っているコストより低ければ、古いものを交換することになります。コンピュータは最適な経路を知りたいだけなので、コストの高い経路は無視する。A-B-DとA-C-Dのどちらか速い方だけを記憶する。

最後に，D から Z まで行って費用を求め，E から Z まで行って費用を求めます．そして、最終的にZにかかる費用を求めますが、これが最も小さい費用です。これでコンピュータは、どの道が一番速いかを知り、答えを得たことになります。コンピュータは、同じような一連のステップを、もっと多くの場所で行うことができます。その都度、A に最も近い場所を探し、その場所の近隣にかかる費用を足し算します。

人は、上記の一連のステップをダイクストラアルゴリズムと呼びます。ダイクストラのアルゴリズムは、Zから間違った方向に行くかもしれない多くの場所を調べるので、遅くなることがあります。ある都市から近くの都市に行く方法をコンピュータに尋ねた場合、ダイクストラのアルゴリズムは別の州を調べることになるかもしれません。

この問題を解決するのがA*です。A*は、各場所から端までの距離をコンピュータに推測させるものである。コンピュータはその推測をもとに、ある場所からZまでの距離をおおまかに知ることができるのです。この総計は、残り距離の予想値にコストを足すことで求められる。こうすることで、より良くなりそうな方向だけを見ることができる。推測が完璧でなくても構わないが、単純に悪い推測でも、プログラムはかなり速く進む。現実の世界で2つの場所の間の道を見つけようとする場合、良い推測はちょうど直線でその間の距離です。道路を越える本当の道はもっと長くなりますが、これならプログラムが推測してくれるので、間違った方向には進みません。

数学やコンピュータサイエンスの文献では、この推測は場所の関数であることが多く、ヒューリスティックと呼ばれる。各場所が頂点で、2つの場所間の各経路が辺である。これはグラフ理論の言葉である。



百科事典を検索する
AlegsaOnline.com - 2020 / 2025 - License CC3