A*

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

A*(A-star, エースター)探索アルゴリズムは、探索アルゴリズムの一つ。

スタートノードからゴールノードまでのパスを計算する、このとき求めるパスが最短であることを保証しているアルゴリズムである。

概要[編集]

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

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

A* アルゴリズムは1968年Peter E. HartNils J. NilssonBertram Raphael の三人が発表した論文[1]の中で最初に記述された。A* というこの一風変わった名前は、この論文でスタートからゴールまでの最短経路を確実に見つけるアルゴリズムを許容的 (Admissible) と呼び、論文の数式中に 許容的なアルゴリズムの集合A と表し、そのAの中でも評価回数が最適になる物を A* と表記していたためである[2]

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 \le h^*(n) \le h(n)

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

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

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

ただし

\forall n,h_1^*(n) < h_2^*(n) \le h(n)

というヒューリスティック関数が存在する場合は h1* を用いるより h2* を用いるほうが計算負荷は少なくてすむ。このため、そのようなヒューリスティックの存在がわかっている場合は 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) + COST(n,m) を計算する、ここで 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年に開発され[3]1980年AO*アルゴリズム と命名された[2]。閉路のある AND/OR グラフに対する A* アルゴリズムに対応する A0アルゴリズム1976年に開発された[4]。AND ノードのコストを「辺のコスト+部分問題のコストの最大値」や「辺のコスト+部分問題のコストの総和」などの単調非減少関数で定義すると[5]、ヒューリスティック関数が許容的であれば、A* 同様、最適解が求まる。なお、閉路のない AND/OR グラフは文脈自由文法(タイプ-2 文法)[6]、閉路のある AND/OR グラフは制限のない文法(タイプ-0 文法)に1対1対応することが証明されている。

関連項目[編集]

参照[編集]

  1. ^ Peter E. Hart; Nils J. Nilsson; Bertram Raphael (July 1968). “A Formal Basis for the Heuristic Determination of Minimal Cost Paths”. IEEE Transactions on Systems Science and Cybernetics 4 (2): 100-107. doi:10.1109/TSSC.1968.300136. ISSN 0536-1567. http://ai.stanford.edu/~nilsson/OnlinePubs-Nils/PublishedPapers/astar.pdf. 
  2. ^ a b Nils J. Nilsson 『人工知能の原理』 白井良明, 辻井潤一, 佐藤泰介訳、日本コンピュータ協会、1983年1月15日(原著1980年)。ISBN 4-88917-026-X
  3. ^ 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. 
  4. ^ Giorgio Levi; Franco Sirovich (January 1976). “Generalized and/or graphs”. Artificial Intelligence 7 (3): 243-259. doi:10.1016/0004-3702(76)90006-0. http://www.sciencedirect.com/science/article/pii/0004370276900060. 
  5. ^ Vipin Kumar; Dana S. Nau; Laveen N. Kanal (August 1985). A General Paradigm for AND/OR Graph and Game Tree Search. http://www.cs.utexas.edu/ftp/AI-Lab/tech-reports/UT-AI-TR-85-9.pdf. 
  6. ^ Patrick A. V. Hall (July 1973). “Equivalence between AND/OR graphs and context-free grammars”. Communications of the ACM 16 (7): 444-445. doi:10.1145/362280.362302. http://dl.acm.org/citation.cfm?id=362302.