A*
A* アルゴリズムは1968年に Peter E. Hart、Nils J. Nilsson、Bertram Raphael の三人が発表した論文の中で最初に記述された。A* というこの一風変わった名前は、この論文でスタートからゴールまでの最短経路を確実に見つけるアルゴリズムを許容的(英: admissible)と呼び、論文の数式中に 許容的なアルゴリズムの集合を 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 ) {\displaystyle f(n)=g(n)+h(n)}
ここで g(n) はスタートノードから n までの最小コストの推定値、h(n) は n からゴールノードまでの最小コストの推定値である。この場合 g に関しては探索の過程で更新を加えることにより g* に近づけてゆくことができるが、h* は、実際にゴールに辿り着くまでは誰にもわからない。そこで、h(n) には人間が(ある程度妥当性を持つように)設計した推定値を与えることにする。このアルゴリズムを A*探索アルゴリズムといい、h (n) をヒューリスティック関数という。
A* のアルゴリズムの実装を以下に示す。この OPENリスト実装は後に述べるように遅いことを記しておく。
スタートノード( S {\displaystyle S} )を作成する。また計算中のノードを格納しておくための優先度付きキュー OPENリストと、計算済みのノードを格納しておくCLOSEリストを用意する。(名前は「リスト」だが、これらの実際のデータ構造は必ずしも連結リストである必要はない。)
ゴールは必ずしも1つである必要はないので、ゴール条件を満たすノード集合を G {\displaystyle G} と呼ぶことにする。
スタートノードを Openリストに追加する、このとき g ( S ) {\displaystyle g(S)} = 0 {\displaystyle 0} であり f ( S ) {\displaystyle f(S)} = h ( S ) {\displaystyle h(S)} となる。また Closeリストは空にする。
Openリストが空なら探索は失敗とする(スタートからゴールにたどり着くような経路が存在しなかったことになる)。
Openリストに格納されているノードの内、最小の f ( n ) {\displaystyle f(n)} を持つノード n {\displaystyle n} を1つ取り出す。同じ f ( n ) {\displaystyle f(n)} を持つノードが複数ある場合、タイブレーク手法によりどれかのノードを選択する。