日本大百科全書(ニッポニカ) 「A*アルゴリズム」の意味・わかりやすい解説
A*アルゴリズム
えーすたーあるごりずむ
グラフ上の最短経路を探すアルゴリズムの一つ。たとえば、カーナビゲーションや乗換案内の経路探索などでは、全解探索をすれば最短距離はみつかるが、計算量が膨大になることが多いので、効率的に計算することが求められる。さらに、探索結果が最短距離であることを保証する必要がある。
古典的には構造化プログラミングの提唱者ダイクストラEdsger Dijkstra（1930―2002）が考案したダイクストラ法があるが、A*はその改良版といえる。ノードnからゴールまでの距離の見積りとしてh(n)というヒューリスティックな関数を用いて、探索を効率化する。たとえばカーナビゲーションの場合には、地点nとゴールの間の直線距離（ユークリッド距離）などに使える。ヒューリスティック関数の見積りが完全で、h(n)が経路の真の距離を与えてくれる場合は探索なしに解を求めることができ、逆になんの見積りもなく、h(n)がつねに0の場合は最悪でもダイクストラ法と同じになる。
［中島秀之 2019年7月19日］
[参照項目] | |