A*

出典: フリー百科事典『ウィキペディア（Wikipedia）』

A*（A-star, エースター）探索アルゴリズムは、経路探索アルゴリズムの一つ。

スタートノードからゴールノードまでの最短パスを計算する。最短パスの発見を保証しているアルゴリズムである。

[編集] 概要

スタートノードから、あるノード n を通って、ゴールノードまでたどり着くときの最短経路を考える。このとき最短経路のコストを f (n) とおくと、

f (n) = g (n) + h (n)

と置くことが出来る。ここで g (n) はスタートノードから n までの最小コスト、h (n) はn からゴールノードまでの最小コストである。もし g (n) と h (n) が一意に決まるのなら最短経路は簡単に求まる。しかしながら実際には g (n) と h (n) をあらかじめ与えることは出来ない、そこで f (n) を次のような f^* (n) に置き換える。

f * (n) = g * (n) + h * (n)

ここで g^* (n) はスタートノードから n までの最小コストの推定値、h^* (n) はn からゴールノードまでの最小コストの推定値である。この場合 g^* (n) に関しては探索の課程で推定値を求めていくことができるが、 h^* (n) を推定することはできない。そこで h^* (n) には適当な推定値を与え g^* (n) は探索しながら適宜更新することで経路を求めるアルゴリズムをA探索アルゴリズムという。このとき h^* (n) のことをヒューリスティック関数という。このアルゴリズムは h^* (n) が以下の条件

$\forall n,0 \le h^*(n) \le h(n)$

を満たすとき求まる経路が最短経路であることが保証されている。これがA*探索アルゴリズムである。この方法はCPU使用率、メモリ使用率など、計算負荷は高いが、ヒューリスティック関数のヒント項を用いることにより、その問題に最適化が可能である。なお各ノード間の最小のコストがわかっているなら h^*(n) をそのコストの定数にすることによってどのようなグラフに対しても最短経路を求めることが可能になる。あるいは最小コストがわからなくても h^*(n) = 0 とすれば常に成り立つことになる。この方法はダイクストラ法と呼ばれていて汎用的にはこちらが使われている。ただし

$\forall n,h_1^*(n) < h_2^*(n) \le h(n)$

というヒューリスティック関数が存在する場合は h₁^* を用いるより h₂^* を用いるほうが計算負荷は少なくてすむ。このため、そのようなヒューリスティックの存在がわかっている場合は A* アルゴリズムの方が有利になる。

[編集] A*アルゴリズムに使用される用語

スタートノード: 開始するノード。
ゴールノード: 到達目標のノード。
現在のノード: アルゴリズム中で使用する、計算中のノード。
隣接ノード: 現在のノードに隣接するノード。
Openリスト: 計算中のノードを格納しておくリスト。
Closedリスト: 計算済みのノードを格納しておくリスト。
コスト: ノード間の移動に必要な重み。ノード間の距離、傾斜、リスク等、問題に応じて内容は変化する。

[編集] アルゴリズムの流れ

ゴールノード（G ）とスタートノード（S ）を作成する。
スタートノードをOpenリストに追加する、このとき g^*(S) = 0 であり f^*(S) = h^*(S) となる。また Closeリストは空にする。
Openリストが空なら探索は失敗とする（スタートからゴールまでの経路がなかったことになる）。
Openリストに格納されているノードの内、最小の f^*(n) を持つノード n を取り出す。
n = G であるなら探索を終了する。それ以外の場合は n を Closeリストに移す。
n の全ての隣接ノード（ここでは隣接ノードを m とおく）に対して以下の操作を行う
1. f '(m) = g^*(n) + h^*(m) + COST(n,m) を計算する、ここで COST(n,m) はノード n から m へ移動するときのコストである。
2. m の状態に応じて以下の操作を行う
  - m が Openリストにも Closeリストにも含まれていない場合 f^*(m) = f '(m) とし m を Openリストに追加する。このとき m の親を n として記録する。
  - m が Openリストにある場合、f '(m) < f^*(m) であるなら f^*(m) = f '(m) に置き換える。このとき記録してある m の親を n に置き換える。
  - m が Closeリストにある場合、f '(m) < f^*(m) であるなら f^*(m) = f　'(m) として m を Openリストに移動する。また記録してある　m の親をn に置き換える。
3 以降を繰り返す。