A* Algorithm

This lesson covers the A (A-star) algorithm* — a heuristic-based search algorithm that finds the shortest path more efficiently than Dijkstra's in many cases. It is part of the OCR A-Level Computer Science (H446) specification, section 2.3.

---

What is A*?

A* (pronounced "A-star") is a best-first search algorithm that finds the shortest path between a start vertex and a goal vertex by combining:

1. g(n) — the actual cost from the start to the current vertex n.
2. h(n) — a heuristic estimate of the cost from vertex n to the goal.

The algorithm selects the next vertex to explore based on:

f(n) = g(n) + h(n)

Where f(n) is the estimated total cost of the path through vertex n.

---

How A* Differs from Dijkstra's

Feature	Dijkstra's	A*
Explores	All vertices (in order of distance from source)	Directed towards the goal using a heuristic
Heuristic	None (h(n) = 0)	Uses h(n) to guide search
Efficiency	Explores many unnecessary vertices	Typically explores fewer vertices
Finds	Shortest path to ALL vertices	Shortest path to a SPECIFIC goal
When h(n) = 0	A* becomes Dijkstra's algorithm	-

---

The Heuristic Function h(n)

The heuristic h(n) is an estimate of the cost from vertex n to the goal. It guides the search towards the goal rather than exploring in all directions.

Properties of a Good Heuristic

Property	Description
Admissible	Never overestimates the true cost to the goal. h(n) <= actual cost.
Consistent (monotone)	h(n) <= cost(n, m) + h(m) for every edge (n, m).
Informative	Higher values (closer to actual cost) make the search more efficient.

Why Admissibility Matters

If h(n) is admissible (never overestimates), A* is guaranteed to find the optimal (shortest) path. If h(n) overestimates, A* may find a suboptimal path.

Common Heuristics

Heuristic	Description	Best For
Straight-line distance (Euclidean)	sqrt((x2-x1)^2 + (y2-y1)^2)	Map navigation, continuous space
Manhattan distance		x2-x1
Zero heuristic	h(n) = 0	Reduces to Dijkstra's (always admissible)

---

Algorithm Steps

1. Create an open list (vertices to explore) and a closed list (already explored).
2. Add the start vertex to the open list with g = 0 and f = h(start).
3. While the open list is not empty: a. Select the vertex n with the lowest f(n) from the open list. b. If n is the goal, reconstruct and return the path. c. Move n to the closed list. d. For each neighbour m of n:
   • If m is in the closed list, skip it.
   • Calculate tentative g(m) = g(n) + weight(n, m).
   • If m is not in the open list, add it.
   • If this path to m is better (lower g), update g(m), f(m), and set n as m's parent.
4. If the open list is empty, no path exists.

Pseudocode (OCR Style)

function aStar(graph, start, goal, heuristic)
    openList = priority queue ordered by f value
    closedList = empty set
    g[start] = 0
    f[start] = heuristic(start, goal)
    parent[start] = null
    openList.add(start)

    while openList is not empty
        current = vertex in openList with lowest f value
        if current == goal then
            return reconstructPath(parent, goal)
        endif

        openList.remove(current)
        closedList.add(current)

        for each neighbour n of current
            if n in closedList then
                continue
            endif
            tentativeG = g[current] + weight(current, n)
            if n not in openList OR tentativeG < g[n] then
                parent[n] = current
                g[n] = tentativeG
                f[n] = g[n] + heuristic(n, goal)
                if n not in openList then
                    openList.add(n)
                endif
            endif
        next n
    endwhile
    return "No path found"
endfunction

---

Worked Example

Consider a graph where vertices represent locations on a map:

Vertices: S (start), A, B, C, G (goal)

Edges (with weights):
S -> A: 1    S -> B: 4
A -> B: 2    A -> C: 5
B -> G: 3
C -> G: 1