🧩
[まとめ] A*アルゴリズムとその発展

2025/07/14に公開
 はじめにA*アルゴリズムとは、最適経路探索における代表的なアルゴリズムの1つです。1968年にPeter Hardらによって発表されました。現在はロボティクス・自動運転からゲームAIにまで、数多くの場面で使われるものとなっています。そんなA*アルゴリズムは発表から約50年の歴史があることから、多くの派生的アルゴリズムが誕生しています。この記事ではそんなA*アルゴリズムの派生形について解説していきます。
また今回、様々なA*アルゴリズムとDijkstra法の非常に簡単なビジュアライザを作りました。以下に置いておきます。

 最適経路探索の問題設定最適経路問題では、幅w, 高さh, の地図を見ながら、障害物を適切によけながらいかに最短経路を探せるかを考えます。Dijkstra法やA*では、この問題を経路の「コストの合計」（あるいは総コスト）を最小化するという問題に置き換えます。一番単純な例を考えてみましょう。以下のようにスタートとゴールが設定されているとします。
この場合、スタートとゴールとの間は以下のように、様々な経路を使ってたどることができます。しかし、経路１は経路２に比べて明らかに遠回りです。この場合、Dijkstra法やA*では、経路１よりも経路２の総コストの方が低いという風に設定するのです。このような感じですべての経路に総コストを設定して、その中で一番総コストの低いものが最適経路ということになります。

 A*アルゴリズムとその発展A*アルゴリズムは非常にホットな研究テーマだったことから、これまでに多くの派生形を生み出してきました。その中でも比較的メジャーだといえるものをいくつかピックアップして紹介します。

 (おさらい) Dijkstra法とはA*の解説の前に、簡単にDijkstra法についておさらいします。Dijkstra法は多くの最適経路探索の基礎となるアルゴリズムです。探索を進める中で、そこで優先度付きキューを用いて一番コストの小さい経路から順に探索を進めていくという流れになっています。

 用語優先度キュー

優先度キューとは、キューの中の要素がそれぞれ値と優先度を持ち、優先度の高い(コスト低)要素から取り出されるというデータ構造を表します。
オープンリスト・クローズドリスト

オープンリストとは探索候補をまとめたリストのことを指します。基本的にDijkstra法やA*アルゴリズムではオープンリストに優先度キューが用いられ、優先度の高い(コスト低)ものから順に探索を進めていきます。一方で、クローズトリストとは、探索済みの要素をまとめたリストのことを指します。Dijkstra法・A*アルゴリズムではこれら2つのリストが用います。

 アルゴリズムの流れDijkstra法のアルゴリズムは以下のような流れで進行します：
# 初期化
1. スタートノードのコストを0に設定
2. オープンリスト(探索候補)にスタートノードを追加
3. クローズドリスト(探索済み)を空で初期化

# メインループ
while オープンリスト(探索候補)が空でない
   1. オープンリストから最小コストのノードuを選択し取り出す(優先度キュー)
   2. ノードuをクローズドリスト(探索済み)に移す
   3. もしノードuがゴールに一致していたならばその時点でwhileを抜ける
   4. ノードuの隣接ノードvそれぞれに対して、次の処理を行う
      a. vがクローズドリスト(探索済み)に入っていたなら飛ばす
      b. 新しいコスト = uのコスト + u->vの移動コスト
      c. もしvがオープンリストにない、または新コストがvの現在のコストより小さければ
         1. vのコストを更新
         2. vの親をuに設定
         3. vがオープンリストになければ追加

# 経路復元
ゴールから親ノードを辿ってスタートまで戻ることで最適経路を取得

 基本的なA*アルゴリズムについてここでは1968年に発表された、一番基本的なA*アルゴリズムについて簡単に解説します。簡単のため、7*7で真ん中に壁を置いた次のような地図を考えます。上下左右にしか動けないこととします。（つまり斜め移動は省く。）スタート、ゴールを左下・右上において、最適経路を求めます。
A*アルゴリズムの真髄は、地図上の位置それぞれに対し以下のコスト関数を用いてその場所のコストを計算し、最終的な経路の総コストを算出することです。
 f(n) = g(n) + h(n) ここで：

g(n): スタートからノードnまでの実際のコスト（実コスト）

h(n): ノードnからゴールまでの推定コスト（ヒューリスティック関数）
つまり、g(n)というすでに分かっていることから算出したコストに加えて、h(n)という、必ずしも正しくはない予測のコストを入れているのです。これにより、その地点からゴールが近"そう"な方向に探索が優先されるため、Dijkstra法に比べて、一般的には早い時間、少ないメモリ使用量で探索が行えるのです。なお、ヒューリスティック関数の選び方、つまりはコストの予測の仕方に制限は特にないため、これの選び方を適切にする必要があります。一番単純な例では、単に障害物を考えない、ゴールとの直線距離も予測コストのh(n)になり得ます。
例えば今回の例に当てはめると、4方向移動なので、L1ノルム(マンハッタン距離)を用いましょう。地図上のある一点を(x_1, y_1), ゴールを(x_2, y_2)として、h(n)は以下。
 h(n) = |x_1 - x_2| + |y_1 - y_2| A*アルゴリズムの1つの特徴として、適切なヒューリスティック関数を定めた場合、最終的には必ず最適解が保証されるということがあります。

 アルゴリズムの流れ# 初期化
1. スタートノードのコストを0に設定
2. オープンリスト(探索候補)にスタートノードを追加
3. クローズドリスト(探索済み)を空で初期化

# メインループ
while オープンリスト(探索候補)が空でない
   1. オープンリストから最小コストf(u) = g(u) + h(u)のノードuを選択し取り出す(優先度キュー)
   2. ノードuをクローズドリスト(探索済み)に移す
   3. もしノードuがゴールに一致していたならばその時点でwhileを抜ける
   4. ノードuの隣接ノードvそれぞれに対して、次の処理を行う
      a. vがクローズドリスト(探索済み)に入っていたなら飛ばす
      b. 新しいコスト = uのコスト + u->vの移動コスト
      c. もしvがオープンリストにない、または新コストがvの現在のコストより小さければ
         1. vのコストを更新
         2. vの親をuに設定
         3. vがオープンリストになければ追加

# 経路復元
ゴールから親ノードを辿ってスタートまで戻ることで最適経路を取得
A*アルゴリズムは、f(n)値の小さいノードから優先的に探索することで、無駄な探索を避けながら最適経路を見つけます。Dijkstra法と異なり、ゴールへのヒューリスティックを活用することで、より効率的な探索が可能になります。
さて、A*アルゴリズムには様々な派生形があります。その中では例えば、新しいヒューリスティックの提案や、根本的な手法の改善等があげられます。今回は根本的な手法の改善に主に焦点を向けて解説をします。

 重み付きA*アルゴリズム (Weighted A*)重み付きA*\アルゴリズムとは、先ほどのコスト関数のヒューリスティック項（予測項）に重みwを掛けることで、探索時間の高速化を図ったものです。
 f(n) = g(n) + w \ h(n) 基本的に重みwは1以上であり、これによって判断材料の中で予測が占めるの割合が上がることから、適切にヒューリスティック関数が設定されていた場合、ゴールに向かおうとする力が強くなります。これによって、より絞られた範囲・最適化された範囲に探索が入るので、探索にかかる時間が減少し、メモリ使用量も少なくなります。
一方でその代償として、重み付きA*アルゴリズムは最適経路を見つけるという保証はありません。特にwが小さすぎればあまり探索時間は変わらない一方で、wが大きすぎれば解の質が下がってしまうので、この塩梅を見つけるのが難しいという問題があります。

 アルゴリズムの流れ# 初期化
1. スタートノードのコストを0に設定
2. オープンリスト(探索候補)にスタートノードを追加
3. クローズドリスト(探索済み)を空で初期化

# メインループ
while オープンリスト(探索候補)が空でない
   1. オープンリストから最小コストf(u) = g(u) + w * h(u)のノードuを選択し取り出す(優先度キュー)
   2. ノードuをクローズドリスト(探索済み)に移す
   3. もしノードuがゴールに一致していたならばその時点でwhileを抜ける
   4. ノードuの隣接ノードvそれぞれに対して、次の処理を行う
      a. vがクローズドリスト(探索済み)に入っていたなら飛ばす
      b. 新しいコスト = uのコスト + u->vの移動コスト
      c. もしvがオープンリストにない、または新コストがvの現在のコストより小さければ
         1. vのコストを更新
         2. vの親をuに設定
         3. vがオープンリストになければ追加

# 経路復元
ゴールから親ノードを辿ってスタートまで戻ることで最適経路を取得

 双方向A*アルゴリズム (Bidirectional A*)Bidirectional A*アルゴリズムでは、スタートとゴールの双方向から交互にコスト関数を適用して探索を行います。Dijkstra法やA*アルゴリズムの問題点の1つに、必要となる探索の深さが深くなればなるほど、必要なメモリ量が指数的に増加してしまうという問題があります。ゆえに、二方向から行うことで理想的な場合では探索の深さを半分とできるため、必要メモリ量を減らすことができるのです。
一方で、合流地点が明確に定まっていないので、常に探索フロンティア(Search Frontier)がお互い重なったかどうか(お互い合流したかどうか)を調べないといけません。これは多対多の比較となるため複雑になります。また、理想的な場合は必要なメモリ量を多く減らせますが、最悪の場合にはメモリ量が従来の2倍必要となります。

 アルゴリズムの流れ# 初期化
1. スタートノードのコストを0に設定し、前方探索のオープンリストに追加
2. ゴールノードのコストを0に設定し、後方探索のオープンリストに追加
3. 前方・後方それぞれのクローズドリストを空で初期化
4. 最良解のコストを無限大に初期化

# メインループ
while 前方または後方のオープンリストが空でない
   1. スタートからの探索:
      a. 前方探索用のオープンリストから最小コストf_forward(u) = g_forward(u) + h_forward(u)のノードuを選択し取り出す
      b. ノードuを前方クローズドリストに移す
      c. もしuが後方クローズドリストにあれば、経路を構築して最良解を更新
      d. uの隣接ノードvそれぞれに対して処理（通常のA*と同様）
   2. ゴールからの探索:
      a. 後方探索用のオープンリストから最小コストf_backward(u) = g_backward(u) + h_backward(u)のノードuを選択し取り出す
      b. ノードuを後方クローズドリストに移す
      c. もしuが前方クローズドリストにあれば、経路を構築して最良解を更新
      d. uの隣接ノードvそれぞれに対して処理（通常のA*と同様）
   
   3. 終了条件の確認:
      両方向の探索フロンティアが重なり、最良解が見つかれば終了

# 経路復元
前方探索と後方探索の合流点から、それぞれスタートとゴールまで辿って最適経路を構築

 Anytime A*アルゴリズムにリアルタイム性が求められる場合には、多少精度を犠牲にしても速度が要求される場合があります。一方で、多少時間に猶予がある場合においては精度をある程度担保したいという気持ちもあります。このような2つの側面を両立するアルゴリズム群をAnytimeアルゴリズムと呼びます。
Anytime A*はAnytimeアルゴリズムの1つで、最もざっくりといえば、「Weighted A*を何度も反復しながら、反復の度に重みwの値をどんどん減らして、徐々に1に近づける」ということになります。先ほど解説したように、Weighted A*はwを上げると精度を犠牲にして速度が上がります。はじめは大きなwにして精度を犠牲にして大雑把な解を出し、その後時間的余裕があれば精度の高い解を出すということなのです。
Anytime A*にも様々な種類があります。ここではARA*(Anytime Repairing A*)を解説します。

 Anytime Repairing A*重みwの値を徐々に1に近づけていくといっても、そのままのA*を何度も繰り返すというのは非常に効率が悪いです。Anytime Repairing A*では局所的不整合(local inconsistency)の考え方を用いて無駄な再探索を行わないことで、計算量を減らします。
局所的不整合とは、基本的には既に探索済みのノードのスタートから既知のコストg(n)が、重みを下げた探索(より精度の高い探索)で低くなった時(より最適な経路が見つかった時)に起きる、2つのコストの不整合を指します。この場合、そこからの後続経路のコスト等が変わりうるため、そこを起点に再探索を行うことで最短経路を改善できる可能性があります。
アルゴリズムの流れとしては、初めに大きな重みwでとりあえずの最短経路を見つけます。その後、重みを下げて再探索を行う際、既に展開済みのノードのコストが改善された場合、そのノードはINCONSリスト(Inconsistency List)に追加されます。このINCONSリストの各要素は次の探索の開始前にオープンリストに移され、新たな重みwで再評価されます。こうして反復探索が行われることで、計算量を抑えつつ精度を上げながらの探索が可能となるのです。

 アルゴリズムの流れ# 初回探索
1. スタートノードのコストを0に設定
2. オープンリストにスタートノード
3. クローズドリストとINCONSリストを空で初期化
4. ImprovePath()を実行
5. 準最適解を公開

# 経路最適化
while w > 1
   1. wを減少させる
   2. INCONSリストの全要素をオープンリストに移す
   3. オープンリストの全要素の優先度を新しいwで更新(f(n) = g(n) + w * h(n))
   4. クローズドリストを空にリセット
   5. ImprovePath()を実行
   6. 新しい準最適解を公開
# ImprovePath
while f(goal) > min_{u∈OPEN}(f(u))
   1. オープンリストから最小コストf(u) = g(u) + w * h(u)のノードuを選択し取り出す(優先度キュー)
   2. ノードuをクローズドリスト(探索済み)に移す
   3. ノードuの隣接ノードvそれぞれに対して、次の処理を行う
      a. もしvが未訪問なら、g(v)を無限で初期化
      b. もしg(v) > g(u) + (u->vへの移動コスト)なら
         1. g(v) = g(u) + (u->vへの移動コスト)とする
         2. もしvがクローズドリストに入っていなければ、オープンリストに追加
         3. もしvがクローズドリストに入っていたら、INCONSリストに追加

 Theta*Theta*は少し毛色が異なり、美しく滑らかに動ける経路を求めることに特化しています。A*は隣接するノード以外には直接探索を行えなかったのに対して、Theta*では**視線(line of sight)**が遮られるような障害物がない限りはどのノードからどのノードへも移ることができるとします。
つまり、今までは隣接ノードを中間地点として多く経由しないといけなかったのに対して、Theta*ではそれらを考慮せず一直線に経路を引くことができるようになるため、より滑らかに経路が生成できるというわけなのです。

 アルゴリズムの流れ# 初期化
1. スタートノードのコストを0に設定
2. オープンリスト(探索候補)にスタートノードを追加
3. クローズドリスト(探索済み)を空で初期化

# メインループ
while オープンリスト(探索候補)が空でない
   1. オープンリストから最小コストf(u) = g(u) + h(u)のノードuを選択し取り出す(優先度キュー)
   2. ノードuをクローズドリスト(探索済み)に移す
   3. もしノードuがゴールに一致していたならばその時点でwhileを抜ける
   4. ノードuの隣接ノードvそれぞれに対して、次の処理を行う
      a. vがクローズドリスト(探索済み)に入っていたなら飛ばす
      b. Line of Sight チェック: uの親からvへの直線経路に障害物がないかチェック
      c. もしLine of Sightが通っていれば:
         1. 新しいコスト = uの親のコスト + uの親->vの直線距離コスト
         2. もしこのコストがvの現在のコストより小さければ:
            - vのコストを更新
            - vの親をuの親に設定
      d. そうでなければ (通常のA*と同様):
         1. 新しいコスト = uのコスト + u->vの移動コスト
         2. もしこのコストがvの現在のコストより小さければ:
            - vのコストを更新
            - vの親をuに設定
      e. vがオープンリストになければ追加

# 経路復元
ゴールから親ノードを辿ってスタートまで戻ることで最適経路を取得
[まとめ] A*アルゴリズムとその発展

はじめに

最適経路探索の問題設定

A*アルゴリズムとその発展

(おさらい) Dijkstra法とは

用語

アルゴリズムの流れ

基本的なA*アルゴリズムについて

アルゴリズムの流れ

重み付きAアルゴリズム (Weighted A)

アルゴリズムの流れ

双方向Aアルゴリズム (Bidirectional A)

アルゴリズムの流れ

Anytime A*

Anytime Repairing A*

アルゴリズムの流れ

Theta*

アルゴリズムの流れ

Discussion
