A*

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索
A*探索アルゴリズム

A*(A-star, エースター)探索アルゴリズムは、グラフ探索アルゴリズムの一つ。 最良優先探索を拡張したZ*に、さらにf値として「現時点までの距離」gと「ゴールまでの推定値」hの和を採用したもの。[1] h は ヒューリスティック関数と呼ばれる。

概要[編集]

A* アルゴリズムは、「グラフ上でスタートからゴールまでの道を見つける」というグラフ探索問題において、 ヒューリスティック関数 h(n) という探索の道標となる関数を用いて探索を行うアルゴリズムである。hは各頂点nからゴールまでの距離のある妥当な推定値を返す関数で、解くグラフ探索問題の種類に応じてさまざまなhを設計することが出来る。 例えば、カーナビなどで用いられる単純な二次元の地図での探索では、hとしてユークリッド距離 を使うことができ、この値は道に沿った実際の距離のおおまかな予測になっている。しかし、高次元空間でのグラフ探索を効率的に行うためには、より高度に設計された関数を用いる必要がある。例えば、15パズルにおいてはマンハッタン距離パターンデータベースSTRIPSプランニングにおいてはFFヒューリスティック[2],Merge-and-Shrink[3],Landmark-Cut[4] などがある。

A* アルゴリズムは、ダイクストラ法を推定値つきの場合に一般化したもので、h が恒等的に0である場合はもとのダイクストラ法に一致する。

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

歴史[編集]

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

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) に置き換えることを考える。

ここで g(n) はスタートノードから n までの最小コストの推定値、h(n)n からゴールノードまでの最小コストの推定値である。この場合 g に関しては探索の過程で更新を加えることによりg*に近づけてゆくことができるが、 h* は、実際にゴールに辿り着くまでは誰にもわからない。そこで、 h(n) には人間が(ある程度妥当性を持つように)設計した推定値を与えることにする。このアルゴリズムを A*探索アルゴリズムといい、 h (n)ヒューリスティック関数という。

アルゴリズムの流れ[編集]

A* のアルゴリズムの実装を以下に示す。

  1. スタートノード( )を作成する。また計算中のノードを格納しておくための優先度つきキュー OPENリストと、計算済みのノードを格納しておくCLOSEリストを用意する。(名前は「リスト」だが、これらの実際のデータ構造は必ずしも連結リストである必要はない。)
  2. ゴールは必ずしも1つである必要はないので、ゴール条件を満たすノード集合を と呼ぶことにする。
  3. スタートノードをOpenリストに追加する、このとき = であり = となる。また Closeリストは空にする。
  4. Openリストが空なら探索は失敗とする(スタートからゴールにたどり着くような経路が存在しなかったことになる)。
  5. Openリストに格納されているノードの内、最小の を持つノード を1つ取り出す。同じを持つノードが複数ある場合、タイブレーク手法によりどれかのノードを選択する。
  6. であるなら探索を終了する。それ以外の場合は を Close リストに移す。
  7. に隣接している全てのノード(ここでは隣接ノードを とおく)に対して以下の操作を行う
    1. を計算する、ここで はノード n から m へ移動するときのコストである。また g(n) は で求めることができる。
    2. m の状態に応じて以下の操作を行う
      • m が Openリストにも Closeリストにも含まれていない場合 とし m を Openリストに追加する。このとき m の親を n として記録する。
      • m が Openリストにある場合、 であるなら に置き換える。このとき記録してある m の親を n に置き換える。
      • m が Closeリストにある場合、 であるなら として m を Openリストに移動する。また記録してある m の親を n に置き換える。
  8. 3 以降を繰り返す。
  9. 探索終了後、発見されたゴール から親を順次たどっていくと S から ゴール までの最短経路が得られる。

以上の流れを見れば、アルゴリズムが手続き的で、並列化が非常に難しいことがわかる。しかし、近年では HDA*[8], PBFS などの並列手法が開発され、特にHDA*は768コア以上の大規模並列計算環境にもスケールすることが実証されている。

性質[編集]

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

  • A*はダイクストラの一般化であり、ダイクストラと同様、グラフに負のコストの辺があれば完全性を失う。その場合にはベルマン–フォード法を用いる。
  • h(n) は常に非負でなくてはならない。
  • あるヒューリスティクス h(n) が 全てのノード n について 真のゴール距離 h*(n) を上回らない場合、hはAdmissible/許容的であると言う。

このとき、A*の返す経路は最適、つまり最短経路である。

  • あるヒューリスティクス h(n) について、全てのノード n と、それに隣接しているノード m について である場合、そのhはconsistent/無矛盾であるという。
  • consistent なhは、常にadmisibleである。[9]
  • ある2つのヒューリスティック関数 h1, h2 について、 が成り立つ時、 h2 は h1 を支配する(dominate)とよぶ。このとき、特に両者が許容的な場合、h2 を用いた探索はより効率的だろうと考えられている。しかし、いくつかのコーナーケースではこのことは成り立たない。[10]

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

部分問題に分割する場合[編集]

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

同じ状態が2度出現した場合に1つのノードにまとめると AND/OR グラフになる。閉路のない AND/OR グラフに対する A* アルゴリズムに対応する物が1968年に開発され[11]1980年AO*アルゴリズム と命名された[7]。閉路のある AND/OR グラフに対する A* アルゴリズムに対応する A0アルゴリズム1976年に開発された[12]。AND ノードのコストを「辺のコスト+部分問題のコストの最大値」や「辺のコスト+部分問題のコストの総和」などの単調非減少関数で定義すると[13]、ヒューリスティック関数が許容的であれば、A* 同様、最適解が求まる。なお、閉路のない AND/OR グラフは文脈自由文法(タイプ-2 文法)[14]、閉路のある AND/OR グラフは制限のない文法(タイプ-0 文法)に1対1対応することが証明されている。

関連項目[編集]

参照[編集]

  1. ^ Pearl,Judea. "Heuristics: intelligent search strategies for computer problem solving." (1984).
  2. ^ Hoffmann, Jörg, and Bernhard Nebel. "The FF planning system: Fast plan generation through heuristic search." Journal of Artificial Intelligence Research (2001): 253-302.
  3. ^ Hoffmann, Jörg, and Bernhard Nebel. "The FF planning system: Fast plan generation through heuristic search." Journal of Artificial Intelligence Research (2001): 253-302.
  4. ^ Helmert, Malte, and Carmel Domshlak. "Landmarks, critical paths and abstractions: what's the difference anyway?." ICAPS. 2009.
  5. ^ How Good is Almost Perfect?. M Helmert, G Röger - AAAI, 2008
  6. ^ 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. 
  7. ^ a b Nils J. Nilsson 『人工知能の原理』 白井良明, 辻井潤一, 佐藤泰介訳、日本コンピュータ協会、1983年1月15日(原著1980年)。ISBN 4-88917-026-X
  8. ^ Kishimoto, Akihiro, Alex S. Fukunaga, and Adi Botea. "Scalable, Parallel Best-First Search for Optimal Sequential Planning." ICAPS. 2009.
  9. ^ Russel, Norvig, Artificial intelligence: a modern approach
  10. ^ Robert C. Holte. Common Misconceptions Concerning Heuristic Search, SoCS 2010
  11. ^ 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. 
  12. ^ 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. 
  13. ^ 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. 
  14. ^ 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.