Heuristics and A*: A Smarter Guess

Dijkstra explores outward in all directions. But we often know where the goal is. Can we use that knowledge to search smarter?

Yes. That’s what A* does. It uses a heuristic - a cheap guess of the remaining distance to the goal - to focus the search.

What is a Heuristic?

A heuristic is a function h(n) that estimates the cost from node n to the goal. It’s a “cheap guess” that helps guide the search.

Key properties:

• Fast to compute - Should be much cheaper than actually finding the path
• Admissible - Never overestimates the true cost (for optimality)
• Informed - Should be reasonably accurate

Think of it like this: if you’re in New York and want to go to Los Angeles, a heuristic might estimate “at least 2,500 miles” (straight-line distance). That’s cheap to compute and gives you a sense of direction.

Common Heuristics for Grids

Manhattan Distance

For 4-direction movement (up, down, left, right):

h(n) = |x_goal - x_n| + |y_goal - y_n|

Example: If goal is at (5, 7) and current node is at (2, 3):

• h = |5 - 2| + |7 - 3| = 3 + 4 = 7

This is admissible - you can’t get there faster than the Manhattan distance (can’t move diagonally).

Euclidean Distance

For 8-direction movement (includes diagonals):

h(n) = √((x_goal - x_n)² + (y_goal - y_n)²)

Example: If goal is at (5, 7) and current node is at (2, 3):

• h = √((5-2)² + (7-3)²) = √(9 + 16) = √25 = 5

This is also admissible for diagonal movement.

Zero Heuristic

h(n) = 0

This turns A* into Dijkstra! When h(n) = 0, A* behaves exactly like Dijkstra.

How A* Works

A* is almost identical to Dijkstra, with one key difference:

Dijkstra: Priority = g(n) = known cost from start to n A:* Priority = f(n) = g(n) + h(n) = known cost + estimated remaining cost

That’s it. Instead of prioritizing by distance from start, A* prioritizes by distance from start plus estimated distance to goal.

A* Algorithm

function astar(graph, start, goal, heuristic):
    g = map with all nodes → infinity  // known cost from start
    g[start] = 0
    
    f = map with all nodes → infinity  // g + h
    f[start] = heuristic(start, goal)
    
    parents = empty map
    visited = empty set
    queue = priority queue containing (f[start], start)
    
    while queue is not empty:
        current_f, current = queue.pop()
        
        if current in visited:
            continue
        
        visited.add(current)
        
        if current == goal:
            return reconstruct_path(parents, start, goal)
        
        for neighbor, edge_weight in graph.neighbors(current):
            if neighbor in visited:
                continue
            
            new_g = g[current] + edge_weight
            new_f = new_g + heuristic(neighbor, goal)
            
            if new_f < f[neighbor]:
                g[neighbor] = new_g
                f[neighbor] = new_f
                parents[neighbor] = current
                queue.push((new_f, neighbor))
    
    return null

The only difference from Dijkstra: we use f = g + h instead of just g for the priority.

Why A* is Usually Faster

A* focuses exploration toward the goal:

Dijkstra exploration:

    [ ][ ][ ][ ]
  [ ][ ][ ][ ][ ]
[ ][ ][S][ ][ ][ ]
  [ ][ ][ ][ ][ ]
    [ ][ ][G][ ]

Explores in all directions equally.

A exploration:*

        [ ][ ]
      [ ][ ][ ]
    [ ][S][ ][ ]
      [ ][ ][G]

Focuses toward the goal, exploring fewer nodes.

Visualizing Heuristics

Here’s a grid showing how A* uses heuristics. The algorithm explores cells with lower f(n) = g(n) + h(n) values first:

Side-by-Side Comparison

See how Dijkstra and A* differ in the number of nodes they explore:

Notice how A* usually explores fewer nodes. It focuses toward the goal instead of exploring all directions.

Admissible Heuristics

For A* to guarantee optimal paths, the heuristic must be admissible:

Admissible: h(n) ≤ true cost from n to goal (never overestimates)

Why it matters: If the heuristic overestimates, A* might skip the optimal path.

Examples:

• Manhattan distance on a 4-direction grid: ✅ Admissible
• Euclidean distance on an 8-direction grid: ✅ Admissible
• Manhattan distance × 2: ❌ Not admissible (overestimates)

Key Takeaways

Before moving forward:

1. Heuristic = cheap guess - Estimates remaining cost to goal
2. A = Dijkstra + heuristic* - Uses f(n) = g(n) + h(n) instead of just g(n)
3. Usually faster - Focuses search toward goal
4. Still optimal - With admissible heuristic
5. Heuristic quality matters - Better heuristics = fewer nodes explored

Quick Check

What’s Next?

Now that you understand both algorithms, let’s compare them directly. When should you use Dijkstra vs A*? We’ll explore the trade-offs in the next page.