A*（A-star, エースター）探索アルゴリズムは、グラフ探索アルゴリズムの一つ。最良優先探索を拡張したZ*に、さらにf値として「現時点までの距離」gと「ゴールまでの推定値」hの和を採用したもの。 h は ヒューリスティック関数と呼ばれる。A* アルゴリズムは、「グラフ上でスタートからゴールまでの道を見つける」というグラフ探索問題において、 ヒューリスティック関数 "h(n)" という探索の道標となる関数を用いて探索を行うアルゴリズムである。hは各頂点nからゴールまでの距離のある妥当な推定値を返す関数で、解くグラフ探索問題の種類に応じてさまざまなhを設計することが出来る。 例えば、カーナビなどで用いられる単純な二次元の地図での探索では、hとしてユークリッド距離 formula_1 を使うことができ、この値は道に沿った実際の距離のおおまかな予測になっている。しかし、高次元空間でのグラフ探索を効率的に行うためには、より高度に設計された関数を用いる必要がある。例えば、15パズルにおいてはマンハッタン距離やパターンデータベース、STRIPSプランニングにおいてはFFヒューリスティック,Merge-and-Shrink,Landmark-Cut などがある。A* アルゴリズムは、ダイクストラ法を推定値つきの場合に一般化したもので、h が恒等的に0である場合はもとのダイクストラ法に一致する。A*の探索効率はhの正確さに左右される。もしもhがまったくでたらめな値を返すならば、探索はゴールとはあさっての方向に進んでしまい、現実的な時間内 --- 一時間、一週間、一年 --- では解を発見できない場合がある。しかし、いくらおかしな方向に探索が進んだとしても、いつかは必ず解を発見できる保証がある(完全性)。一方、hが常に正しい値"h*"を返す場合、計算機は「迷うこと無く=分岐をすること無く」グラフ上の最短経路を発見することができる。そのようなhのことを、パーフェクト・ヒューリスティクスとよぶ。現実に用いられる有用なhは、これらの中間の位置にある。A* アルゴリズムは1968年に Peter E. Hart、Nils J. Nilsson、Bertram Raphael の三人が発表した論文の中で最初に記述された。A* というこの一風変わった名前は、この論文でスタートからゴールまでの最短経路を確実に見つけるアルゴリズムを許容的 () と呼び、論文の数式中に 許容的なアルゴリズムの集合を A と表し、そのAの中でも評価回数が最適になる物を A と表記していたためである。スタートノードから、あるノード "n" を通って、ゴールノードまでたどり着くときの最短経路を考える。このときこの最短経路のコストを "f* (n)" とおくと、と置くことが出来る。ここで "g* (n)" はスタートノードから "n" までの最小コスト、"h* (n)" は"n" からゴールノードまでの最小コストである。もし "g* (n)" の値と "h* (n)"の値を知っていれば、全体の最短経路"f* (n)" は容易に求まる。しかしながら実際には "g* (n)" と "h* (n)" をあらかじめ与えることは出来ない。そこで "f* (n)" を次のような推定値 "f (n)" に置き換えることを考える。ここで "g(n)" はスタートノードから "n" までの最小コストの推定値、"h(n)" は "n" からゴールノードまでの最小コストの推定値である。この場合 "g" に関しては探索の過程で更新を加えることにより"g*"に近づけてゆくことができるが、 "h*" は、実際にゴールに辿り着くまでは誰にもわからない。そこで、 "h(n)" には人間が(ある程度妥当性を持つように)設計した推定値を与えることにする。このアルゴリズムを A*探索アルゴリズムといい、 "h (n)" をヒューリスティック関数という。A* のアルゴリズムの実装を以下に示す。以上の流れを見れば、アルゴリズムが手続き的で、並列化が非常に難しいことがわかる。しかし、近年では HDA*, PBFS などの並列手法が開発され、特にHDA*は768コア以上の大規模並列計算環境にもスケールすることが実証されている。A*の性質はhの性質によって大きく左右される。このとき、A*の返す経路は最適、つまり最短経路である。このアルゴリズムはCPUの使用率、メモリの使用率など、計算負荷は高いが、問題に応じた適切なヒューリスティック関数を用いることにより、問題に対しての最適化が可能である。分割統治法のように、部分問題に分割したうえで全体問題を解いた方が効率的な問題もある。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対応することが証明されている。

出典:wikipedia