A* search with an admissible heuristic

Guide search toward the goal with a heuristic and compare how many cells it expands against uniform-cost search.

Python

import heapq

GRID = [
    "S.......",
    "........",
    "..####..",
    "........",
    "........",
    ".......G",
]


def find(symbol):
    for r, row in enumerate(GRID):
        if symbol in row:
            return (r, row.index(symbol))


START, GOAL = find("S"), find("G")


def manhattan(cell):
    return abs(cell[0] - GOAL[0]) + abs(cell[1] - GOAL[1])


def search(heuristic):
    frontier = [(heuristic(START), heuristic(START), 0, START)]
    best = {START: 0}
    expanded = 0
    while frontier:
        _, _, cost, cell = heapq.heappop(frontier)
        if cost > best[cell]:
            continue
        expanded += 1
        if cell == GOAL:
            return cost, expanded
        r, c = cell
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < len(GRID) and 0 <= nc < len(GRID[0]) and GRID[nr][nc] != "#":
                new_cost = cost + 1
                if new_cost < best.get((nr, nc), 10**9):
                    best[(nr, nc)] = new_cost
                    h = heuristic((nr, nc))
                    heapq.heappush(frontier, (new_cost + h, h, new_cost, (nr, nc)))
    return None


print(search(manhattan))
print(search(lambda cell: 0))

Output

(12, 13)
(12, 44)

Explanation

Uninformed search explores in every direction. Informed search uses a heuristic function h(n), an estimate of the remaining cost from a state n to the goal. A* orders its frontier by f(n) = g(n) + h(n), where g(n) is the cost of the best path found so far. It always expands the state with the lowest estimated total cost.

A* returns an optimal solution when h is admissible: it never overestimates the true remaining cost. For graph search the heuristic should also be consistent, meaning h(n) <= cost(n, n') + h(n') for each step. On a grid where you move in four directions at cost 1, the Manhattan distance |dx| + |dy| is both admissible and consistent, because every move can reduce it by at most 1. With h = 0, A* becomes uniform-cost search, the Dijkstra-style algorithm for non-negative costs.

The program searches an 8 by 6 grid with a wall. Both searches find the optimal cost of 12, but A* expands 13 cells while uniform-cost search expands 44, because the heuristic steers it toward the goal. When several states have the same f, the program prefers the one with smaller h, which makes the search dive toward the goal. The program skips outdated heap entries instead of removing them, a common technique with Python's heapq.

Explore the dry run

Guided walkthroughReady

1import heapq

3GRID = [

4 "S.......",

5 "........",

6 "..####..",

7 "........",

8 "........",

9 ".......G",

10]

13def find(symbol):

14 for r, row in enumerate(GRID):

15 if symbol in row:

16 return (r, row.index(symbol))

19START, GOAL = find("S"), find("G")

22def manhattan(cell):

23 return abs(cell[0] - GOAL[0]) + abs(cell[1] - GOAL[1])

26def search(heuristic):

27 frontier = [(heuristic(START), heuristic(START), 0, START)]

28 best = {START: 0}

29 expanded = 0

30 while frontier:

31 _, _, cost, cell = heapq.heappop(frontier)

32 if cost > best[cell]:

33 continue

34 expanded += 1

35 if cell == GOAL:

36 return cost, expanded

37 r, c = cell

38 for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):

39 if 0 <= nr < len(GRID) and 0 <= nc < len(GRID[0]) and GRID[nr][nc] != "#":

40 new_cost = cost + 1

41 if new_cost < best.get((nr, nc), 10**9):

42 best[(nr, nc)] = new_cost

43 h = heuristic((nr, nc))

44 heapq.heappush(frontier, (new_cost + h, h, new_cost, (nr, nc)))

45 return None

48print(search(manhattan))

49print(search(lambda cell: 0))

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
The heuristic is the straight-line grid distance to the goal, ignoring walls. It never overestimates, so it is admissible.	`—`	—
The priority is f = g + h, with ties broken toward the smaller h.	`f = cost so far + estimate`	—
A* finds the optimal cost 12 after expanding only 13 cells.	`f = cost so far + estimate`	(12, 13)
With h = 0 it is uniform-cost search: the same optimal cost, but 44 cells expanded.	`f = cost so far + estimate`	(12, 13) (12, 44)

Cost and common mistakes

Worst-case time and memory are exponential in the solution depth, O(b^d). A good heuristic reduces the effective branching factor, and the cost with h = 0 is O((V + E) log V) with a binary heap.

A heuristic that overestimates can make A* return a non-optimal path. Check admissibility before trusting the result.
A* can use a lot of memory because it stores every generated state. Variants such as IDA* trade time for memory.
Counts of expanded cells depend on tie-breaking, but the optimal cost does not.

Try it yourself

Is the heuristic 2 × Manhattan distance admissible on this grid?

Reveal answer and reasoning

No. It overestimates the true cost of an unobstructed path, which is exactly the Manhattan distance, so A* with it could return a non-optimal solution.

A* search with an admissible heuristic

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading