A*アルゴリズム入門！仕組みを分かりやすく解説
引用元：https://news.ycombinator.com/item?id=44296523
Aとかダイクストラ、BFSってさ、全部同じアルゴリズムなんだけど、優先キューの並び順が違うだけって考えると分かりやすいよ。BFSは発見順（キュー）、ダイクストラはここまでの距離＋次の距離、Aはそれに目標までの推定距離も加えるんだ。ダイクストラが推定距離0だから、A*の推定はそれより大きくちゃダメ、つまり過小評価じゃないとダメってわけ。
グラフ探索アルゴリズムってさ、未知のノード（白）、既知だけどまだ行ってないノード（灰）、行ったノード（黒）って３つのグループで考えられるんだけど、この”灰色のノード”をどう管理するかでアルゴリズムが決まるんだ。
DFSはキュー、BFSはスタック、ダイクストラは優先キューで辺の重さ、A*はヒューリスティックで並び替え。これ、他のアルゴリズムとかゴミコレクタにも応用できる考え方で面白いね。
A*で使うヒューリスティック関数ってさ、ちょっと特別な条件があるんだ。それは”admissible”って言って、本当の最短距離より大きく見積もっちゃダメなんだよ。
たとえ適切なヒューリスティックじゃなくても、記事に書いてある通りパスは見つかるんだ。ただ、そのパスが最短とは限らないってだけね。これ、結構普通にやられてることだよ。
この考え方、めっちゃ分かりやすくて良いね！使うわ、ありがとう。ちょっと細かいことだけど、DFSとBFS逆になってないかな？
幅優先探索はキューを使うよ。
深さ優先探索はスタック。
A*は優先キューだね。
正確には、ダイクストラが優先キューを使うんだ。
A*はダイクストラにプラスして、ゴールまでの推定値をコストに加えて、よりゴールに近いノードを優先的に探索するって感じかな。
コメント主が言ってるのはさ、BFSは優先キューでキーがh(n)=0, g(n)=辺の数、ダイクストラはh(n)=0, g(n)=辺の重みの合計、A*はh(n)=heuristic(n), g(n)=辺の重みの合計って考えられるってことだね。なるほど、面白い。
同じように、キューもさ、挿入するたびに増える数字をキーにした優先キューとして表現できるんだ。スタックならキーをマイナスにすればいい。これってdecorate-sort-undecorateパターンっていう考え方で、ヒープソートに違うキー関数を使うだけで色々なアルゴリズムになるってことなんだよ。
「元のコメント主の主張は、BFSはh(n)=0、g(n)=#edgesの優先度付きキューだってことだけど、彼はそんなこと言ってないし、それ違くない？」って指摘は違うと思うよ。彼はそんなこと言ってないし、それも正しくない。
理論計算機科学では「#xs」は「xsの数」って書くんだ。僕の文は「g(n) = number of edges」って読んで欲しかったんだよね。これは暗黙的に（BFSの話だから）今のノードnから見て、今までのエッジ数を意味してる。nは普通グラフのサイズだけど、Aでは（AI:MAみたいに）現在のノードを表すことが多いんだ。全部私の責任です。（免責事項：CS教授で、毎年BFSとDijkstra、2年おきにAを教えてます。）
それは正しいと思うな。ただ、「#edges」は「開始点からノードまでのパスにあるエッジの数」って理解する必要があるけどね。それ、僕が最初に考えた3つの解釈には入ってなかったんだ。
ヒューリスティックが過大か過小か覚えるのに、「Dijkstraは推定値を”0”にしてるんだから、明らかに「許容可能なヒューリスティック」の基準は過小評価じゃなきゃだめだ」って考えるのは、ちょっと考えすぎかな :-) 。10歳の子が地図を見るみたいにシンプルに考えようよ。直線距離（Euclidean distance）は、地図上の距離を推定する一番分かりやすいヒューリスティックで、これは許容可能だよね。直線距離は距離を最小にする、つまり決して過大評価しない。これだけで過小評価が必要だって思い出せる十分なヒントになるよ。「競プロやってた時に、Aを「実用的で覚えやすい」視点から考えたのは、全部同じアルゴリズムで、優先度キューの優先度が違うだけってことだ」っていうのは、分かりやすいけど、Aをもっと魅力的（と個人的には思う）に捉える別の方法は、実はDijkstraを改造したグラフでやってるって考えることなんだ。各エッジの頂点間のヒューリスティックの差分をエッジの重みに調整する感じ。この方法で調整の符号を覚えるには、次の頂点が目的地にすごく近くなった状況を想像して、その場合重みを大きくする必要があるか小さくする必要があるかを考えよう。（目的地に近づいてるんだから、小さくする必要があるね。）
どのアルゴリズムを使えばいいか：
エージェントが決定を下す必要がある（左か右か）という情報しかない場合：
- DFSまたはBFS
決定のコストについて少し情報がある場合：
- UCSまたはDijkstra’s algorithm
決定のコストのアイデアがあり、目標がだいたいどの方向にあるか rough ideaがある場合：
- A star
コストを知っているだけでなく、大まかな方向も知っていて、さらにuniform cost grid（均一コストグリッド）であることを知っている場合：
- Jump point search
たぶん、過小評価/過大評価を覚える一番簡単な方法は、Euclidean distanceがすごく一般的な admissible heuristicだってことだけ覚えておくことだと思う。
LeetCodeは若いプログラマーを競プロや面接みたいな競技的なことのために鍛えてくれるよ。
Codeforcesの方が断然良いよ。コミュニティも良いし、問題も良い。
あと、Depth First Searchはただのスタックだよ！
うん、でもすぐにはそうならないんだ。一時的に深いノードを優先するとループしない深さ優先探索（Depth-first traversal）になって、グラフがTreeの場合は簡略化されて通常のスタックベースの深さ優先探索になるんだ。最初のゴールに落ち着くと、末尾再帰最適化されたDFSが得られるって感じ。
Red Blob Gamesはゲーム開発に興味がある人には最高のブログだよ。解説が分かりやすいし、ほとんどの記事に疑似コードか実装例があって、大きな記事には直感的な理解を助ける素晴らしいアニメーションがたくさんあるんだ。
Advent of Codeの課題で六角形グリッドのパズルがあったのを覚えてるんだけど、Red Blob Gamesの六角形グリッドガイドがすごく良くて、一時的にサイトが落ちたことがあったな。後でCivilizationクローンを作った時にも使ったし、本当に素晴らしいリソースだよ。https://www.redblobgames.com/grids/hexagons/
10年経った今でも覚えてる、あのブログ記事のグラフィックが平面から尖った形に変わるだけでなく、コードもアニメーションするのを見た時の、あの小さな喜び。インタラクティブなグラフィックは、子供の頃に科学博物館にいた時のような楽しさを全部思い出させてくれるんだ。
僕も同じことを言いに来たよ。Red Blob Gamesはgamedevを始めたい人にとって、まさに宝の山だよ。
Aには深い愛情があるんだ。初めて完全に理解できた複雑なアルゴリズムだからね。大学でデータ構造とアルゴリズムの最初の授業（2000年代初頭）で、研究してコードを書いて論文を書くアルゴリズムを選ぶ課題があって、Aを選んだんだ。
この記事の作者がやったみたいに、何時間もかけて手書きで同じようなグリッドを描いて、手作業で計算したよ[0]。20年以上経った今でも、どこかにこれらのノートを持ってるんだ。自分がそれにかけた労力をすごく誇りに思ってたから。
とにかく、この記事と、昔を思い出させてくれてありがとう。[0] https://imgur.com/a/zRYaodL (Imgurリンクでごめんね)
A*が昔「AI」って呼ばれてたの面白いね。今の「AI」ってGenAIとかDLのことで、昔の「AI」より狭い意味になってるじゃん？DLはMLの一部で、MLは昔のAIの一部、その中にGenAIがあるって関係？じゃあ、AI全体の分野って今なんて呼べばいいんだろ？って考えてるとこ。
↑のコメントだけど、ゲームのAIって昔からいろいろあったよ。NPCがプレイヤー見て攻撃したり逃げたりするコード全部「ゲームのAI」って呼ばれてたんだ。簡単なルールだけでもね。「AI」って他の分野よりゲームでは意味が軽かったけど、全体的に「AI」って言葉が使われるようになって変わってきたね。
ゲームAIだけじゃなくて、大学の「Artificial Intelligence」の授業でもA*とかformal logic、planning、knowledge representationとか教えてたんだよ。Russell-Norvigの有名な教科書とかね。Deep learningが流行ってからは、ああいう昔のAIはGOFAI、つまり”Good Old-Fashioned AI”ってちょっと皮肉っぽく呼ばれてるね。
僕はRussellとNorvigの最初の教科書でAIの授業を受けた世代だよ。今の「AI」の95%くらいを占めるNeural networksは、当時は1章だけで、そんなに詳しくなかったんだ。僕も年取ったな。
RussellとNorvigのあの最高の教科書、最新版は「Artificial Intelligence：An Outdated Approach」ってタイトルにしないとかな？あの本めちゃくちゃ好きだから、LLMに「AI」って名前つけるの聞くと、なんかちょっとゾッとするんだよね。
もちろん、ゲームにもっとすごいAIもあるよ。ChessのDeep Blueとか、GoでLee Sedolに勝ったDeepMindとか覚えてる？ああいうClassic gamesは、今のVideo gamesよりAIの研究者たちに注目されてるんだ。
もっとコメントを表示（1）
OpenAIがDota 2でAIを試したけど、人間に勝つためにはGameplayをすごく制限しないといけなかったんだ。大変だよね。
「AI」のDefinitionって、ずーっと「どうやって動くかよく分かんないけど、詳しい人は少ない」っていう、Definitionが動くTargetだったんだ。AI Effectみたいな？だから、いつか今使ってるLLMだって、AIって呼ばれなくなる日が来ると思うよ。
これ見てみてよ。AI effectについてのWikipedia記事。LLMのことでもっと更新が必要かもね。誰かやる？
https://en.m.wikipedia.org/wiki/AI_effect
「Artificial intelligence」って言葉は、Technical termじゃなくて、いつもMarketing termだったんだ。John McCarthyがDARPAのGrantをもらうために、審査員にウケるようにカッコいいPhraseを選んだのが始まりらしいよ。
俺が生徒に説明する時は、「Traditional AI」、「Machine Learning」、「Data Science」をベン図で示すやり方なんだ（まあ、最近はGen AIが別の円を作り始めてるけどね）。
A*は「Traditional AI」の領域に分類されるよ。これは状態探索、論理表現、統計／確率（今はデータサイエンスって呼ばれてる）の混合なんだ。
一般の人が「AI」って考えてる場所は、それら全ての円が集まる所で、ロボットからif-else文まで何でも含まれてるんだ。
＞これが昔「AI」と呼ばれてたのは興味深いね。
大学のAI研究室でA*を習ったのを覚えてるよ。
今はこういうのって些細に聞こえるし、当たり前だと思って使ってるよね。
老いを感じるね〜。
大学院で「Game AI」の授業を取ったことがあるんだ。
その授業では、色々なパスファインディングのアプローチとか意思決定の方法を、MLやAIとは別の、役に立つ分野として学んだよ。
初期のAIの多くは、単純に昔からある古典的なデータ構造やアルゴリズムを応用したものだったんだ。
まあ、パーセプトロンは何十年も前からあるけどね。
誰かこの情報をGarminのバカどもに送ってくれ！
あいつらのナビは、山とか水の上を真っ直ぐに進めって言って、到達できない目的地に案内するんだぜ。
まるで「私には分かりません」って言わないAIみたいだ。
グリッドベースのパズルゲーム開発者として（https://thinky.gg — Pathologyは最短ステップでA地点からB地点に行くゲームの一つだよ）、A*には最適化だけでなく、その上に様々なヒューリスティックを構築することで他の種類のパスファインディングにももっと汎用的に使える点に魅力を感じてるんだ。
デベロッパーの中には、双方向探索、事前計算されたパターンデータベース、デッドロック検出みたいな技術を使うソルバーを作った人もいるよ。
双方向探索、俺は「double-ended」って習ったんだけど、これマジで役に立つよ（30%速くなるって読んだことがある）。
都市や国の道路探索とかね。
実際の道路みたいに、複数の層（動脈路線の重要度が違う）があって、高速で（重みが軽い）移動できるんだ。
前の地図の仕事で、俺たちのバックエンドがこれを使ってマジで助かったよ。
これは「パスファインディング」のカテゴリでブックマークしてるよ。
一緒にブックマークしてるのはこれらかな。
https://juhrjuhr.itch.io/deep-space-exploitation/devlog/9454
https://www.redblobgames.com/grids/hexagons/
関連リンクをいくつか。
https://lukeyoo.fyi/recap/2025/5/a-star
https://github.com/micttyoid/quantized-pathfinding
個人的にA*の最高の入門はルーマニアを旅することだと思うな :)
AI a Modern Approachっていう本もいいよ。
このチュートリアル、”ルーマニアの地理わかんない人には申し訳ないけど、みたいな注釈あったよね？”(うろ覚えだけど)って話。
A*の経路探索がどんな感じか、この動画で可視化しててわかりやすいよ → https://youtube.com/shorts/L8t0tt1Vrsw
これ見て懐かしくなった！俺も何年か前に学校の課題でA*習った時、このチュートリアル EXACTLY 使ったんだよねー。
超簡単な質問かもだけど、これってどう読むの？ A-star？ Ah-sterisk？
Ay-star（エイスタァ）だよ。
A*はシンプルでいいけど、環境がまだわかってない状態での経路探索って、どうやるんだろう？
知らない環境でのマッピングとか経路探索なら、Simultaneous localization and mapping ってやつがあるよ。詳しくはこちら → https://en.m.wikipedia.org/wiki/Simultaneous_localization_an…
SLAMはマッピング向けかな。未知の環境でのプランニング（実行）なら、多分 D* Lite とかじゃない？
確か今は、こういう問題には機械学習ベースのアプローチが一番いいと思うよ。他には、まず探索して環境情報を先に手に入れるステップを入れるとか。
機械学習の手法はパス探索にはあまり向いてないね。最先端の技術でも、A*みたいなステート空間探索には敵わないんじゃないかな。
ベンチマークは見当たらないけど、俺が言ってたのはこういうアプローチの例だよ：https://www.researchgate.net/publication/355761412_Path_plan…
GOFAI技術ってのは、
A) 環境の後知恵を取り込むのが苦手なことが多いんだ。
それに、
B) 探索コストを考慮するように応用するのが、全く現実的じゃないことも多いんだよね。
最適な輸送理論とかを使った、未知の環境での最適な不偏パス探索のGOFAI技術も聞いたことはあるけどさ。でも不偏な方法って、実際の環境では明らかに劣るだろうね。
いて座A*（Sagittarius A*）と間違えないようにね。こっちだよ：https://en.wikipedia.org/wiki/Sagittarius_A*
AやHN初めての人もいるかもしれないって考えてみてよ！初めて見たって人もいるかもだろ？それに、透視図法の本を10冊持ってて、全部ないと理解できないってこともあるんだ。
あるいは、Aについて教えてるなら、この記事が学生に一番よく伝わるってこともあるかもしれないだろ。他の記事へのリンクを提供してくれてありがとう！誰かの役には立つと思うよ！
そうそう、前に記事が投稿されたらもう終わりで、みんなその日オンラインだったって思ってる変な抽象化に縛られて生きてる人がいるんだよね。で、何故かそれを指摘することで得られる『委員長ポイント』を追い求めてる。今日の視点からどんな議論ができるか見てみようぜ。
A*は人気があって当然だと思うよ。CS101でみんなが学ぶ深さ優先や幅優先探索の簡単な応用で、すごく役に立つ状況があるのに、なぜかCS教育の標準じゃないんだよね。
初めて学ぶ時は本当に素晴らしい発見だよ。
BFSとDFSの違いが「探索してないノードの袋から次に探索するノードをどう選ぶか」だって認識するのに役立つなら、さらに素晴らしい。
DFSを再帰アルゴリズムとしてだけ教わると、その対称性が見えなくなりがちだからね。
数年ごとに新しい世代のプログラマーを驚かせるために、繰り返し出てくればいいんだよ。
この記事見てびっくりしたよ。この時期じゃないんだもん。A*ってだいたい12月頃に出てくるんだよね。Advent of Codeを通じて知る人が多いから。
（僕もAdvent of Codeでしか使ったことないけど）
もっとコメントを表示（2）
これはただ単に、パスファインディングを始めたばかりの人に教える最初の、最も分かりやすいものだからだと思うよ。現実世界でも使えるし、視覚化や計算も簡単だからね。
だからチュートリアルも全部これなんだ :)
この記事が何度も戻ってくる本当の理由は、A*アルゴリズムそのものより、例とか視覚化を通して教えるのがいかに上手いか、だと思うね。
A*は好きじゃないなー。あれはパフォーマンスハックであって、モノが目的地に着こうとする時の自然な振る舞い方とは違うと思うんだ。
ハックでもないし、何かみたいに振る舞おうとしてるわけでもないよ。Aは完全で最適なアルゴリズムで、ちゃんと証明できる性質を持ってるんだ。もし適切なヒューリスティックがあれば、ダイクストラ法よりAを使うべきだよ。
非許容ヒューリスティックも役に立つことがあるし、それがどれだけ最適じゃなくなるかを考えるのは簡単だよ。最適な結果よりパフォーマンス優先したい時（探索空間の一部を無視とか）や、ゲームキャラをちょっとバカっぽく動かしたい時（ジグザグ行かせるとか）に使えるかもね。
多分投稿者が言いたかったのは、非許容ヒューリスティックは、最適じゃなくても時々もっと自然に見える動きになるってことだと思うな。
A*って、どうやって行くかじゃなくて、どう行くかを「決める」方法なんだよ。結果は最短経路で、それに従って動くんだ。これは人が知らない場所で最短ルートを見つけるのと結構似てるね。地図で北の都市に行く最短ルート探す時、南に行く道はあんまり見ないでしょ？目的地にまっすぐ近づく道を中心に探すよね。
いろんな状況でめっちゃ役に立つよ。もし Civilizationみたいな見下ろし型ストラテジーゲーム作るなら、Aは完璧だね。なんか変なこと起きずに最短経路出してくれる、高速なパフォーマンスハックとして。でも、環境が違うとダメかな。レーシングゲームとかにはAはそんなに役に立たないね。
ヘックスタイルでA*を実装するのに3時間かかったけど、最初に試した時（陸地タイルだけね）動いたよ。特にCivみたいなゲーム向け。ユニットをまとめて一緒に動かそうとすると複雑になるんだ。貨物船や軍艦で水上を渡れるようにするのは、また別の課題だね。
