A*探索アルゴリズムにはコストという概念があります。「コストの小さい経路」＝「体力の消耗度が小さい経路」とします。つまり、コストの一番小さな経路が最短経路となるわけです。コストはfという記号で表します。

---

例えば今、スタート地点からゴール地点までの最短経路があるとします。そして、その最短経路上にあるnという地点にいるとします。このとき、最短経路は当然ながら「スタート地点から地点nまでの最短経路」＋「地点nからゴール地点までの最短経路」です。スタート地点から地点nまでの最短経路のコストをg(n)、地点nからゴール地点までの最短経路のコストをh(n)と表すと、地点nを通る最短経路のコストf(n)は次のように表現できます。

f(n) = g(n) + h(n)

今回はもともと最短経路を知っていましたので、スタート地点から地点nまでの最短経路コストg(n)、地点nからゴール地点までの最短経路コストh(n)のどちらも分かっていました。よって、地点nを通る経路の最小コストはf(n)ということが計算できました。

---

しかし、全く初めての迷路で、ある地点nにぽんと置かれた場合、スタート地点から地点nまでの最短経路コストg(n)、地点nからゴール地点までの最短経路コストh(n)、どちらとも知っているはずがありません。しかしながら、これらの値が分からないとf(n)が計算できず、他の経路とコストを比較することができない、つまり、最短経路を求めることができなくなってしまいます。

これは困ります。したがって、勘でも何でもよいので、とりあえずコストを与えてみることにします。「スタート地点から地点nまでの推定最短経路コスト」、「地点nからゴール地点までの推定最短経路コスト」を「推定」という意味を込めた*付きのg*(n)、h*(n)で表します。すると、地点nを通る、ある最短経路の推定コストf*(n)は、次のように表現できます。

f*(n) = g*(n) + h*(n)　…(※)

ここで、実はg*(n)の値は分かります。というのは、迷路はスタート地点から移動を始めるので、スタート地点から出発して地点nに来たとすると、地点nまでの最短距離は探索しているうちに分かってくるためです。一方、h*(n)の値はこれから進む道であるので最後まで分かりません（分かっていたら探索する必要がない）。

このように、その時点で知っているg(n)とテキトーなh*(n)をもとにf*(n)を計算し、その値が一番小さくなる経路を選んでいくことで、最短経路を求めることができます。このアルゴリズムをA探索アルゴリズムといいます。

---

しかしながら、h*があまりにもテキトーな値を返すとf*もテキトーになってしまい、f*の値を比較しながら進んでいく手法が崩壊してしまいます（「h*がテキトー」→「コストfもテキトー」→「コストが低いと思って選択した道が、実は低くなかった」→「いろいろな道を無駄に歩き回ってなかなかゴールにたどり着かない」）。

そこで、h*をもっともらしい値を返す関数にすることを考えます。この、もっともらしい推定値を与えてくれるh*はヒューリスティック関数と呼ばれます。今、h*(n)を「0以上」かつ「地点nからゴールまでの実際の最短経路コスト以下」の範囲の値とします。これは以下のように表すことができます。

（どのようなnにおいても）, 0 ≦ h*(n) ≦ h(n)

このようなh*を採用したときに求まる経路は、最短経路であることが保証されています。もっともらしいf*(n)を求め、そのf*(n)の値が一番小さくなる経路を選んで探索を進めるわけです。このようにして最短経路を求めるアルゴリズムをA*探索アルゴリズムといいます。

---

A*探索アルゴリズムでは、地点nからゴール地点までの推定最短経路コストを、本当の最短経路コスト以下に見積もって代入することがポイントです。あらかじめ迷路データが与えられる場合などは、地点nからゴール地点までの直線距離をh*(n)とすることが多いようです。これによって、なるべくゴールに近付く方向から探索するようになります。また、スタート地点から現在地までの経路コストはその都度修正します。探索の途中では、行き止まりになったり、推定コストが高くなる方向にしか進めない場面に遭遇する場合もあります。そのときは、次に小さい推定コストをもつ経路を選択し、探索を続けます。

---

このようにして最終的にゴール地点（G）に到着します。このとき式(※)は次のようになります。

f*(G) = g(G) + 0　→　f(G) = g(G)

「スタート地点から探索してきた最短経路コストg(G)」は確実な値であるので、「スタート地点からゴール地点までの最短経路コストf(G)」も確実な値となるわけです。

結果、一番小さい経路コストg(G)をもつ「経路」が「スタート地点からゴール地点までの最短経路」となる、つまり、最短経路が求められたことになります。