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

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

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

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

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

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

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

いまの地図アプリは、A*探索をそのまま使っているのですか？

そのままではありません。経路探索の専門家による2015年の総説は「道路網では、地理的な直線距離を手がかりにするA*は、現代の他の手法と比べて振るわない」と述べています。実際の経路検索は、地図をあらかじめ計算し直しておく前処理と組み合わせることで、大陸規模でもミリ秒以下で答えを返します。A*は考え方の土台として生き続けている、と捉えるのが実態に近いでしょう。

A*探索をもっと速くする方法はありますか？

あります。ただし引き換えがあります。同じ総説は、残りの距離をより強気に見積もれば処理は速くなるものの「正しさはもはや保証されない」と明記しています。「必ず最短」と「速さ」は取引の関係にあり、実務ではどちらを優先するかを決めることになります。多少の遠回りより待ち時間の短さを取る、という判断もあり得るわけです。

電車の乗り換え検索も同じ仕組みですか？

見た目は似ていますが、別物と考えたほうがよいでしょう。同じ総説は、公共交通の経路検索を、時刻に左右されることと複数の基準を同時に扱うことから「本質的にはるかに難しい問題」だとしています。道路なら距離や所要時間の短い順で決まりますが、電車は発車時刻に縛られ、所要時間・乗換回数・運賃のどれを重んじるかで答えが変わるためです。