A*のソースを表示

{{混同|x1=[[天体]]の|いて座A*}}
{{pathnav|探索|最良優先探索|frame=1}}
[[Image:Astar progress animation.gif|thumb|A*探索アルゴリズム]]

'''A*（A-star、エースター）探索アルゴリズム'''（エースターたんさくアルゴリズム）は、[[グラフ (データ構造)|グラフ]][[探索]][[アルゴリズム]]の一つ。
[[最良優先探索]]を拡張した[[Z*]]に、さらにf値として「現時点までの距離」g と「ゴールまでの推定値」h の和を採用したもの<ref>{{Cite book |last=Pearl |first=Judea |authorlink=ジューディア・パール |title="Heuristics intelligent search strategies for computer problem solving" |year=1984 |isbn=0201055945 |language=English ||publisher=Addison-Wesley }}</ref>。h はヒューリスティック関数と呼ばれる。

== 概要 ==
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 が恒等的に 0 である場合はもとのダイクストラ法に一致する。

A* の探索効率は h の正確さに左右される。
もしも h がまったくでたらめな値を返すならば、探索はゴールとはあさっての方向に進んでしまい、現実的な時間内（一時間、一週間、一年）では解を発見できない場合がある。しかし、いくらおかしな方向に探索が進んだとしても、いつかは必ず解を発見できる保証がある（完全性）。
一方、h が常に正しい値 ''h*'' を返す場合、計算機は「迷うこと無く=分岐をすること無く」グラフ上の最短経路を発見することができる。そのような h のことを、パーフェクト・ヒューリスティクスとよぶ<ref>How Good is Almost Perfect?. M Helmert, G Röger - AAAI, 2008</ref>。
現実に用いられる有用な h は、これらの中間の位置にある。

== 歴史 ==
A* アルゴリズムは[[1968年]]に [[:w:Peter E. Hart|Peter E. Hart]]、[[:w:Nils John Nilsson|Nils J. Nilsson]]、[[:w:Bertram Raphael|Bertram Raphael]] の三人が発表した論文の中で最初に記述された<ref>{{Cite journal |author=Peter E. Hart |author2=Nils J. Nilsson |author3=Bertram Raphael |title=A Formal Basis for the Heuristic Determination of Minimal Cost Paths |url=http://ai.stanford.edu/~nilsson/OnlinePubs-Nils/PublishedPapers/astar.pdf |journal=IEEE Transactions on Systems Science and Cybernetics |volume=4 |issue=2 |pages=100-107 |doi=10.1109/TSSC.1968.300136 |year=1968 |month=July |issn=0536-1567 }}</ref>。A* というこの一風変わった名前は、この論文でスタートからゴールまでの最短経路を確実に見つけるアルゴリズムを'''許容的'''（{{lang-en-short|admissible}}）と呼び、論文の数式中に 許容的なアルゴリズムの[[集合]]を '''A''' と表し、その'''A'''の中でも評価回数が最適になる物を '''A<sup>*</sup>''' と表記していたためである<ref name="nillson1980"/>。

== 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'' に関しては探索の過程で更新を加えることにより ''g*'' に近づけてゆくことができるが、''h*'' は、実際にゴールに辿り着くまでは誰にもわからない。そこで、''h(n)'' には人間が（ある程度妥当性を持つように）設計した推定値を与えることにする。このアルゴリズムを '''A*探索アルゴリズム'''といい、''h (n)'' を[[ヒューリスティック]]関数という。

== アルゴリズムの流れ ==
A* のアルゴリズムの実装を以下に示す。この OPENリスト実装は後に述べるように遅いことを記しておく。
# スタートノード（<math>S</math>）を作成する。また計算中のノードを格納しておくための[[優先度付きキュー]] '''OPENリスト'''と、計算済みのノードを格納しておく'''CLOSEリスト'''を用意する。（名前は「リスト」だが、これらの実際のデータ構造は必ずしも[[連結リスト]]である必要はない。）
# ゴールは必ずしも１つである必要はないので、ゴール条件を満たすノード集合を <MATH>G</MATH> と呼ぶことにする。
# スタートノードを Openリストに追加する、このとき <math>g(S)</math> = <math>0</math> であり <math>f(S)</math> = <math>h(S)</math> となる。また Closeリストは空にする。
# Openリストが空なら探索は失敗とする（スタートからゴールにたどり着くような経路が存在しなかったことになる）。
# Openリストに格納されているノードの内、最小の <math>f(n)</math> を持つノード <math>n</math> を1つ取り出す。同じ <math>f(n)</math> を持つノードが複数ある場合、タイブレーク手法によりどれかのノードを選択する。
# <math>n \in G </math> であるなら探索を終了する。それ以外の場合は <math>n</math> を Close リストに移す。
# <math>n</math> に隣接している全てのノード（ここでは隣接ノードを <math>m</math> とおく）に対して以下の操作を行う
## <math>f'(m) = g(n) + COST(n,m) + h(m)</math> を計算する、ここで <math>COST(n,m)</math> はノード n から m へ移動するときのコストである。また <math>g(n)</math> は <math>g(n) = f(n) - h(n)</math> で求めることができる。
## m の状態に応じて以下の操作を行う
##* 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 が Closeリストにある場合、<math>f'(m) < f(m)</math> であるなら <math>f(m) \leftarrow f'(m)</math> として m を Openリストに移動する。また記録してある m の親を n に置き換える。
# 3 以降を繰り返す。
# 探索終了後、発見されたゴール <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コア以上の大規模並列計算環境にもスケールすることが実証されている。

== 実際に使われているOPEN/CLOSEリストの実装 ==
OPEN/CLOSEリストに登録されているノードの数が多い場合、ノードの展開ごとに子ノード m をOPENから CLOSE へ移動（あるいは逆）するのは非常に高価な操作である。
たとえば、OPEN/CLOSEリストが2分探索木（[[赤黒木]]など）で実装されている場合、まずノードの探すのに <math>O(log N)</math> かかり（ノードのIDで検索）、また削除にも <math>O(log N)</math> かかる。配列の場合には削除により大きなコストがかかる。

しかし、データ構造を工夫することで、より効率よい実装を行うことが出来る。ノードを 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である。
# ノードに一意な整数 ID をもたせる。
# また、ID からノードを <math>O(1)</math> で参照できる[[ハッシュテーブル]]を用意する。
# OPEN にノードを追加する際には、m が Openリストに含まれているかは検証せず、重複を許して追加する。かつ、このときノードではなく ID のみを追加する。
## ID は整数1つ分なので、重複のオーバーヘッドを最小化出来る。
# OPEN からノードを pop する際、pop したノードの状態が OPEN であれば展開を行うが、CLOSE であれば単にスキップする。
## このことにより、重複があっても同じノードを無駄に展開しないようにできる。
## このことにより、OPENリストは、f値による[[優先度付きキュー]]の下に先入れ先出し/[[FILO|先入れ後出し]]のキューを用意することで実装できる。
## ノードの検索がおこなわれず、かつ削除が先頭あるいは末尾にしかおこらないので、効率的な実装が可能である。
# CLOSEリストは使用しない。
# f値による優先度付きキューは、辺のコストが1である場合には単にf値ごとの可変配列にしたほうが高速な操作が可能である。
## 辺のコストに大幅なばらつきがある場合には、ヒープとして実装したほうがよい。

== 性質 ==
A* の性質は h の性質によって大きく左右される。

* A* はダイクストラの一般化であり、ダイクストラと同様、グラフに負のコストの辺があれば完全性を失う。その場合には[[ベルマン–フォード法]]を用いる。
* h(n) は常に非負でなくてはならない。
* あるヒューリスティクス h(n) が 全てのノード n について 真のゴール距離 h*(n) を上回らない場合、h は Admissible/'''許容的'''であると言う。
:<math>\forall n,0 \le h(n) \le h^*(n)</math>
このとき、A*の返す経路は[[最適]]、つまり最短経路である。
* あるヒューリスティクス h(n) について、全てのノード n と、それに隣接しているノード m について <math> h(n) \le cost(n,m) + h(m) </math> である場合、その h はconsistent/'''無矛盾'''であるという。
* consistent な h は、常に admissible である<ref>Russel, Norvig, Artificial intelligence: a modern approach</ref>。
* ある2つのヒューリスティック関数 h1, h2 について、<math>\forall n,h_1(n) \le h_2(n) </math> が成り立つ時、 h2 は h1 を支配する (dominate) とよぶ。このとき、特に両者が許容的な場合、h2 を用いた探索はより効率的だろうと考えられている。しかし、いくつかのコーナーケースではこのことは成り立たない<ref>Robert C. Holte. Common Misconceptions Concerning Heuristic Search, SoCS 2010</ref>。

このアルゴリズムは[[CPU]]の使用率、[[主記憶装置|メモリ]]の使用率など、計算負荷は高いが、問題に応じた適切なヒューリスティック関数を用いることにより、問題に対しての最適化が可能である。

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

同じ状態が2度出現した場合に1つのノードにまとめると AND/OR グラフになる。[[閉路]]のない AND/OR グラフに対する A<sup>*</sup> アルゴリズムに対応する物が[[1968年]]に開発され<ref>{{Cite journal |author=Nils J. Nilsson |title=Searching problem-solving and game-playing trees for minimal cost solutions |journal=Information Processing 68 : proceedings of IFIP Congress 1968 |pages=1556-1562 |volume=2 |year=1968 |month=August |publisher=Amsterdam : North-Holland }}</ref>、[[1980年]]に '''AO<sup>*</sup>アルゴリズム''' と命名された<ref name="nillson1980">{{Cite book  |和書 |date=1983-01-15 |origdate=1980 |title=人工知能の原理 |publisher=日本コンピュータ協会 |translator=白井良明, 辻井潤一, 佐藤泰介 |author=Nils J. Nilsson |isbn=4-88917-026-X }}</ref>。閉路のある AND/OR グラフに対する A<sup>*</sup> アルゴリズムに対応する '''A<sub>0</sub>アルゴリズム''' は[[1976年]]に開発された<ref>{{Cite journal |author=Giorgio Levi |author2=Franco Sirovich |title=Generalized and/or graphs |url=http://www.sciencedirect.com/science/article/pii/0004370276900060 |journal=Artificial Intelligence |volume=7 |issue=3 |pages=243-259 |doi=10.1016/0004-3702(76)90006-0 |year=1976 |month=January }}</ref>。AND ノードのコストを「辺のコスト＋部分問題のコストの最大値」や「辺のコスト＋部分問題のコストの総和」などの単調非減少関数で定義すると<ref>{{Cite journal |author=Vipin Kumar |author2=Dana S. Nau |author3=Laveen N. Kanal |title=A General Paradigm for AND/OR Graph and Game Tree Search |url=http://www.cs.utexas.edu/ftp/AI-Lab/tech-reports/UT-AI-TR-85-9.pdf |year=1985 |month=August }}</ref>、ヒューリスティック関数が許容的であれば、A<sup>*</sup> 同様、最適解が求まる。なお、閉路のない AND/OR グラフは[[文脈自由文法]]（タイプ-2 文法）<ref>{{Cite journal |author=Patrick A. V. Hall |title=Equivalence between AND/OR graphs and context-free grammars |url=http://dl.acm.org/citation.cfm?id=362302 |year=1973 |month=July |journal=Communications of the ACM |volume=16 |issue=7 |pages=444-445 |doi=10.1145/362280.362302 }}</ref>、閉路のある AND/OR グラフは制限のない文法（タイプ-0 文法）に1対1対応することが証明されている。

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

== 関連項目 ==
* [[最良優先探索]]
* [[ダイクストラ法]]
* [[均一コスト探索]]
* [[双方向探索]]
* [[シェーキー]]

{{アルゴリズム}}

[[Category:検索アルゴリズム]]
[[Category:アルゴリズム]]
[[Category:ゲーム人工知能]]
[[Category:数学に関する記事]]