Aアルゴリズム

ウィキペディア

A*

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/14 07:07 UTC 版)

探索 > 最良優先探索 > A*

A*探索アルゴリズム

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

概要

A* アルゴリズムは、「グラフ上でスタートからゴールまでの道を見つける」というグラフ探索問題において、ヒューリスティック関数 h(n) という探索の道標となる関数を用いて探索を行うアルゴリズムである。h は各頂点 n からゴールまでの距離のある妥当な推定値を返す関数で、解くグラフ探索問題の種類に応じてさまざまな h を設計することが出来る。例えば、カーナビなどで用いられる単純な二次元の地図での探索では、h としてユークリッド距離 ${\sqrt {x^{2}+y^{2}}}$