
No.
4-6
A*
(「 エー・スター」と読みます)は、グラフの最短路問題を解くアルゴリズムで、ダイクスト
ラ法を発展させたものです。ダイクストラ法では、始点から各頂点までの最短路を順番に決定し
ていくときに、始点に近い頂点から順に決定していました。したがって、終点から遠ざかる方向
の頂点の最短路も決定していきますが、これは結局使われないのでムダになります。
A*
は、あら
かじめ推定コストをヒントとして設定し、その情報を利用することで、ムダな探索を省くように
改良したものです。
S
G
G
S
ののはダイクストラ法
いて
はマスとの間の
コスト
1
のグラフと
S
G
のとにダイクストラ法めて
01 02
03
「
S
」スタート
「
G
」ゴール