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, widely considered the first mobile robot capable of reasoning about its own actions, needed a way to plan a path across a room full of obstacles using a limited onboard computer. Their paper, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths," did something unusually rigorous for the era: it didn't just propose a faster heuristic search, it proved exactly which class of heuristics guaranteed the result would still be optimal — the admissibility condition covered below. That formal guarantee is precisely why A* displaced ad-hoc heuristic search methods and became the default choice everywhere from GPS navigation to real-time strategy games.

Working Principle

A* (introduced conceptually in Part 10) is Dijkstra's algorithm with one addition: instead of prioritizing the frontier purely by \(g(v)\) (the actual distance traveled so far), it prioritizes by \(f(v) = g(v) + h(v)\), adding a heuristic estimate \(h(v)\) of the remaining distance to the goal. This single change lets the search "lean toward" the goal instead of expanding uniformly outward.

def astar_pseudocode(graph, start, goal, heuristic):
    """
    graph: dict[vertex] -> list[(neighbor, weight)]
    heuristic: function(vertex) -> estimated distance to goal
    """
    import heapq
    g = {start: 0}
    open_set = [(heuristic(start), start)]   # (f-score, vertex)
    came_from = {}

    while open_set:
        _, current = heapq.heappop(open_set)
        if current == goal:
            return g[current]   # found the optimal cost (if heuristic is admissible)

        for neighbor, weight in graph[current]:
            tentative_g = g[current] + weight
            if neighbor not in g or tentative_g < g[neighbor]:
                g[neighbor] = tentative_g
                came_from[neighbor] = current
                f = tentative_g + heuristic(neighbor)
                heapq.heappush(open_set, (f, neighbor))

    return None   # goal unreachable

Choosing a Heuristic

The rule for picking one safely: the heuristic's assumed movement must never be more restrictive than the graph's actual movement rules — Manhattan distance on an 8-directional grid would overestimate distance (diagonal moves make some paths shorter than the heuristic assumes), breaking admissibility.

Worked Example

A 4×1 grid, start at column 0, goal at column 3, using Manhattan distance as the heuristic (here just the horizontal distance remaining).

flowchart LR
    S["Start
g=0, h=3, f=3"] --> C1["Cell 1
g=1, h=2, f=3"]
    C1 --> C2["Cell 2
g=2, h=1, f=3"]
    C2 --> G["Goal
g=3, h=0, f=3"]
            

Notice \(f\) stays constant at 3 the entire way — exactly the true remaining distance at every step, since the heuristic here is a perfect (if trivial) predictor. In a graph with obstacles, \(f\) would fluctuate as the heuristic's straight-line estimate diverges from the actual best route around barriers, but A* still explores far fewer cells than Dijkstra would, because it never wastes effort expanding cells that clearly lead away from the goal.

Why Admissibility Guarantees Optimality

This is a direct adaptation of Dijkstra's correctness proof (from its deep dive) with the heuristic folded in. Claim: if \(h\) is admissible (never overestimates true remaining distance), the first time A* pops the goal vertex from the priority queue, \(g(\text{goal})\) is the true shortest-path distance. Proof sketch: suppose some other, cheaper path to the goal exists through a currently-unexpanded vertex \(u\). Since \(h\) never overestimates, \(f(u) = g(u) + h(u) \leq g(u) + \text{true remaining distance from } u = \text{true total cost through } u\), which by assumption is less than the goal's current \(f\)-value — so \(u\) (or some vertex on its path) would have been popped from the priority queue before the goal, contradicting that the goal was popped first. This is exactly Dijkstra's argument, generalized to account for the heuristic's optimistic bias.

Complexity Analysis

In the worst case (a completely uninformative heuristic, \(h(v) = 0\) everywhere), A* degrades exactly to Dijkstra's algorithm:

$$\text{Time: } O((V+E)\log V) \text{ worst case} \qquad \text{Typically far less with a strong heuristic}$$

The practical speedup from a good heuristic is often dramatic — orders of magnitude fewer vertices explored on large spatial graphs — even though the worst-case bound doesn't change.

Implementation

import heapq

def astar(graph, start, goal, heuristic):
    g = {start: 0}
    parent = {start: None}
    open_set = [(heuristic(start), start)]
    visited = set()

    while open_set:
        _, current = heapq.heappop(open_set)
        if current in visited:
            continue
        visited.add(current)

        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, []):
            tentative_g = g[current] + 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), 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 <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <functional>
#include <iostream>
using namespace std;

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

    unordered_map<string, int> g{{start, 0}};
    unordered_map<string, string> parent;
    unordered_set<string> visited;
    priority_queue<pair<int,string>, vector<pair<int,string>>, greater<>> open;
    open.push({heuristic(start), start});

    while (!open.empty()) {
        auto [f, current] = open.top(); open.pop();
        if (visited.count(current)) continue;
        visited.insert(current);

        if (current == goal) {
            vector<string> path;
            string node = goal;
            while (true) {
                path.push_back(node);
                if (!parent.count(node)) break;
                node = parent[node];
            }
            reverse(path.begin(), path.end());
            return {g[goal], path};
        }

        for (auto& [neighbor, weight] : graph[current]) {
            int tentativeG = g[current] + weight;
            if (!g.count(neighbor) || tentativeG < g[neighbor]) {
                g[neighbor] = tentativeG;
                parent[neighbor] = current;
                open.push({tentativeG + heuristic(neighbor), neighbor});
            }
        }
    }
    return {-1, {}};
}

int main() {
    unordered_map<string, vector<pair<string,int>>> graph = {
        {"S", {{"A", 1}}}, {"A", {{"B", 1}}}, {"B", {{"G", 1}}}, {"G", {}}
    };
    unordered_map<string, int> distToGoal = {{"S", 3}, {"A", 2}, {"B", 1}, {"G", 0}};
    auto [cost, path] = astar(graph, "S", "G", [&](const string& v) { return distToGoal[v]; });
    cout << "Cost: " << cost << endl;  // 3
    return 0;
}

import java.util.*;
import java.util.function.ToIntFunction;

class AStar {
    record Edge(String to, int weight) {}

    static int[] astar(Map<String, List<Edge>> graph, String start, String goal,
                        ToIntFunction<String> heuristic) {
        Map<String, Integer> g = new HashMap<>();
        g.put(start, 0);
        Set<String> visited = new HashSet<>();
        PriorityQueue<Object[]> open = new PriorityQueue<>(Comparator.comparingInt(o -> (int) o[0]));
        open.add(new Object[]{heuristic.applyAsInt(start), start});

        while (!open.isEmpty()) {
            Object[] top = open.poll();
            String current = (String) top[1];
            if (visited.contains(current)) continue;
            visited.add(current);
            if (current.equals(goal)) return new int[]{g.get(goal)};

            for (Edge e : graph.getOrDefault(current, List.of())) {
                int tentativeG = g.get(current) + e.weight();
                if (!g.containsKey(e.to()) || tentativeG < g.get(e.to())) {
                    g.put(e.to(), tentativeG);
                    open.add(new Object[]{tentativeG + heuristic.applyAsInt(e.to()), e.to()});
                }
            }
        }
        return new int[]{-1};
    }

    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, Integer> distToGoal = Map.of("S", 3, "A", 2, "B", 1, "G", 0);
        int[] result = astar(graph, "S", "G", distToGoal::get);
        System.out.println("Cost: " + result[0]);  // 3
    }
}

Real-World Applications

Exercises

1. Run A* by hand on a small grid with one obstacle, using Manhattan distance, and count how many cells it expands compared to a plain BFS/Dijkstra sweep.
2. Prove that Euclidean distance is always admissible for a graph where movement is allowed in any direction at unit cost per unit distance.
3. Construct a heuristic that overestimates in at least one case, and show a concrete example where A* using it returns a suboptimal path.
4. Challenge: Implement A* with a "weighted" heuristic \(f(v) = g(v) + w \cdot h(v)\) for \(w > 1\) (deliberately sacrificing optimality for speed), and measure the tradeoff between path quality and vertices expanded as \(w\) increases.

Limitations