カーナビが目的地までの道順を一瞬で出す。ゲームの敵が壁を避けて最短でこちらへ寄ってくる。どちらも裏では「最短経路を求める」という同じ問題を解いています。
素朴にやるなら、スタートからゴールまでの道を片っ端から試して、いちばん短いものを選ぶことになります。ですが分かれ道のたびに候補が枝分かれするので、少し広い地図になっただけで組み合わせは天文学的にふくれ上がり、まともに終わりません。それでも地図アプリやゲームが即座に答えを返すのは、全部の道を試したりせず、「見込みのある候補から順に確定していく」というひとつの発想を使っているからです。その王道がダイクストラ法で、もう一段賢くしたのが A★（エースター）です。順に見ていきます。
いちばん安い候補から確定する ── ダイクストラ
地図をマス目で考えます。1マス進むのにコストがかかり、ふつうの道は $1$、ぬかるみのように通りにくいマスは $5$、というふうに重みをつけます。目指すのは、スタートからゴールまでのコストの合計がいちばん小さい道です。
鍵になるのが $g$ という値です。$g$ は経路の名前でも「今の勝者」でもなく、マスひとつひとつが持つ数字で、「そのマスへ、今わかっている範囲でいちばん安く行くといくらか」を表します。スタート地点は $g=0$。そこから隣の上下左右を見ると、4マスそれぞれに $g=1$ が付きます。ここで大事なのは、この4マスから1つを選ぶわけではないこと。4マス全部が「暫定 $g=1$」の候補（フロンティア）として並びます。
ダイクストラがやるのは、フロンティアに並んだマスのうち $g$ がいちばん小さいものを1つ取り出して確定し、その隣の $g$ を計算して候補に加える、という手順の繰り返しだけです。たとえば $g=1$ の上のマスを確定したとします。するとその周り（さらに上・左上・右上）に $g=2$ が付きます。では次に進むのはその $g=2$ のどれか——ではありません。候補にはまだ手つかずの「右」「左」「下」が $g=1$ のまま残っています。$1 < 2$ なので、次に確定するのは上方向ではなく、この $g=1$ のマス。「上へ一歩進んだのに、また元の近くへ戻って右を確定する」ように見えるのは、このためです。全体でいちばん安い候補を選ぶ、という一点を守っているだけなのです。
そして、ここがダイクストラの心臓部です。1つのマスは、まわりの確定が進むにつれて、いくつものルートから「このマス経由なら $g$ はいくつ」という候補を何度も受け取ります。同じマスに、複数の $g$ の候補が届くのです。そのたびにやることは一つだけ。いま持っている値より安ければ書き換える（これを更新、あるいは緩和と呼びます）。だから各マスの $g$ は、届いた候補のうち最小値へとだんだん下がっていき、そのマスが全体でいちばん安くなった瞬間に、最小のまま確定します。この「複数の候補が届いて、小さい方だけが生き残る」一手が、遠回りと近道を正しく選び分けているからくりの全部です。のちほど、ぬかるみのところで、この様子を実際の数字で見ます。
だから確定は $g$ の小さい順に進みます。$g=1$ のマスをぜんぶ埋めてから $g=2$ の輪、その次が $g=3$ の輪……と、同じ $g$ のマスがひと組ずつ確定していきます。池に石を落としたときの輪とまったく同じで、輪の半径がそのままコスト $g$。この輪が外へ育っていくのが「波紋」の正体です。
最短が保証されるのは、いちばん安いマスにはもうそれ以上安く来る方法が残っていないからです。他のマスは今より高いコストからしか伸びてこないので、確定した瞬間にその $g$ は最終値として動きません。
では、壁があるとどうなるか。壁は「コストが高い」のではなく、そもそも通れないマスです。計算に入る前に、道として除外されます。だから突き抜けはできず、上か下へ回り込むしかありません。回り込むぶん、壁の裏のマスは $g$ が大きくなり、確定も遅れます。結果として、同じ $g$ の輪は壁のところで食い込み、波紋が壁を避けて、へこみながら広がっていくように見えます。
ぬかるみは、壁とはまったく別ものです。ぬかるみは通れます。ただし通るとコストが高い（このデモでは1マスあたり5）。ここがダイクストラの賢いところで、ぬかるみを「禁止」したり、はじめから計算の外に置いたりはしません。ぬかるみを突っ切った場合の合計コストと、迂回した場合の合計コストを両方きちんと出して、安いほうを採るだけです。だから「通るか避けるか」は決め打ちのルールではなく、ぬかるみの深さ（通りにくさ）と広さ、そして迂回がどれだけ遠いかの綱引きで決まります。深いぬかるみ（コスト5）なら迂回したほうが安く、浅くて通りやすいぬかるみ（コスト2）なら、遠回りするより突っ切ったほうが安く済む、というふうにです。
では、ダイクストラはこの「どっちが安いか」をどうやって知るのでしょう。経路を2本まるごと作って比べているわけではありません。マスごとに $g$ を配って進むうちに、ある地点へ複数のルートから $g$ の候補が届くたびに、「今より安ければ更新する」だけです。ここで効いてくるのが、さきほどの「同じマスに複数の候補が届いて、小さい方だけを残す」という一手です。ぬかるみのすぐ右どなりのマスには、まっすぐ突っ切ってきた $g$ と、上を迂回してきた $g$ の2つが届きます。同じマスなのに、いったんは $g$ の候補が2つ立つのです。ダイクストラはそのうち小さいほうだけを残します。
深いぬかるみ（+5）なら、まっすぐの $g$ は $1, 2, 7, 12, 13$ と跳ね上がるので、迂回の $9$ が勝ちます。浅いぬかるみ（+2）なら、まっすぐは $1, 2, 4, 6, 7$ で、今度は $7$ が迂回の $9$ に勝つ。同じマスに届く $g$ の候補が2つあって、そのつど小さい方が生き残る——この一手が、通る／迂回を分けている正体です。特別な場合分けをしているわけではなく、ただ「安いほうで上書きする」を繰り返しているだけなのです。
「結局どの道を通ったのか」は、探索中に気にしなくて大丈夫です。各マスが「自分の $g$ を更新してくれた隣」だけ覚えておき、最後にゴールからその印を逆にたどれば、一本の最短経路が浮かび上がります。
手数か、コストか ── 幅優先(BFS)との違い
ここで、ダイクストラのいとこのような、もっと素朴なやり方にも触れておきます。幅優先探索（BFS）です。名前はいかめしいですが、やることは「スタートから一歩の場所、二歩の場所……と、歩数の近い順にべたっと塗り広げていく」だけ。じつは、さきほどのダイクストラで「どのマスもコストが同じ（重みなし）」という場合が、ちょうどこの BFS にあたります。
両者の違いは、重みを見るかどうかだけです。BFS は一歩を一歩としか数えないので手数こそ最短ですが、ぬかるみだろうとおかまいなしに突っ切るため、合計コストは高くつくことがあります。ダイクストラはコストを積み上げて比べるので、避けたほうが安ければぬかるみを迂回し、手数が多少増えてもコストの合計を最小にします。重みが入った瞬間に、同じ「近い順」でも「手数の短い道」と「コストの安い道」へ枝分かれするわけです。
ゴールの方を優先する ── A★
ダイクストラの弱点は、ゴールがどちらにあるかをまったく気にしないことです。$g$（スタートからの実コスト）が小さい順に、全方位へ均等に広げるので、ゴールと正反対の空き地まで律儀に塗ってしまいます。
そこで A★ は、$g$ にもう一つ、$h$ という値を足します。
$$ f = g + h $$
ここで $g$ と $h$ は、向きが正反対です。$g$ は「スタートから“もう来た道”に、実際にかかったコスト」。後ろ向きの、確定した実績です。いっぽう $h$ は「そのマスからゴールまで、“これから”どれくらいかかりそうか」の見積り。前向きの、まだ通っていない道の当て推量です。大事なのは、$h$ は探索して測るわけではないこと。ゴールの座標はわかっているので、マスの位置との差から公式でパッと出せます。グリッドなら、縦の差と横の差を足すだけ——マンハッタン距離です。壁もぬかるみも考えずに、まっすぐ測った「ざっくりの残り歩数」だと思ってください。
$g$ がスタートから広がる波紋なら、$h$ はゴールから広がる波紋。向きが逆なだけで、どちらもマスに数字を配っているのは同じです。
そして A★ は、この2つを足した $f = g + h$ の小さいマスから確定します。$f$ は「このマスを通ってゴールまで行くと、ざっと総額いくらか」の見込みです。ここに効き目が出ます。$g$ が同じ2つのマスでも、ゴールに近いほう（$h$ が小さいほう）は $f$ が小さくなる。だから A★ はゴールに近いマスを先に確定し、探索がゴールの方へ細く伸びていきます。$g$ しか見ないダイクストラは、この2つを区別できず、ゴールと逆のマスまで律儀に広げてしまう——その差です。
さきほどの波紋でいえば、A★ は $h$ のぶんだけ波紋をゴール方向へ引き伸ばして、要らない輪を描かせないイメージ。同じ盤面でも、探索するマス数はこれだけ変わります。
デモの初期盤面でも、ダイクストラが $170$ マスほど調べるところを、A★ はおよそ $90$ マスで同じ最短コストにたどり着きます。
最後に、いちばん引っかかりやすい「控えめな $h$」の話です。まず押さえたいのは、$h$ は自動で決まるものではなく、こちらが選ぶ「見積りの公式」だということ。マンハッタン距離はその一例にすぎません。$h=0$ と決めればただのダイクストラになりますし、直線距離を使う手も、わざと大きめの数を使う手もあります。だから「誰が控えめにするのか」の答えは、$h$ の公式を決める人（設計者）です。
「控えめ（許容的）」とは、選んだ $h$ が本当の残りコストを絶対に超えないこと。マンハッタン距離が自動的にこれを満たすのは、壁もぬかるみも無視してまっすぐ測っているからです。実際には壁を回ったり、ぬかるみで余計にかかったりするので、本当の残りは必ずマンハッタン以上。つまりマンハッタンは、必ず「本当以下」＝控えめになります。
なぜ控えめが大事かというと、$h$ が本当を超えなければ $f = g + h$ も本当の総コストを超えないので、A★ が最短の道を「高そう」と勘違いして捨てることがなく、必ず最短にたどり着くからです。逆に「マンハッタン×5」のような強気の見積りを選ぶと、探索はもっと速くなる代わりに、最短でない道を返すことがあります。速さと確実さのどちらを取るかは、$h$ の選び方しだい。A★ とは、ゴールの位置というヒントを控えめに使うダイクストラなのです。
触ってみる
同じ盤面で BFS・ダイクストラ・A★ を切り替えて、探索の広がり方を見比べられるようにしました。方式を変えると塗り広がる形が変わり、A★ だけがゴールの方へ細く伸びるのが分かります。各マスに出る数字がその $g$（スタートからの最小コスト。BFS のときだけは、重みを見ないので「手数」）で、同じ数字のマスが波紋の輪をつくります。盤面はクリックやドラッグで編集でき、壁やぬかるみを置いたり、スタートとゴールを動かしたりできます。下の比較表には三方式の探索マス数・経路コスト・手数が並ぶので、BFS は手数が最短でもコストが高いこと、A★ はダイクストラと同じコストをずっと少ない探索で当てることを、数字で確かめてみてください。ゴールを別のマスへ動かすと A★ の絞り込む向きがすぐ付いてくるのも、さきほどの「座標を知っている」話がそのまま目に見える瞬間です。
うまく表示されないときは、ビジュアライザを別タブで開く 。
どこで使われているか
道路網を距離や所要時間で重み付けして最短路を出すカーナビや地図アプリ、壁を避けてユニットを動かすゲームAI、障害物をよけて2点を結ぶ配線や配管の設計。どれも最短経路探索そのものです。ネットワークの世界でも、ルーティングプロトコルの OSPF がリンクコストにダイクストラ法を使って経路を決めています。実際の地図規模になると、A★ をさらに前処理で加速した手法（ALT や Contraction Hierarchies など）が使われますが、芯にあるのはここで見た「見込みのある候補から確定する」という同じ考え方です。
気をつけたいこと
A★ の $h$ は控えめな見積りでなければなりません。ゴールまでを実際より大きく見積もると、探索は速くなる代わりに最短でない道を返すことがあります（それで構わない場面もありますが、保証は消えます）。また、コストに負の値が混じるとダイクストラの前提 ── いちばん安いものを確定したらもう覆らない ── が崩れるので、そのときはベルマン–フォード法のような別の道具が要ります。そして A★ はダイクストラの万能な上位互換ではなく、良い $h$ を作れて初めて効くものです。手がかりのない問題では $h=0$、つまりただのダイクストラに戻ります。
シリーズの仲間
このシリーズは「素朴なやり方だと大変そう ── でも隠れた構造を突くと一気に」という気持ちよさで繋がっています。
- 画像を「リネームだけ」で並び替える玉突き方式 … 並び替えのサイクルを、穴（目印）を歩かせてほどく。
- 配列を「その場で」左に回す … 別配列なしで、部分反転だけで回す。
- 配列を「輪」に見立てるリングバッファ … head の目印だけを動かして、先頭削除のシフトを消す。
- カメとウサギで「輪」を見つけるフロイドの循環検出 … 追加メモリ $O(1)$ でループと入口を発見。
今回は「探す」側でしたが、やみくもに広げず見込みのある候補から確定するという発想は、やはり同じ系譜にあります。
参考文献
- ダイクストラ法：E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik, vol. 1 (1959), pp. 269–271. DOI: 10.1007/BF01386390 。概説は Wikipedia: ダイクストラ法 。
- A★探索：P. E. Hart, N. J. Nilsson, B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths,” IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2 (1968), pp. 100–107. DOI: 10.1109/TSSC.1968.300136 。概説は Wikipedia: A* search algorithm 。
理屈だけだと掴みにくいので、ぜひ上のビジュアライザで壁やぬかるみを置き換えたり、ゴールを動かしたりしながら、三つの方式の広がり方と数字の違いを眺めてみてください。