A* アルゴリズムは、「グラフ上でスタートからゴールまでの道を見つける」というグラフ探索問題において、 ヒューリスティック関数 ''h(n)'' という探索の道標となる関数を用いて探索を行うアルゴリズムである。hは各頂点nからゴールまでの距離のある妥当な推定値を返す関数で、解くグラフ探索問題の種類に応じてさまざまなhを設計することが出来る。 例えば、カーナビなどで用いられる単純な二次元の地図での探索では、hとしてユークリッド距離 <math>\sqrt{x^2 + y^2}</math> を使うことができ、この値は道に沿った実際の距離のおおまかな予測になっている。しかし、高次元空間でのグラフ探索を効率的に行うためには、より高度に設計された関数を用いる必要がある。例えば、[[15パズル]]においては[[マンハッタン距離]]や[[パターンデータベース]]、[[STRIPS]]プランニングにおいては[[FFヒューリスティック]]<ref name="#1">Hoffmann, Jörg, and Bernhard Nebel. "The FF planning system: Fast plan generation through heuristic search." Journal of Artificial Intelligence Research (2001): 253-302.</ref>(削除) , (削除ここまで)[[Merge-and-Shrink]]<ref name="#1"/>(削除) , (削除ここまで)[[Landmark-Cut]]<ref>Helmert, Malte, and Carmel Domshlak. "Landmarks, critical paths and abstractions: what's the difference anyway?." ICAPS. 2009.</ref> などがある。
A* アルゴリズムは、「グラフ上でスタートからゴールまでの道を見つける」というグラフ探索問題において、 ヒューリスティック関数 ''h(n)'' という探索の道標となる関数を用いて探索を行うアルゴリズムである。h(追記) (追記ここまで)は各頂点(追記) (追記ここまで)n(追記) (追記ここまで)からゴールまでの距離のある妥当な推定値を返す関数で、解くグラフ探索問題の種類に応じてさまざまな(追記) (追記ここまで)h(追記) (追記ここまで)を設計することが出来る。 例えば、カーナビなどで用いられる単純な二次元の地図での探索では、h(追記) (追記ここまで)としてユークリッド距離 <math>\sqrt{x^2 + y^2}</math> を使うことができ、この値は道に沿った実際の距離のおおまかな予測になっている。しかし、高次元空間でのグラフ探索を効率的に行うためには、より高度に設計された関数を用いる必要がある。例えば、[[15パズル]]においては[[マンハッタン距離]]や[[パターンデータベース]]、[[STRIPS]]プランニングにおいては[[FFヒューリスティック]]<ref name="#1">Hoffmann, Jörg, and Bernhard Nebel. "The FF planning system: Fast plan generation through heuristic search." Journal of Artificial Intelligence Research (2001): 253-302.</ref>(追記) 、 (追記ここまで)[[Merge-and-Shrink]]<ref name="#1"/>(追記) 、 (追記ここまで)[[Landmark-Cut]]<ref>Helmert, Malte, and Carmel Domshlak. "Landmarks, critical paths and abstractions: what's the difference anyway?." ICAPS. 2009.</ref> などがある。
一方、hが常に正しい値''h*''を返す場合、計算機は「迷うこと無く=分岐をすること無く」グラフ上の最短経路を発見することができる。そのようなhのことを、パーフェクト・ヒューリスティクスとよぶ<ref>How Good is Almost Perfect?. M Helmert, G Röger - AAAI, 2008</ref>。
一方、h(追記) (追記ここまで)が常に正しい値(追記) (追記ここまで)''h*''(追記) (追記ここまで)を返す場合、計算機は「迷うこと無く=分岐をすること無く」グラフ上の最短経路を発見することができる。そのような(追記) (追記ここまで)h(追記) (追記ここまで)のことを、パーフェクト・ヒューリスティクスとよぶ<ref>How Good is Almost Perfect?. M Helmert, G Röger - AAAI, 2008</ref>。
##* m が Openリストにも Closeリストにも含まれていない場合 <math>f(m) \leftarrow f'(m)</math> とし m を Openリストに追加する。このとき m の親を n として記録する。
##* m が Openリストにも Closeリストにも含まれていない場合 <math>f(m) \leftarrow f'(m)</math> とし m を Openリストに追加する。このとき m の親を n として記録する。
##* m が Openリストにある場合、<math>f'(m) < f(m)</math> であるなら、m をOpenから削除し、<math>f(m) \leftarrow f'(m)</math> に置き換え、再びOpenに挿入する(削除) (Open (削除ここまで)が正しくソートされていることを保証するため(削除) ) (削除ここまで)。また、記録してある m の親を n に置き換える。
##* m が Openリストにある場合、<math>f'(m) < f(m)</math> であるなら、m を(追記) (追記ここまで)Open(追記) (追記ここまで)から削除し、<math>f(m) \leftarrow f'(m)</math> に置き換え、再び(追記) (追記ここまで)Open(追記) (追記ここまで)に挿入する(追記) (Open (追記ここまで)が正しくソートされていることを保証するため(追記) ) (追記ここまで)。また、記録してある m の親を n に置き換える。
##* m が Closeリストにある場合、<math>f'(m) < f(m)</math> であるなら <math>f(m) \leftarrow f'(m)</math> として m を Openリストに移動する。また記録してある m の親を n に置き換える。
##* m が Closeリストにある場合、<math>f'(m) < f(m)</math> であるなら <math>f(m) \leftarrow f'(m)</math> として m を Openリストに移動する。また記録してある m の親を n に置き換える。
# 3 以降を繰り返す。
# 3 以降を繰り返す。
# 探索終了後、発見されたゴール <math>n_G</math> から親を順次たどっていくと S から ゴール <math>n_G</math> までの最短経路が得られる。
# 探索終了後、発見されたゴール <math>n_G</math> から親を順次たどっていくと S から ゴール <math>n_G</math> までの最短経路が得られる。
以上の流れを見れば、アルゴリズムが手続き的で、並列化が非常に難しいことがわかる。しかし、近年では [[HDA*]]<ref>Kishimoto, Akihiro, Alex S. Fukunaga, and Adi Botea. "Scalable, Parallel Best-First Search for Optimal Sequential Planning." ICAPS. 2009.</ref>(削除) , (削除ここまで)[[PBFS]] などの並列手法が開発され、特にHDA*は768コア以上の大規模並列計算環境にもスケールすることが実証されている。
以上の流れを見れば、アルゴリズムが手続き的で、並列化が非常に難しいことがわかる。しかし、近年では [[HDA*]]<ref>Kishimoto, Akihiro, Alex S. Fukunaga, and Adi Botea. "Scalable, Parallel Best-First Search for Optimal Sequential Planning." ICAPS. 2009.</ref>(追記) 、 (追記ここまで)[[PBFS]] などの並列手法が開発され、特に(追記) (追記ここまで)HDA*(追記) (追記ここまで)は768コア以上の大規模並列計算環境にもスケールすることが実証されている。
しかし、データ構造を工夫することで、より効率よい実装を行うことが出来る。ノードをOPEN/CLOSEリスト間で行ったり来たりさせる代わりに、以下のように実装する<ref>Burns, E. A., Hatem, M., Leighton, M. J., & Ruml, W. (2012, July). Implementing fast heuristic search code. In Fifth Annual Symposium on Combinatorial Search. https://www.aaai.org/ocs/index.php/SOCS/SOCS12/paper/view/5404/5173</ref>:
しかし、データ構造を工夫することで、より効率よい実装を行うことが出来る。ノードを(追記) (追記ここまで)OPEN/CLOSEリスト間で行ったり来たりさせる代わりに、以下のように実装する<ref>Burns, E. A., Hatem, M., Leighton, M. J., & Ruml, W. (2012, July). Implementing fast heuristic search code. In Fifth Annual Symposium on Combinatorial Search. https://www.aaai.org/ocs/index.php/SOCS/SOCS12/paper/view/5404/5173</ref>:
# それぞれのノードに、ノードの状態として OPEN, CLOSE の2種類のタグをもたせる。全てのノードは始めOPENである。
# それぞれのノードに、ノードの状態として OPEN, CLOSE の2種類のタグをもたせる。全てのノードは始めOPENである。
A* の探索効率は h の正確さに左右される。
もしも h がまったくでたらめな値を返すならば、探索はゴールとはあさっての方向に進んでしまい、現実的な時間内(一時間、一週間、一年)では解を発見できない場合がある。しかし、いくらおかしな方向に探索が進んだとしても、いつかは必ず解を発見できる保証がある(完全性)。
一方、h が常に正しい値 h* を返す場合、計算機は「迷うこと無く=分岐をすること無く」グラフ上の最短経路を発見することができる。そのような h のことを、パーフェクト・ヒューリスティクスとよぶ[4]。
現実に用いられる有用な h は、これらの中間の位置にある。
歴史
A* アルゴリズムは1968年に Peter E. Hart、Nils J. Nilsson、Bertram Raphael の三人が発表した論文[5]の中で最初に記述された。A* というこの一風変わった名前は、この論文でスタートからゴールまでの最短経路を確実に見つけるアルゴリズムを許容的(英: admissible)と呼び、論文の数式中に 許容的なアルゴリズムの集合を A と表し、そのAの中でも評価回数が最適になる物を A* と表記していたためである[6]。
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) に置き換えることを考える。
{\displaystyle f(n)=g(n)+h(n)}
ここで g(n) はスタートノードから n までの最小コストの推定値、h(n) は n からゴールノードまでの最小コストの推定値である。この場合 g に関しては探索の過程で更新を加えることにより g* に近づけてゆくことができるが、h* は、実際にゴールに辿り着くまでは誰にもわからない。そこで、h(n) には人間が(ある程度妥当性を持つように)設計した推定値を与えることにする。このアルゴリズムを A*探索アルゴリズムといい、h (n) をヒューリスティック関数という。
{\displaystyle f'(m)=g(n)+COST(n,m)+h(m)} を計算する、ここで {\displaystyle COST(n,m)} はノード n から m へ移動するときのコストである。また {\displaystyle g(n)} は {\displaystyle g(n)=f(n)-h(n)} で求めることができる。
m の状態に応じて以下の操作を行う
m が Openリストにも Closeリストにも含まれていない場合 {\displaystyle f(m)\leftarrow f'(m)} とし m を Openリストに追加する。このとき m の親を n として記録する。
m が Openリストにある場合、{\displaystyle f'(m)<f(m)} であるなら、m を Open から削除し、{\displaystyle f(m)\leftarrow f'(m)} に置き換え、再び Open に挿入する(Open が正しくソートされていることを保証するため)。また、記録してある m の親を n に置き換える。
m が Closeリストにある場合、{\displaystyle f'(m)<f(m)} であるなら {\displaystyle f(m)\leftarrow f'(m)} として m を Openリストに移動する。また記録してある m の親を n に置き換える。
3 以降を繰り返す。
探索終了後、発見されたゴール {\displaystyle n_{G}} から親を順次たどっていくと S から ゴール {\displaystyle n_{G}} までの最短経路が得られる。
分割統治法のように、部分問題に分割したうえで全体問題を解いた方が効率的な問題もある。A* 同様の通常の状態遷移はどれかがゴールに到達すれば良いので OR と呼び、部分問題に分割する場合は全ての部分問題が解けないといけないので AND と呼ぶと、探索木が AND/OR 木になる。AND で状態を分割する際、ゴールも分割する必要がある。
^Pearl, Judea (1984) (English). "Heuristics intelligent search strategies for computer problem solving". Addison-Wesley. ISBN0201055945
^ abHoffmann, Jörg, and Bernhard Nebel. "The FF planning system: Fast plan generation through heuristic search." Journal of Artificial Intelligence Research (2001): 253-302.
^Helmert, Malte, and Carmel Domshlak. "Landmarks, critical paths and abstractions: what's the difference anyway?." ICAPS. 2009.
^How Good is Almost Perfect?. M Helmert, G Röger - AAAI, 2008
^Russel, Norvig, Artificial intelligence: a modern approach
^Robert C. Holte. Common Misconceptions Concerning Heuristic Search, SoCS 2010
^Nils J. Nilsson (August 1968). "Searching problem-solving and game-playing trees for minimal cost solutions". Information Processing 68 : proceedings of IFIP Congress 1968 (Amsterdam : North-Holland) 2: 1556-1562.