🎓 A1Learner
🔍
0 of 93 lessons completed

DSA A* Search, Surveyed

A* search is Dijkstra's algorithm aimed by an estimate of the distance still to go. The estimate never overstates the true remaining cost, so the shortest path guarantee survives.

Manhattan distance

The estimate ignores obstacles and counts only row and column steps. The start cell sits six steps from the goal by this measure.

def manhattan(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])


goal = (2, 6)
for cell in [(2, 0), (0, 0), (4, 6), (2, 6)]:
    print(cell, "estimate:", manhattan(cell, goal))

The f score

Both cells on the middle row score an f of 6 here. The row 0 cell scores 10, so the heap serves it later.

def manhattan(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])


goal = (2, 6)
rows = [((2, 3), 3), ((0, 3), 5), ((2, 5), 5)]
for cell, g in rows:
    h = manhattan(cell, goal)
    print(cell, "g:", g, "h:", h, "f = g + h:", g + h)

Ties leave in push order

Each heap entry stores the f value, a counter and the cell. The counter breaks the tie before any cells are compared.

import heapq

heap = []
counter = 0
for entry in [(6, (2, 5)), (6, (2, 4)), (10, (0, 3))]:
    heapq.heappush(heap, (entry[0], counter, entry[1]))
    counter += 1
print("equal f values leave in push order:")
while heap:
    print(heapq.heappop(heap))

Example

import heapq

GRID = [
    ".......",
    ".......",
    ".......",
    ".......",
    ".......",
]
START = (2, 0)
GOAL = (2, 6)


def manhattan(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])


def search(use_heuristic):
    g = {START: 0}
    came = {START: None}
    counter = 0
    heap = [(0, counter, START)]
    visited = 0
    while heap:
        _, _, cell = heapq.heappop(heap)
        visited += 1
        if cell == GOAL:
            break
        r, c = cell
        for nxt in [(r - 1, c), (r, c + 1), (r + 1, c), (r, c - 1)]:
            nr, nc = nxt
            if not (0 <= nr < 5 and 0 <= nc < 7):
                continue
            if GRID[nr][nc] == "#":
                continue
            new_g = g[cell] + 1
            if nxt not in g or new_g < g[nxt]:
                g[nxt] = new_g
                came[nxt] = cell
                counter += 1
                h = manhattan(nxt, GOAL) if use_heuristic else 0
                heapq.heappush(heap, (new_g + h, counter, nxt))
    path = []
    cell = GOAL
    while cell is not None:
        path.append(cell)
        cell = came[cell]
    path.reverse()
    return visited, g[GOAL], path


d_visited, d_cost, _ = search(False)
a_visited, a_cost, a_path = search(True)
print("Dijkstra visited:", d_visited, "path cost:", d_cost)
print("A* visited:", a_visited, "path cost:", a_cost)
print("A* path:", a_path)
print("nodes saved:", d_visited - a_visited)

Key points

  • A heuristic is an estimate of the remaining cost from a node to the goal.
  • The Manhattan distance between two cells adds the row gap and the column gap.
  • An admissible heuristic is a heuristic that never overestimates the true remaining cost.
  • The letter g names the exact cost already paid from the start.
  • A* ranks each cell by f, which is g plus the heuristic value.
  • Heap entries carry a push counter, so equal f values leave in push order.

In this example, both searches find a path of cost 6 across the open grid. Dijkstra's search pops 27 cells before it reaches the goal. The A* search pops only the 7 cells of the path itself, saving 20 visits. The two counts are the evidence that aiming the search works.

Note

with the heuristic set to zero everywhere, A* becomes Dijkstra's algorithm exactly.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

A heuristic overestimates the true remaining cost for one cell. What can happen?