A*探索(えーすたーたんさく)とは

A*探索とは、スタートからゴールまでの最短経路を、効率よく見つけ出す探索アルゴリズムです。エースターと読みます。カーナビが目的地までの近い道を案内したり、ゲームのキャラクターが障害物をよけて進んだりするときに使われる、経路探索の定番です。1968年に考案された古典的な手法です。

「当て推量」で近道を見つける仕組み

A*探索の賢さは、二つの値を足して進む点にあります。「ここまで実際にかかった距離」と「ゴールまでのおおよその残り距離（当て推量）」を足し、その合計が小さい地点から優先して調べていく仕組みです。やみくもに全方向を探すのではなく、ゴールに近づきそうな方向を優先するので速く済みます。ここでいう当て推量は、いいかげんな推測ではありません。残り距離を控えめに見積もりさえすれば、必ず本当の最短経路にたどり着けることが数学的に保証されているのが、この手法の美点です。

いまも現役の定番アルゴリズム

A*探索は、スタンフォード研究所のピーター・ハートらが1968年に発表しました。ChatGPTのような生成AIが登場するはるか前に生まれた手法ですが、地図アプリの経路案内、ゲームのキャラ移動、ロボットの経路計画など、いまも幅広く使われています。生成AIとはまったく別系統の、地道で実用的なAIの基礎技術といえます。

A*探索に関するよくある質問

A*探索は何に使われていますか？

スタートからゴールまでの最短経路を効率よく見つける探索アルゴリズムで、カーナビの経路案内、ゲームのキャラ移動、ロボットの経路計画などに今も幅広く使われています。1968年に考案された古典的な手法です。

A*探索はなぜ速いのですか？

「ここまで実際にかかった距離」と「ゴールまでのおおよその残り距離(当て推量)」を足し、その合計が小さい地点から優先して調べるためです。残り距離を控えめに見積もれば、必ず最短経路にたどり着けることが数学的に保証されています。

A*探索は生成AIと同じ技術ですか？

別系統です。ChatGPTのような生成AIが登場するはるか前の1968年に生まれた、地道で実用的なAIの基礎技術で、もともとは世界初の汎用移動ロボット「シェイキー」のために作られました。