A* Search

A* is the standard algorithm for pathfinding. It expands nodes in order of f(n) = g(n) + h(n):

• g(n) — the real, accumulated cost from the start to n (like Dijkstra).
• h(n) — a heuristic estimate of the remaining cost from n to the goal.

The heuristic “steers” the search toward the goal, so A* typically explores far fewer nodes than Dijkstra while still returning an optimal path.

The Algorithm

open = {start}; g[start] = 0
f[start] = g[start] + h(start, goal)

while open not empty:
    cur = node in open with the smallest f
    if cur == goal: return reconstructed path
    move cur to closed
    for each walkable neighbor nb:
        tentative = g[cur] + cost(cur, nb)
        if tentative < g[nb] or nb not seen:
            g[nb] = tentative
            f[nb] = g[nb] + h(nb, goal)
            parent[nb] = cur; add nb to open

return "no path"

The open list is usually a priority queue keyed by f. Nodes never become worse in g when revisited, so each relaxation either adds a node or improves it.

Optimality: Admissible Heuristics

A heuristic is admissible when it never overestimates the true cost to the goal. The classic grid heuristic is the Manhattan distance (for 4-directional movement) or Euclidean distance (for free movement). With an admissible h, f is a lower bound on the total path cost through n, so the first time the goal is expanded, its path is provably optimal. A heuristic that occasionally overestimates trades optimality for speed (weighted A*).

A* vs. Its Family

A* with h = 0 is Dijkstra. The heuristic is free information used to focus the search.

Where It’s Used

• Game AI — unit pathfinding on tile maps (often with Hierarchical A*, HPA).
• GPS navigation — with road-aware heuristics.
• Robot motion planning — grids, visibility graphs, and configuration spaces.
• Puzzle solving — the 8/15-puzzle uses admissible heuristics like misplaced tiles or Manhattan sums.
• Parsing — Viterbi and dynamic-programming variants of A* in NLP.

Practice Trajectory

1. Implement A* on a small grid; print open/closed after each expansion.
2. Prove Manhattan distance is admissible for 4-directional moves.
3. Compare node expansions against Dijkstra on the same map.
4. Add diagonal movement (cost √2) and update the heuristic accordingly.
5. Solve: maze shortest-path and sliding-puzzle problems.

When It’s the Right Tool