はじめに
前回のダイクストラ法は、グリッド上の最短経路を確実に引けました。ただし1つ、もやっとする結果が残りました。最短経路はたった23セルなのに、それを見つけるためにマップのほぼ全部（369セル）を調べていたことです。
今回のA*（エースター）は、まったく同じマップ・まったく同じ最短コストのまま、この探索を 369 → 113 セル（約7割減） まで減らします。
やることは、ダイクストラにたった1つの関数を足すだけです。その関数の名前がヒューリスティック。この記事のゴールは、「なぜ見積もりを足すだけで、最短を保ったまま探索が速くなるのか」 を、自分のコードで再現できるようになることです。
このシリーズについて
本記事は、Pythonで経路生成（パスプランニング：ロボットやゲームのキャラが障害物をよけて目的地へ進む道すじを計算すること）を基礎から学ぶ全4回シリーズの第2回です。
前回のダイクストラが、あとの全手法が比較される 基準 でした。A*はその上に立つので、まだ①を読んでいない方は先に①からがおすすめです。
想定読者と環境
- 想定読者：Pythonが少し書ける方。前回①を読んで「$g$（実コスト）」「緩和」「優先度キュー」がなんとなく分かっていると一番スムーズです（未読でも本文で軽く復習します）
- 環境は前回と同じ。NumPy と Matplotlib だけ、優先度キューの
heapqは標準ライブラリなので追加インストール不要です
| ライブラリ | 用途 | インストール |
|---|---|---|
| NumPy | マップ（格子）を配列で持つ | pip install numpy |
| Matplotlib | 経路と探索の様子を可視化 | pip install matplotlib |
マップも前回とまったく同じものを使います（20×20・中央に壁と1マスの隙間・ぬかるみ帯）。同じ土俵で比べるためです。
1. 前回の宿題：369の無駄はどこから来たか
ダイクストラは「スタートに近い順」にノードを確定していきました。この戦略には、大きな盲点が1つあります。
ゴールが右上にあっても、ダイクストラは左下にも同じ熱心さで探索を広げる。
「近い順」しか見ていないので、探索は水たまりのように全方向へ均等に広がります。ゴールと反対方向にも、律儀にマスを塗りつぶす。これが369マスの正体です。
素直な不満はこうです。「ゴールはあっちにあるんだから、そっち側を重点的に探せばいいのに」。A*は、この不満をそのまま形にします。
2. A*のアイデア：f = g + h
ダイクストラは、優先度キューから $g$（スタートからの実コスト）が小さい順 にノードを取り出していました。A*は、取り出す順番を決める値を変えます。
f(v) = g(v) + h(v)
- $g(v)$：スタートから $v$ までの実際にかかったコスト（前回の主役。もう分かっている確定的な値）
- $h(v)$：$v$ からゴールまでの推定コスト（今回の新顔。まだ行っていないので「見積もり」）
- $f(v)$：その $v$ を通る道の、スタートからゴールまでの総コストの見積もり
ダイクストラが「ここまでどれだけ来たか（$g$）」だけで選んでいたのに対し、A*は「この先ゴールまでを含めた通し（$f$）」で選ぶ。違いはこれだけです。
前回の「探検隊」の比喩を延長しましょう。ダイクストラの隊員は、背後（スタートからの経過時間）だけを見て進む先を決めていました。A*の隊員は、それに加えて顔を上げてゴールの方角を見る。「ゴールに近づく一歩」を優先するので、隊列は反対方向に散らばらず、ゴールへ細く伸びていくのです。
3. ヒューリスティック h の設計：「過大評価しない」が最短保証の条件
ここが今回いちばん大事なところです。「見積もり $h$ を足すだけ」と言いましたが、$h$ の作り方をまちがえると、A*は最短経路を見失います。安全な $h$ の条件は、たった1つ。
許容性（admissibility）：$h$ は、本当のゴールまでのコストを、決して超えて（過大評価して）はいけない。
理由は直感的です。$h$ が本当の残りコストより大きいと、A*は「あっちは遠そうだ」とまだ短い可能性のある道を早々に見捨ててしまう。逆に $h$ が本当のコスト以下（＝控えめな見積もり）である限り、A*は最短を見落としません。
$h = 0$（＝まったく見積もらない）は、いつでも許容的です。このとき $f = g$ となり、A*はダイクストラそのものに戻ります。つまりダイクストラはA*の特別な場合（$h=0$）。これは章末で実際に確かめます。
今回の h：オクタイル距離
本記事のマップは8近傍（斜め移動あり・斜めのコストは $\sqrt{2}$）なので、それに合った見積もりを使います。オクタイル距離（octile distance：斜めに進める前提での最短の格子距離）です。ゴールまでの縦の差を $dr$、横の差を $dc$ とすると、
h = \sqrt{2}\cdot \min(dr, dc) + 1 \cdot \bigl(\max(dr, dc) - \min(dr, dc)\bigr)
「斜めで詰められるだけ詰めて（$\sqrt{2}$）、残りをまっすぐ進む（$1$）」と見積もる、という意味です。
なぜ地形（ぬかるみ×3）を無視してよいのか。 $h$ は「まっすぐ自由に進めたら」の距離なので、実際のコスト（壁を迂回する・ぬかるみで3倍かかる）は必ずこの見積もり以上になります。つまりオクタイル距離は決して過大評価しない＝許容的。だから最短保証が保たれます。実際、スタート地点では $h=24.04$ に対し本当のコストは $26.97$。ちゃんと下回っています。
4. 実装する：ダイクストラとの差分は「キューに h を足す」だけ
処理の骨格は前回と同じ。違うのは、キューに入れる優先度を $g$ から $f=g+h$ に変える1点だけです。
図：A*の処理フロー。前回のダイクストラの図と見比べてください。オレンジの「$f=g+h$」以外は全部同じです。
ファイル構成も前回を流用します。constant.py・grid_map.py・plot.py は前回①とまったく同じなので、まだ手元にない方は①から持ってきてください。新しく書くのは heuristic() と astar.py、そして図を出す main.py だけです。
| ファイル | 前回から | 役割 |
|---|---|---|
constant.py |
流用（①と同一） | 定数（セルの種類・地形の重み・移動コスト） |
grid_map.py |
流用（①と同一） | 占有格子地図とサンプルマップ |
plot.py |
流用（①と同一） | 可視化の下地 |
astar.py |
新規 | A* 本体＋ヒューリスティック |
main.py |
差し替え | 解いて比較図を出す |
4-1. ヒューリスティック h
まず、今回の主役 heuristic() です。オクタイル距離をそのままコードにします。
# astar.py
import heapq # 優先度キュー（取り出すたびに最小の要素が出る）
from constant import CONNECTIVITY, COST_STRAIGHT, COST_DIAGONAL
from grid_map import GridMap
from dijkstra import reconstruct_path # 経路復元は①と共通
def heuristic(cell: tuple, goal: tuple) -> float:
"""
ゴールまでの推定コスト h（オクタイル距離）を返す
8近傍（斜め移動あり・斜めコスト√2）に整合したヒューリスティック。
地形の重み（ぬかるみ×3）は考えず「まっすぐ進めたら」の距離を返すので，
実際のコストを超えない（＝許容的：最短保証をこわさない）。
パラメータ
cell: 現在セル (row, col)
goal: ゴールセル (row, col)
戻り値
h: ゴールまでの推定コスト（下限の見積もり）
"""
dr = abs(cell[0] - goal[0])
dc = abs(cell[1] - goal[1])
# 斜めで詰められるぶんは斜め(√2)，残りは直線(1)で進むと見積もる
diagonal = min(dr, dc)
straight = max(dr, dc) - diagonal
return COST_DIAGONAL * diagonal + COST_STRAIGHT * straight
4-2. A* 本体
ダイクストラのコードと並べて見比べてください。キューの要素を (コスト, セル) から (f=g+h, g, セル) に変え、push する優先度に heuristic() を足す。変わったのは実質そこだけです。
def astar(grid_map: GridMap, connectivity: CONNECTIVITY = CONNECTIVITY.EIGHT) -> tuple:
"""
A* 法でスタートからゴールまでの最短経路（コスト最小の経路）を求める
Dijkstra との違いは，キューの優先度を g（実コスト）ではなく
f = g + h（実コスト＋ゴールまでの推定）にする1点だけ。
パラメータ
grid_map: 占有格子地図（スタート・ゴール設定済み）
connectivity: 近傍の種類（4近傍 / 8近傍）
戻り値
path: 最短経路（セルのリスト。到達できなければ空リスト）
explored: 確定した順に並べた探索済みセルのリスト（可視化・比較用）
cost: ゴールまでの最短コスト（到達できなければ無限大）
"""
start = grid_map.start
goal = grid_map.goal
# g 値（始点からの実コスト最小値）と，経路復元用の親ノード
dist = {start: 0.0}
came_from = {}
visited = set()
explored = []
# 優先度キュー。要素は (f=g+h, g, セル)。取り出し順は f の小さい順
queue = [(heuristic(start, goal), 0.0, start)]
while queue:
# いま未確定の中で f（＝g+h）が最小のノードを取り出す
f, cost, current = heapq.heappop(queue)
if current in visited:
continue
visited.add(current)
explored.append(current)
if current == goal:
break
# 近傍ノードを緩和（relax）する
for n_cell, move_cost in grid_map.neighbors(current, connectivity):
new_cost = cost + move_cost
if n_cell not in dist or new_cost < dist[n_cell]:
dist[n_cell] = new_cost
came_from[n_cell] = current
priority = new_cost + heuristic(n_cell, goal)
heapq.heappush(queue, (priority, new_cost, n_cell))
path = reconstruct_path(came_from, start, goal)
cost = dist.get(goal, float("inf"))
return path, explored, cost
理論とコードの対応は、ダイクストラの4つの勘どころに 1つ足すだけです。
- キューの要素を
(f, g, セル)の3つ組にして、取り出しは $f=g+h$ の最小（＝ゴールを含んだ通しで最有望なノードを選ぶ） - 確定の判定に使うのは相変わらず $g$（
dist）。$h$ は「並べ替えのヒント」に徹し、確定コストそのものは汚さない
つまずきポイント：なぜタプルを
(f, g, セル)の順にするのか。heapqはタプルを先頭の要素から比較します。先頭を $f$ にすれば「$f$ が小さい順」に取り出せます。$f$ が同点のときは次の $g$ で比較される（＝ゴールに近い方＝実コストの大きい方が優先されがち）ので、探索が素直にゴールへ伸びます。
4-3. 動かす
main.py で、ダイクストラとA*を同じマップで解いて、左右に並べて比較します。
# main.py
from constant import *
from grid_map import make_sample_map
from dijkstra import dijkstra
from astar import astar
from plot_compare import plot_compare_static, plot_compare_animation
def main() -> None:
grid_map = make_sample_map()
d_path, d_explored, d_cost = dijkstra(grid_map, CONNECTIVITY.EIGHT)
a_path, a_explored, a_cost = astar(grid_map, CONNECTIVITY.EIGHT)
print(f"Dijkstra: 通過点={len(d_path)} コスト={d_cost:.2f} 展開ノード={len(d_explored)}")
print(f"A* : 通過点={len(a_path)} コスト={a_cost:.2f} 展開ノード={len(a_explored)}")
plot_compare_static(grid_map, (d_path, d_explored, d_cost),
(a_path, a_explored, a_cost), "astar_compare.png")
plot_compare_animation(grid_map, (d_path, d_explored),
(a_path, a_explored), "astar_compare.gif", frames_n=40)
if __name__ == "__main__":
main()
比較図を描く plot_compare.py は本筋ではないので折りたたみにします（①の plot.py の下地をそのまま使い、左右2枚を並べているだけです）。
plot_compare.py の全文（クリックで展開）
# plot_compare.py （比較図。①の plot.py の下地 _draw_base を流用）
import matplotlib
matplotlib.use("Agg") # 画面を出さずに画像へ保存（ヘッドレス）
import matplotlib.pyplot as plt
import matplotlib.animation as animation
from plot import _draw_base
def _draw_panel(ax, grid_map, path, explored, title):
"""1枚ぶん（地形＋探索済み＋経路）を描く"""
_draw_base(ax, grid_map)
if explored:
ax.plot([c[1] for c in explored], [c[0] for c in explored],
"s", color="skyblue", markersize=6, alpha=0.5)
if path:
ax.plot([c[1] for c in path], [c[0] for c in path],
"-", color="tab:orange", linewidth=2.5)
_draw_base(ax, grid_map)
ax.set_title(title)
def plot_compare_static(grid_map, dij, ast, filename):
"""Dijkstra と A* の探索範囲・経路を左右に並べた静止画を保存"""
d_path, d_explored, d_cost = dij
a_path, a_explored, a_cost = ast
fig, axes = plt.subplots(1, 2, figsize=(11, 5.6))
_draw_panel(axes[0], grid_map, d_path, d_explored,
f"Dijkstra (explored={len(d_explored)}, cost={d_cost:.2f})")
_draw_panel(axes[1], grid_map, a_path, a_explored,
f"A* (explored={len(a_explored)}, cost={a_cost:.2f})")
fig.tight_layout()
fig.savefig(filename, dpi=110, bbox_inches="tight")
plt.close(fig)
def plot_compare_animation(grid_map, dij, ast, filename, frames_n=40):
"""探索フロントが広がる様子を左右で同時再生するGIFを保存"""
d_path, d_explored = dij
a_path, a_explored = ast
def cut(explored, i):
# 進捗率 i/frames_n までの探索済みセル
k = round(len(explored) * i / frames_n)
return explored[:k]
fig, axes = plt.subplots(1, 2, figsize=(11, 5.6))
def update(i):
for ax in axes:
ax.clear()
last = (i == frames_n)
_draw_panel(axes[0], grid_map, d_path if last else [], cut(d_explored, i),
f"Dijkstra (explored={len(d_explored)})")
_draw_panel(axes[1], grid_map, a_path if last else [], cut(a_explored, i),
f"A* (explored={len(a_explored)})")
anim = animation.FuncAnimation(fig, update, frames=frames_n + 1, interval=120)
anim.save(filename, writer="pillow")
plt.close(fig)
GIFの保存には Pillow を使います（
pip install pillow）。
5. 動かして、目で確かめる
5つのファイル（constant.py / grid_map.py / dijkstra.py / astar.py / plot.py）に、今回の plot_compare.py と main.py を加えて同じフォルダに置き、そのフォルダへ移動して実行します。
cd astar
python main.py
ターミナルには、次のように表示されます。
Dijkstra: 通過点=23 コスト=26.97 展開ノード=369
A* : 通過点=23 コスト=26.97 展開ノード=113
- 展開ノード 369 → 113（約7割減）：A*は反対方向をほとんど探索していない。$h$ がゴール方向へ探索を引き寄せた成果です
- コストは 26.97 で完全一致：速くなっても最短は1ミリも損なわれていない。これがオクタイル距離の許容性の御利益です
- 通過点はどちらも23：同じ長さの最適解にたどり着いている
左の水色（探索済み）がマップ全面に広がるのに対し、右のA*は水色がゴール方向へ細く伸びているだけ。この見た目の差が、そのまま 369 と 113 の差です。
⚠️ 経路の見た目は、マップやゴールによって前回とわずかに変わることがあります。 同じコスト26.97でも、それを実現する道すじは複数あり得ます（斜めをどこで消化するか等）。A*は「同コストの最適解のうちの1本」を返すので、ダイクストラの経路とセル単位で完全一致するとは限りません。コストが同じなら、どちらも正しい最短経路です。
6. まとめ：h の質が探索効率を決める
A*で、最短を保ったまま探索の無駄を7割減らせることを、同じマップで確かめました。要点です。
- A*は優先度を $g$ から $f = g + h$ に変えるだけ。$h$ が探索をゴール方向へ引き寄せる
- $h$ は**許容的（過大評価しない）**でなければならない。そうであれば最短は保証される
- $h = 0$ なら A* はダイクストラに戻る（ダイクストラは A* の特別な場合）
| 手法 | 経路コスト | 展開ノード数 | ゴール方向を意識？ |
|---|---|---|---|
| ダイクストラ（①） | 26.97 | 369 | しない |
| A*（今回） | 26.97 | 113 | する |
A*の賢さは、結局 $h$ の質にかかっています。ゴールへの見積もりが正確なほど探索は細く速くなり、雑なら（$h=0$なら）ダイクストラに逆戻り。「よい見積もりをどう作るか」 が、この先の経路計画でもずっと効いてきます。
次回③はポテンシャル法。ここまでの「格子（グリッド）をマスごとに調べる」世界を離れ、連続空間で「ゴールへの引力」と「障害物からの斥力」に沿って進む、別の発想の手法へ入っていきます。
章末：やってみよう
手を動かすと、$h$ の効き方が体に入ります。数値は手元で確かめた実測値です。
-
$h=0$ にする：
heuristic()が常に0.0を返すようにすると、A*はダイクストラそのものになり、展開ノードは113から369へ戻ります（コストは26.97のまま）。「ダイクストラ＝$h=0$のA*」を目で確認できます。 -
$h$ を盛って、やりすぎの閾値を探す：
returnをw * (...)に変えて倍率wを上げてみてください。このマップではw=2→展開24、w=3→展開23 とさらに速くなりますがコストは26.97のまま（まだ最適）。ところがw=5にすると展開は19まで減る代わりに、コストが 26.97 → 35.94 に悪化します。過大評価は「速いが最短が壊れる」トレードオフ。壊れ始める倍率を自分で挟み込んでみてください。 -
4近傍にする：
CONNECTIVITY.FOURにしたら、$h$ はマンハッタン距離（縦＋横の格子距離）に替えるのが自然です。近傍とヒューリスティックはセットで整合させる、が勘どころ。 -
ゴールを動かす：
make_sample_map()のゴールを変えると、$h$ の引き寄せの向きが変わり、探索範囲の形も変わります。
終わりに
今回は、ダイクストラに「ゴールの方角の見積もり $h$」を足すだけで、最短を保ったまま探索を速くできることを、手を動かして確かめました。$f = g + h$、そして $h$ は過大評価しない。この2つが分かっていれば大成功です。
経路生成シリーズ全体は、こちらのまとめから辿れます。
ロボット関連の記事はこちらのまとめにもあります。
次回は ③ポテンシャル法。格子を離れ、連続空間を「引力と斥力」で進みます。
役に立ったら いいね・ストック で応援いただけると、次回の励みになります。