■

A*でOPENリストに入る評価コストの計算式 f( )=g( )+h( )
gはその地点までにかかった実際のコスト、hはヒューリスティックでゴールまでの見積もりコスト。
ダイクストラ法の場合h( )が0、探索が進むにつれてOPENリストに入っているfはほぼ単調に増加。よってOPENリストに入ったノードは近いうちに展開される。

対してA*ではh( )というゴールまでの見積もりコスト関数が入ってるのでダイクストラ法ほどにはf( )の値は変化しない。式を見てわかるとおり探索が進みゴールに近づくにつれてf( )の内、h( )の影響が小さくなってくるのがわかる。hは一般にunderestimate、よって探索が進むと、h( )の影響が小さくなり、同じくfは次第に増加する。