|
A *（A-star, エースター）探索アルゴリズムは、グラフ探索アルゴリズムの一つ。 最良優先探索を拡張したZ *に、さらにf値として「現時点までの距離」gと「ゴールまでの推定値」hの和を採用したもの。〔Pearl,Judea. "Heuristics: intelligent search strategies for computer problem solving." (1984).〕 h は ヒューリスティック関数と呼ばれる。 == 概要 == A * アルゴリズムは、「グラフ上でスタートからゴールまでの道を見つける」というグラフ探索問題において、 ヒューリスティック関数 ''h(n)'' という探索の道標となる関数を用いて探索を行うアルゴリズムである。hは各頂点nからゴールまでの距離のある妥当な推定値を返す関数で、解くグラフ探索問題の種類に応じてさまざまなhを設計することが出来る。 例えば、カーナビなどで用いられる単純な二次元の地図での探索では、hとしてユークリッド距離 を使うことができ、この値は道に沿った実際の距離のおおまかな予測になっている。しかし、高次元空間でのグラフ探索を効率的に行うためには、より高度に設計された関数を用いる必要がある。例えば、15パズルにおいてはマンハッタン距離やパターンデータベース、STRIPSプランニングにおいてはFFヒューリスティック〔Hoffmann, Jörg, and Bernhard Nebel. "The FF planning system: Fast plan generation through heuristic search." Journal of Artificial Intelligence Research (2001): 253-302.〕,Merge-and-Shrink〔Hoffmann, Jörg, and Bernhard Nebel. "The FF planning system: Fast plan generation through heuristic search." Journal of Artificial Intelligence Research (2001): 253-302.〕,Landmark-Cut〔Helmert, Malte, and Carmel Domshlak. "Landmarks, critical paths and abstractions: what's the difference anyway?." ICAPS. 2009.〕 などがある。 A * アルゴリズムは、ダイクストラ法を推定値つきの場合に一般化したもので、h が恒等的に0である場合はもとのダイクストラ法に一致する。 A *の探索効率はhの正確さに左右される。 もしもhがまったくでたらめな値を返すならば、探索はゴールとはあさっての方向に進んでしまい、現実的な時間内 --- 一時間、一週間、一年 --- では解を発見できない場合がある。しかし、いくらおかしな方向に探索が進んだとしても、いつかは必ず解を発見できる保証がある(完全性)。 一方、hが常に正しい値''h *''を返す場合、計算機は「迷うこと無く=分岐をすること無く」グラフ上の最短経路を発見することができる。そのようなhのことを、パーフェクト・ヒューリスティクスとよぶ〔How Good is Almost Perfect?. M Helmert, G Röger - AAAI, 2008〕。 現実に用いられる有用なhは、これらの中間の位置にある。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「A*」の詳細全文を読む スポンサード リンク
|