A* Search

The idea

A* Search is an informed search that finds the cheapest path from start to goal. For each node it computes f(n) = g(n) + h(n): g is the real cost paid so far, and h is a heuristic guess of the cost still remaining. It always expands the waiting node with the smallest f, so it balances "how far I've come" with "how far I probably have to go" — giving the exactness of cost-based search with the speed of a good guess.

How it works

1. Put the start node in OPEN (the frontier of nodes waiting to be expanded), with g=0 and f = g + h(start).
2. CLOSED (already-expanded nodes) starts empty.
3. Pick from OPEN the node with the smallest f(n) = g(n) + h(n). This is the node we expand next.
4. If that node is the goal, stop — trace back the parent pointers to read off the shortest path.
5. Otherwise move it from OPEN to CLOSED (it is now expanded and won't be revisited normally).
6. Look at each neighbor: compute a tentative g = (g of current) + (edge cost to neighbor).
7. If this path to the neighbor is cheaper than any we've seen, record it — set the neighbor's g, f = g + h, and parent — and place/update it in OPEN.
8. Repeat from step 3 until the goal is expanded, or OPEN empties (meaning no path exists).

See it step by step

Watch A* Search search a real problem — flying from Sydney (SYD) to London (LHR). Click Next to advance one expansion and watch OPEN, the traversal, the path and the cost update live.

Start at Sydney. OPEN (the frontier) holds just Sydney.

Expanding

OPEN — frontier

CLOSED — traversal

Path so far

Cost so far

← Prev Step 1 / 6 Next step →

OPEN, CLOSED & the data structures

OPEN is a priority queue (min-heap) ordered by f(n) = g(n) + h(n), so the most promising node — lowest estimated total cost — always comes out first. CLOSED is a set of nodes already expanded; checking it prevents re-expanding the same node and wasting work. We also keep, per node, its best-known g cost and a parent pointer so we can rebuild the final path once the goal is reached.

Pseudocode

function A_STAR(start, goal, h):
    g[start] = 0
    f[start] = h(start)
    OPEN = priority queue ordered by f     # frontier
    push start into OPEN
    CLOSED = empty set                     # expanded nodes

    while OPEN not empty:
        current = node in OPEN with smallest f
        if current == goal:
            return reconstruct_path(current)
        move current from OPEN to CLOSED
        for each neighbor of current:
            if neighbor in CLOSED: continue
            tentative_g = g[current] + cost(current, neighbor)
            if tentative_g < g[neighbor]:      # a cheaper route found
                parent[neighbor] = current
                g[neighbor] = tentative_g
                f[neighbor] = tentative_g + h(neighbor)
                if neighbor not in OPEN: push neighbor into OPEN
    return failure                          # OPEN empty, no path

At a glance