---
title: 'A* Search'
source: 'https://academia.sh/en/courses/algorithms/a-star-search'
course: Algorithms
language: en
updated: '2026-08-17T18:07:36+00:00'
license: 'CC BY-SA 4.0'
---

# A* Search

Target-directed search with a heuristic function, admissibility and consistency conditions, the relation to Dijkstra, and the gain in expanded vertex count.

The previous two algorithms computed distance from the source to **every** vertex.
This is wasteful if a specific target is the goal: vertices in the opposite direction
from the target are processed with the same care.

A* reduces this waste by folding an estimate of where the target lies into the search.

## The Evaluation Function

Two quantities are kept for each vertex:

- $g(v)$ — the best known cost from the source to `v` (the distance in Dijkstra's
  algorithm).
- $h(v)$ — the **estimated** remaining cost from `v` to the target; it comes from
  knowledge of the problem.

The search proceeds by their sum:

$$
f(v) = g(v) + h(v)
$$

$f(v)$ is the estimated total cost of a solution passing through `v`. The priority
queue orders not by distance but by this value; everything else is the same as
Dijkstra's algorithm.

```python
import heapq


def a_star(graph: dict[str, list[tuple[str, int]]],
           start: str, target: str, h: dict[str, int]) -> float | None:
    g: dict[str, float] = {start: 0}
    open_set: list[tuple[float, float, str]] = [(h[start], 0, start)]
    closed: set[str] = set()

    while open_set:
        _, cost, vertex = heapq.heappop(open_set)
        if vertex in closed:
            continue
        closed.add(vertex)
        if vertex == target:
            return cost
        for neighbor, weight in graph[vertex]:
            new_cost = cost + weight
            if new_cost < g.get(neighbor, float("inf")):
                g[neighbor] = new_cost
                heapq.heappush(open_set, (new_cost + h[neighbor], new_cost, neighbor))
    return None
```

If $h(v) = 0$ for every vertex, $f = g$ and the algorithm becomes exactly Dijkstra's
algorithm. A* is, in this sense, a generalization of Dijkstra: the heuristic is the
extra information added to the search.

## Admissibility

The heuristic cannot be arbitrary. Being **admissible** means it never **exceeds** the
true remaining cost at any vertex:

$$
h(v) \leq h^*(v)
$$

Here $h^*(v)$ is the true remaining cost. With an admissible heuristic, A* guarantees
that the first solution it finds is optimal.

Justification: when the target reaches the front of the queue, $f(\text{target}) =
g(\text{target})$. If a better solution existed, a vertex on that solution's path
would be in the queue, and — since estimates never overshoot — its $f$ value would be
smaller than the true total cost, so it would be popped before the target.

If the condition is violated, optimality is lost.

```python
graph = {
    "A": [("B", 1), ("C", 5)],
    "B": [("H", 10)],
    "C": [("H", 1)],
    "H": [],
}

overestimating = {"A": 0, "B": 1, "C": 10, "H": 0}     # C's estimate is far above the true value (1)
admissible = {"A": 6, "B": 10, "C": 1, "H": 0}

print(a_star(graph, "A", "H", overestimating))         # 11  — not optimal
print(a_star(graph, "A", "H", admissible))              # 6
print(a_star(graph, "A", "H", {v: 0 for v in graph}))   # 6   — Dijkstra
```

The overestimate causes the true shortest path through `C` (`A→C→H`, 6) to be pruned
away; the algorithm returns the `A→B→H` path (11) instead.

## Consistency

A stronger condition is **consistency**: for every edge `(v, w)`,

$$
h(v) \leq \text{weight}(v, w) + h(w)
$$

This is the heuristic's counterpart of the triangle inequality. A consistent heuristic
is admissible and additionally guarantees the following: when a vertex is closed, its
$g$ value is final, so no vertex is ever expanded twice.

With a heuristic that is admissible but not consistent, closed vertices may need to be
reopened; the algorithm still returns the optimal result, but does more work. Most
heuristics used in practice — straight-line distance on a plane, Manhattan distance on
a grid — are consistent.

## The Measured Gain

The gain shows up in the **number of expanded vertices**. In the grid below, every
step costs one unit; neighbors lie in four directions.

```python
def grid_search(grid: list[str], start: tuple[int, int],
                target: tuple[int, int], heuristic) -> tuple[int, int]:
    """(path cost, number of expanded vertices)"""
    g = {start: 0}
    open_set = [(heuristic(start, target), 0, start)]
    closed: set[tuple[int, int]] = set()
    count = 0

    while open_set:
        _, cost, vertex = heapq.heappop(open_set)
        if vertex in closed:
            continue
        closed.add(vertex)
        count += 1
        if vertex == target:
            return cost, count
        row, col = vertex
        for dr, dc in ((-1, 0), (0, -1), (0, 1), (1, 0)):
            r, c = row + dr, col + dc
            if 0 <= r < len(grid) and 0 <= c < len(grid[0]) and grid[r][c] != "#":
                new_cost = cost + 1
                if new_cost < g.get((r, c), float("inf")):
                    g[(r, c)] = new_cost
                    heapq.heappush(open_set, (new_cost + heuristic((r, c), target), new_cost, (r, c)))
    return -1, count


zero = lambda a, b: 0
manhattan = lambda a, b: abs(a[0] - b[0]) + abs(a[1] - b[1])

open_grid = ["." * 15 for _ in range(15)]
walled = ["".join("#" if (2 <= r <= 12 and c == 7) else "." for c in range(15))
          for r in range(15)]

print(grid_search(open_grid, (7, 1), (7, 13), zero))       # (12, 147)
print(grid_search(open_grid, (7, 1), (7, 13), manhattan))  # (12, 13)
print(grid_search(walled, (7, 1), (7, 13), zero))          # (24, 212)
print(grid_search(walled, (7, 1), (7, 13), manhattan))     # (24, 169)
```

On the open grid, A* follows the strip leading to the target and expands 13 vertices
instead of 147. The path cost is identical — the gain is not in correctness, but in
work spent.

On the walled grid, the gain erodes: Manhattan distance does not see the wall, so the
estimate stays far below the truth and the heuristic does not narrow the search
direction enough. **A heuristic's quality is measured by how close it comes to the
truth**; every point between $h = 0$ and $h = h^*$ lies somewhere between Dijkstra and
walking straight to the target.

## Trade-offs

**Memory.** A* stores every vertex in the open set; in large search spaces, memory is
as limiting as time. Variants that iterate by increasing depth ($O(b\,d)$ memory) solve
this problem at a cost.

**Deliberate overestimation.** Scaling the heuristic by a factor narrows the search
but breaks optimality; it is used knowing the solution found may be worse by that
factor. This is a reasonable trade-off when a fast answer is worth more than an
optimal one.

**The heuristic's own cost.** $h$ is computed for every vertex; an expensive heuristic
can take away more than the expansions it saves.

These trade-offs are the artificial-intelligence side of search, and together with
game trees they are the subject of the AI Engineering curriculum; they are
not treated here.

## Summary

- A* expands vertices by their $f(v) = g(v) + h(v)$ value; with $h = 0$ it reduces to
  Dijkstra's algorithm.
- An admissible heuristic never exceeds the true remaining cost and guarantees the
  solution found is optimal.
- A consistent heuristic satisfies the triangle inequality; no vertex is ever expanded
  twice.
- The gain shows up in the number of expanded vertices and is proportional to how
  close the heuristic is to the truth.
- Obstacles push the estimate further from the truth and reduce the gain.
- Memory use, deliberate overestimation, and the heuristic's own computational cost
  are the main trade-offs.

## Next Step

The question asked so far has been "what is the cheapest path between two vertices."
The next lesson changes the question: what is the cheapest set of edges connecting all
vertices to each other? The minimum spanning tree problem will establish the
correctness of a greedy choice on different grounds — the cut property.