A* Search

A Bit of History

A* was developed in 1968 by Peter Hart, Nils Nilsson, and Bertram Raphael at the Stanford Research Institute (SRI), as part of the Shakey project. Shakey the Robot, an early mobile robot able to reason about actions, needed to plan around obstacles using very limited computing resources. Their paper, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths," did more than propose a faster search: it identified conditions under which heuristic guidance preserves optimality. That marriage of practical direction and a formal guarantee is why A* became a foundational tool in pathfinding and planning.

The Three Scores

For every discovered vertex $v$, A* separates what it knows from what it estimates:

Working Principle

A* is best understood as Dijkstra's relaxation rule with a more informed queue order. Assume finite, nonnegative edge costs and a goal heuristic:

1. Set $g(start)=0$ and push the start with priority $h(start)$.
2. Pop the entry with minimum $f$. Skip it if its saved $g$ no longer equals the best known $g$ for that vertex.
3. If it is the goal, reconstruct the path through parent pointers.
4. For every edge $(u,v)$ of cost $w\ge 0$, relax $g(v)$ with $g(u)+w$. On improvement, update the parent and push a fresh queue entry.
5. If the queue empties, the goal is unreachable.

Allowing a better $g$ value to push a vertex again is called reopening. It keeps graph-search A* correct for admissible heuristics even when they are inconsistent. Old heap entries are harmless because the stale-entry test discards them.

Choosing a Heuristic

Admissible: never overestimate

If $h^*(v)$ is the true cheapest remaining cost, admissibility requires $0\le h(v)\le h^*(v)$. The heuristic is optimistic: it may ignore walls, traffic, or terrain, but it cannot invent extra cost.

Consistent: obey a triangle inequality

For every edge $(u,v)$ with cost $w(u,v)$, consistency requires

$$h(u) \le w(u,v)+h(v), \qquad h(goal)=0.$$

Then $f$ never decreases along a path, so once a vertex is expanded with its best queue entry, it never needs reopening. Every consistent heuristic is admissible under the usual goal assumptions; an admissible heuristic need not be consistent.

Match the units. If one orthogonal step can cost as little as $c_{min}$, scale Manhattan distance by $c_{min}$. Obstacles may be ignored because ignoring them lowers the estimate. Discounted shortcuts, portals, or cheaper diagonal moves must be reflected or the heuristic may overestimate.

Worked Example

Use a 7×5 grid with unit-cost four-directional movement. Start at $(0,2)$, goal at $(6,2)$, and place a vertical wall in column 3 with one opening at the bottom. Manhattan distance ignores the wall, so it begins at 6 even though the true route cost is 10.

The early $f=6$ values are lower bounds, not promises. When the search reaches the wall and must move away from the goal, $g$ rises faster than $h$ falls, revealing the true $f=10$ route cost.

Why A* Is Optimal

Assume nonnegative edges, $h(goal)=0$, an admissible heuristic, and an implementation that accepts improved $g$ values even for previously expanded vertices. Let $C^*$ be the optimal start-to-goal cost.

Before an optimal solution is found, some frontier vertex $x$ lies on an optimal path with its optimal prefix cost $g^*(x)$. Because $h$ never overestimates,

$$f(x)=g^*(x)+h(x)\le g^*(x)+h^*(x)=C^*.$$

If A* popped the goal with cost greater than $C^*$, that goal entry would have $f(goal)=g(goal)>C^*$ while $x$ still had priority at most $C^*$. A min-priority queue could not choose the goal first. Therefore the first non-stale goal entry has optimal cost.

What consistency buys you

For a consistent heuristic, every traversed edge satisfies $f(v)\ge f(u)$ after relaxation from $u$. Once a vertex is expanded at minimum $f$, no later route can improve its $g$ value. A permanent closed set is then safe. With an admissible but inconsistent heuristic, reopening may be necessary—the implementation below supports it.

Complexity Analysis

With a consistent heuristic, nonnegative edges, and a binary heap, each vertex is expanded at most once and each edge is relaxed once:

$$\text{Time: } O((V+E)\log V) \qquad \text{Space: } O(V+E)$$

The duplicate-entry heap used below may hold multiple entries for a vertex, but at most one per successful relaxation; its logarithmic factor can be written $\log E$, which is $O(\log V)$ for ordinary simple graphs.

Heuristic quality mostly changes the number of states reached before the goal. With $h=0$, A* is Dijkstra. With a perfect heuristic, it can focus tightly on optimal routes. With an inconsistent heuristic, reopening can cause additional expansions and the simple one-expansion bound no longer applies.

Implementation

The code uses duplicate heap entries instead of a decrease-key operation. Each entry remembers the $g$ value that created it; if a better route has since been found, the entry is stale and skipped.

import heapq
from itertools import count

def astar(graph, start, goal, heuristic):
    g = {start: 0}
    parent = {start: None}
    sequence = count()  # avoids comparing vertex objects when scores tie
    open_set = [(heuristic(start), 0, next(sequence), start)]

    while open_set:
        _, pushed_g, _, current = heapq.heappop(open_set)
        if pushed_g != g.get(current):
            continue  # a later relaxation made this entry stale

        if current == goal:
            path = []
            while current is not None:
                path.append(current)
                current = parent[current]
            return g[goal], path[::-1]

        for neighbor, weight in graph.get(current, []):
            if weight < 0:
                raise ValueError("A* requires nonnegative edge weights")
            tentative_g = pushed_g + weight
            if neighbor not in g or tentative_g < g[neighbor]:
                g[neighbor] = tentative_g
                parent[neighbor] = current
                heapq.heappush(open_set, (
                    tentative_g + heuristic(neighbor),
                    tentative_g,
                    next(sequence),
                    neighbor,
                ))

    return None, None   # unreachable

# Grid coordinates, Manhattan distance heuristic
positions = {"S": (0, 0), "A": (1, 0), "B": (2, 0), "G": (3, 0)}
def manhattan(v):
    gx, gy = positions["G"]
    x, y = positions[v]
    return abs(gx - x) + abs(gy - y)

graph = {"S": [("A", 1)], "A": [("B", 1)], "B": [("G", 1)], "G": []}
cost, path = astar(graph, "S", "G", manhattan)
print("Cost:", cost, "Path:", path)   # Cost: 3  Path: ['S', 'A', 'B', 'G']

#include <algorithm>
#include <functional>
#include <iostream>
#include <queue>
#include <stdexcept>
#include <string>
#include <tuple>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;

using Cost = long long;
using Graph = unordered_map<string, vector<pair<string, Cost>>>;

pair<Cost, vector<string>> astar(
    const Graph& graph, const string& start, const string& goal,
    const function<Cost(const string&)>& heuristic) {

    unordered_map<string, Cost> g{{start, 0}};
    unordered_map<string, string> parent;
    using Entry = tuple<Cost, Cost, string>;  // f, saved g, vertex
    priority_queue<Entry, vector<Entry>, greater<Entry>> open;
    open.push({heuristic(start), 0, start});

    while (!open.empty()) {
        auto [f, pushedG, current] = open.top();
        open.pop();
        (void)f;
        if (!g.count(current) || pushedG != g.at(current)) continue;

        if (current == goal) {
            vector<string> path;
            for (string node = goal;; node = parent.at(node)) {
                path.push_back(node);
                if (node == start) break;
            }
            reverse(path.begin(), path.end());
            return {pushedG, path};
        }

        auto it = graph.find(current);
        if (it == graph.end()) continue;
        for (const auto& [neighbor, weight] : it->second) {
            if (weight < 0) throw invalid_argument("negative edge weight");
            Cost tentativeG = pushedG + weight;
            if (!g.count(neighbor) || tentativeG < g.at(neighbor)) {
                g[neighbor] = tentativeG;
                parent[neighbor] = current;
                open.push({tentativeG + heuristic(neighbor), tentativeG, neighbor});
            }
        }
    }
    return {-1, {}};
}

int main() {
    Graph graph = {
        {"S", {{"A", 1}}}, {"A", {{"B", 1}}},
        {"B", {{"G", 1}}}, {"G", {}}
    };
    unordered_map<string, Cost> h = {{"S", 3}, {"A", 2}, {"B", 1}, {"G", 0}};
    auto [cost, path] = astar(graph, "S", "G", [&](const string& v) { return h.at(v); });
    cout << "Cost: " << cost << " Path:";
    for (const auto& v : path) cout << ' ' << v;
    cout << '\n';
}

import java.util.*;
import java.util.function.ToLongFunction;

class AStar {
    record Edge(String to, long weight) {}
    record State(long f, long g, String node) {}
    record Result(long cost, List<String> path) {}

    static Result astar(Map<String, List<Edge>> graph,
                        String start, String goal,
                        ToLongFunction<String> heuristic) {
        Map<String, Long> g = new HashMap<>();
        Map<String, String> parent = new HashMap<>();
        g.put(start, 0L);

        PriorityQueue<State> open = new PriorityQueue<>(
            Comparator.comparingLong(State::f));
        open.add(new State(heuristic.applyAsLong(start), 0, start));

        while (!open.isEmpty()) {
            State state = open.poll();
            String current = state.node();
            if (!g.containsKey(current) || state.g() != g.get(current)) continue;

            if (current.equals(goal)) {
                LinkedList<String> path = new LinkedList<>();
                for (String node = goal; node != null; node = parent.get(node))
                    path.addFirst(node);
                return new Result(state.g(), path);
            }

            for (Edge e : graph.getOrDefault(current, List.of())) {
                if (e.weight() < 0) throw new IllegalArgumentException("negative edge weight");
                long tentativeG = state.g() + e.weight();
                if (!g.containsKey(e.to()) || tentativeG < g.get(e.to())) {
                    g.put(e.to(), tentativeG);
                    parent.put(e.to(), current);
                    open.add(new State(
                        tentativeG + heuristic.applyAsLong(e.to()),
                        tentativeG,
                        e.to()));
                }
            }
        }
        return null;
    }

    public static void main(String[] args) {
        Map<String, List<Edge>> graph = new HashMap<>();
        graph.put("S", List.of(new Edge("A", 1)));
        graph.put("A", List.of(new Edge("B", 1)));
        graph.put("B", List.of(new Edge("G", 1)));
        graph.put("G", List.of());

        Map<String, Long> h = Map.of("S", 3L, "A", 2L, "B", 1L, "G", 0L);
        Result result = astar(graph, "S", "G", h::get);
        System.out.println(result);  // Result[cost=3, path=[S, A, B, G]]
    }
}

Real-World Applications

A* is most useful when the state space is too large to search blindly, transitions have nonnegative costs, and the domain supplies a meaningful lower bound on the remaining cost.

The graph is a modeling choice

Before tuning a heuristic, decide what one state means and which transitions are legal. A grid cell may be enough for a simple map; a car-like robot may need $(x,y,\theta)$ so orientation is part of the state. A* can only optimize paths represented by that model.

Variants & Tradeoffs

Pitfalls & Debugging

Exercises

A compact mental model

A* is Dijkstra with informed ordering. The $g$ score records evidence, the heuristic supplies optimistic guidance, and $f=g+h$ decides what to investigate next. Correctness comes from the heuristic contract and from handling later improvements correctly—not from the priority formula alone.