A*

出典: フリー百科事典『ウィキペディア（Wikipedia）』
移動先: 案内、 検索

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

スタートノードからゴールノードまでのパスを計算する、このとき求めるパスが最短であることを保証しているアルゴリズムである。

概要

A* アルゴリズムは、各頂点nからゴールまでの距離の推定値 h* (n) を知っていた場合に対して最短経路問題（に帰着できる問題）を効率的に解くアルゴリズムである。 ただし、推定値は実際の距離と同じであるかないしそれより小さくなければならない。 例えば地図上を道路に沿って歩いたときの最短経路を求めたい場合、直線距離を h* (n) として用いる事ができる。

A* アルゴリズムは有名なアルゴリズムダイクストラ法を推定値つきの場合に一般化したもので、 大まかに言えば、ダイクストラ法を推定値が小さい方ものから順に探索するよう改良したものである。 推定値 h* (n) が恒等的に0である場合はもとのダイクストラ法に一致する。

A* アルゴリズムは1968年に Peter Hart、Nils Nilsson、Bertram Raphael の三人が発表した論文の中で最初に記述された。A* というこの一風変わった名前は、この論文でスタートからゴールまでの最短経路を確実に見つけるアルゴリズムを許容的 (Admissible) と呼び、論文の数式中に 許容的なアルゴリズムの集合を A と表し、そのAの中でも評価回数が最適になる物を A* と表記していたためであるといわれている。

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

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

と置くことが出来る。ここで g (n) はスタートノードから n までの最小コスト、h (n) はn からゴールノードまでの最小コストである。もし g (n) の値と h (n)の値を知っていれば、全体の最短経路f (n) は容易に求まる。しかしながら実際には g (n) と h (n) をあらかじめ与えることは出来ない、そこで f (n) を次のような推定値 f* (n) に置き換える。

<math>f^*(n) = g^*(n) + h^*(n)</math>

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

このとき h* (n) のことをヒューリスティック関数という。このアルゴリズムは h* (n) が以下の条件

<math>\forall n,0 \le h^*(n) \le h(n)</math>

を満たすとき、求まる経路がスタートからゴールまでの最短経路であることが保証されている。これをA*探索アルゴリズムという。

このアルゴリズムはCPUの使用率、メモリの使用率など、計算負荷は高いが、ヒューリスティック関数のヒント項を用いることにより、問題に対しての最適化が可能である。

もし各ノード間の最小のコストが既知であるとするならば、h*(n) をその最小コストを返す定数にすれば与えられた経路の状態に関係なく最短経路を求めることが可能になる。あるいは最小コストがわからないとしても上記の条件は h*(n) = 0 とするならば、常に成り立つことになる。この方法はダイクストラ法と呼ばれており、汎用的にはこちらの方法が使われている。

ただし

<math>\forall n,h_1^*(n) < h_2^*(n) \le h(n)</math>

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

アルゴリズムの流れ

A* のアルゴリズムの実装を以下に示す。

  1. ゴールノード（G ）とスタートノード（S ）を作成する。また計算中のノードを格納しておくためのリスト（Openリスト）と、計算済みのノードを格納しておくリスト（Closeリスト）を用意する。
  2. スタートノードをOpenリストに追加する、このとき g*(S) = 0 であり f*(S) = h*(S) となる。また Closeリストは空にする。
  3. Openリストが空なら探索は失敗とする（スタートからゴールにたどり着くような経路が存在しなかったことになる）。
  4. Openリストに格納されているノードの内、最小の f*(n) を持つノード n を取り出す。
  5. n = G であるなら探索を終了する。それ以外の場合は n を Close リストに移す。
  6. n に隣接している全てのノード（ここでは隣接ノードを m とおく）に対して以下の操作を行う
    1. f '(m) = g*(n) + h*(m) + COST(n,m) を計算する、ここで COST(n,m) はノード n から m へ移動するときのコストである。また g*(n) は g*(n) = f*(n) - h*(n) で求めることができる。
    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 に置き換える。
  7. 3 以降を繰り返す。
  8. 探索終了後 G から親を順次たどっていくと S から G までの最短経路が得られる。

関連項目

参考文献

  • Hart, P. E.; Nilsson, N. J.; Raphael, B. (1968). "A Formal Basis for the Heuristic Determination of Minimum Cost Paths". IEEE Transactions on Systems Science and Cybernetics SSC4 (2): pp. 100–107. PDFテンプレート:Link GA
「http://wikippe.e-do-match.com/index.php?title=A*&oldid=110812」から取得