A*
n ∈ G {\displaystyle n\in G} であるなら探索を終了する。それ以外の場合は n {\displaystyle n} を Close リストに移す。
n {\displaystyle n} に隣接している全てのノード(ここでは隣接ノードを m {\displaystyle m} とおく)に対して以下の操作を行う f ′ ( m ) = g ( n ) + C O S T ( n , m ) + h ( m ) {\displaystyle f'(m)=g(n)+COST(n,m)+h(m)} を計算する、ここで C O S T ( n , m ) {\displaystyle COST(n,m)} はノード n から m へ移動するときのコストである。また g ( n ) {\displaystyle g(n)} は g ( n ) = f ( n ) − h ( n ) {\displaystyle g(n)=f(n)-h(n)} で求めることができる。 m の状態に応じて以下の操作を行う m が Openリストにも Closeリストにも含まれていない場合 f ( m ) ← f ′ ( m ) {\displaystyle f(m)\leftarrow f'(m)} とし m を Openリストに追加する。このとき m の親を n として記録する。