利用者:Greek Fellows/sandbox

探索 > 最良優先探索 > Greek Fellows/sandbox

A*探索アルゴリズム

A*（A-star, エースター）探索アルゴリズムは、探索アルゴリズムの一つ。 スタートノードからゴールノードまでの経路を計算する、このとき求める経路が最良（最短）であることを保証しているアルゴリズムである。 最良優先探索において、評価関数を許容的な物に制限した物がA*である。

概要

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

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

A* アルゴリズムは1968年に Peter E. Hart、Nils J. 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)$に置き換える。

$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\leq h^{*}(n)\leq h(n)$

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

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

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

ただし、

$\forall n,h_{1}^{*}(n)<h_{2}^{*}(n)\leq h(n)$

というヒューリスティック関数が存在する場合、構文解析に失敗 (構文エラー): {\displaystyle h_1^*(n)を用いるより<math>h_2^*(n)} を用いるほうが計算負荷は少なくてすむ。このため、そのようなヒューリスティックの存在がわかっている場合は 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)+\mathrm {COST} (n,m)$を計算する、ここで$\mathrm {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$までの最短経路が得られる。

部分問題に分割する場合

分割統治法のように、部分問題に分割したうえで全体問題を解いた方が効率的な問題もある。A* 同様の通常の状態遷移はどれかがゴールに到達すれば良いので OR と呼び、部分問題に分割する場合は全ての部分問題が解けないといけないので AND と呼ぶと、探索木が AND/OR 木になる。AND で状態を分割する際、ゴールも分割する必要がある。

同じ状態が2度出現した場合に1つのノードにまとめると AND/OR グラフになる。閉路のない AND/OR グラフに対する A* アルゴリズムに対応する物が1968年に開発され、1980年に AO* アルゴリズム と命名された。閉路のある AND/OR グラフに対する A* アルゴリズムに対応する A₀アルゴリズム は1976年に開発された。AND ノードのコストを「辺のコスト＋部分問題のコストの最大値」や「辺のコスト＋部分問題のコストの総和」などの単調非減少関数で定義すると、ヒューリスティック関数が許容的であれば、A* 同様、最適解が求まる。なお、閉路のない AND/OR グラフは文脈自由文法（タイプ-2 文法）、閉路のある AND/OR グラフは制限のない文法（タイプ-0 文法）に 1 対 1 対応することが証明されている。

関連項目

• 最良優先探索
• ダイクストラ法
• 均一コスト探索
• 双方向探索
• シェーキー

参照

[[Category:検索アルゴリズム]] [[Category:数学に関する記事]]