A* 探索アルゴリズム
A*は、コンピュータが2つの場所の間を高速で移動する方法を見つけ出すために使用できる一連の手順（アルゴリズム）です。場所のリストがあり、1つの場所からもう1つの場所にまっすぐ行くのがどれだけ難しいか、A*を使えば、最も速い方法をすぐに知ることができます。これは、ダイクストラのアルゴリズムに関連していますが、賢い推測を行うので、遅い方法を試すのにそれほど長い時間を費やすことはありません。2つの場所の間の経路を求めるだけなら、これは良いステップの連続です。もし、同じ地図から多くの経路を求めるのであれば、フロイド・ウォーシャル・アルゴリズムのように、一度にすべての答えを見つける、より高速な方法がある。A*は、一回の旅行で複数の場所を訪れたい場合（巡回セールスマン問題）には使えません。
ステップ
A*はまず、あなたが行くことができるすべての場所のリストを必要とし、次にそれぞれの場所間の道のりのリストを必要とします。そして、A地点からZ地点に行くのに一番速い方法を教えてくれます。
AからZに行くには、A-B-D-Z, A-C-D-Z, A-B-E-Z, A-C-E-Zの4通りの行き方があります。A*を使うコンピュータは、まずAからB、AからCに行くのがどれだけ大変かを調べます。これは、それらの場所の「コスト」です。ある場所のコストとは、Aからその場所に行くのがどれだけ大変かということである。両方のコストを書き出した後、コンピュータはBからDに行くのがどれだけ大変かを調べ、Bのコストにこれを加える。これをDの費用として書き留めます。次にコンピュータは、CからDに行くのがどれだけ大変かを調べ、Cの費用にこれを加えます。これはDの別のコストであり、もしそれがすでに持っているコストより低ければ、古いものを交換することになります。コンピュータは最適な経路を知りたいだけなので、コストの高い経路は無視する。A-B-DとA-C-Dのどちらか速い方だけを記憶する。
最後に，D から Z まで行って費用を求め，E から Z まで行って費用を求めます．そして、最終的にZにかかる費用を求めますが、これが最も小さい費用です。これでコンピュータは、どの道が一番速いかを知り、答えを得たことになります。コンピュータは、同じような一連のステップを、もっと多くの場所で行うことができます。その都度、A に最も近い場所を探し、その場所の近隣にかかる費用を足し算します。
人は、上記の一連のステップをダイクストラアルゴリズムと呼びます。ダイクストラのアルゴリズムは、Zから間違った方向に行くかもしれない多くの場所を調べるので、遅くなることがあります。ある都市から近くの都市に行く方法をコンピュータに尋ねた場合、ダイクストラのアルゴリズムは別の州を調べることになるかもしれません。
この問題を解決するのがA*です。A*は、各場所から端までの距離をコンピュータに推測させるものである。コンピュータはその推測をもとに、ある場所からZまでの距離をおおまかに知ることができるのです。この総計は、残り距離の予想値にコストを足すことで求められる。こうすることで、より良くなりそうな方向だけを見ることができる。推測が完璧でなくても構わないが、単純に悪い推測でも、プログラムはかなり速く進む。現実の世界で2つの場所の間の道を見つけようとする場合、良い推測はちょうど直線でその間の距離です。道路を越える本当の道はもっと長くなりますが、これならプログラムが推測してくれるので、間違った方向には進みません。
数学やコンピュータサイエンスの文献では、この推測は場所の関数であることが多く、ヒューリスティックと呼ばれる。各場所が頂点で、2つの場所間の各経路が辺である。これはグラフ理論の言葉である。
