A* Search

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.

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.

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.

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.