Search & Planning10 min read

Heuristic Search

Use smart guesses to search faster
scope:Core Conceptdifficulty:Beginner

The Compass in the Maze

Remember our maze from state space search? BFS and DFS are blind — they don't know which direction the exit is. They just explore systematically and hope for the best.

Now imagine you have a compass that always points toward the exit. You still can't see through walls, but you have a sense of direction. When you reach a fork, you pick the path that feels closer to the goal.

That compass is a heuristic — an educated guess about how close you are to the solution. It doesn't guarantee you're right, but it dramatically speeds up the search.

What Exactly is a Heuristic?

A heuristic is a function h(n) that estimates the cost from a node n to the goal. It's not exact — it's an approximation. For example:

  • GPS navigation: the straight-line distance to your destination (ignoring roads)
  • Sliding puzzle: how many tiles are in the wrong position
  • Chess: the total value of your pieces minus your opponent's pieces

The key insight: a good heuristic doesn't need to be perfect. It just needs to point you in roughly the right direction. Even a mediocre compass is better than no compass at all.

Greedy Best-First Search

The simplest heuristic search is Greedy Best-First Search. At every step, it picks the node that looks closest to the goal according to the heuristic. It's fast, but it can be fooled — like following a compass straight into a wall.

A* Search: The Gold Standard

A* (A-star) is the most famous heuristic search algorithm. It combines two pieces of information:

  • g(n) — the actual cost to reach node n from the start
  • h(n) — the estimated cost from n to the goal (the heuristic)

A* picks the node with the lowest f(n) = g(n) + h(n). This balances "how far I've come" with "how far I think I have left."

The magic of A*: if your heuristic never overestimates the true cost (we call this admissible), A* is guaranteed to find the shortest path. You get the optimality of BFS with the speed of a heuristic. Best of both worlds.

A* Search Implementation

import heapq


def a_star(graph, start, goal, h):
    """A* search using a heuristic function h."""
    # Priority queue: (f_score, node, path, g_score)
    open_set = [(h(start), start, [start], 0)]
    visited = set()
    
    while open_set:
        f, node, path, g = heapq.heappop(open_set)
        
        if node == goal:
            print(f"Found path with cost {g}")
            return path
        
        if node in visited:
            continue
        visited.add(node)
        
        for neighbor, cost in graph[node]:
            if neighbor not in visited:
                new_g = g + cost
                new_f = new_g + h(neighbor)
                heapq.heappush(open_set, (new_f, neighbor, path + [neighbor], new_g))
    
    return None


# Graph: node -> [(neighbor, cost), ...]
city_map = {
    'Home':    [('Cafe', 2), ('Park', 5)],
    'Cafe':    [('Library', 3), ('Park', 2)],
    'Park':    [('Library', 1), ('Office', 6)],
    'Library': [('Office', 2)],
    'Office':  []
}


# Heuristic: straight-line estimate to Office
estimate = {'Home': 7, 'Cafe': 5, 'Park': 4, 'Library': 2, 'Office': 0}


path = a_star(city_map, 'Home', 'Office', lambda n: estimate[n])
print("Path:", path)
Output
Found path with cost 7
Path: ['Home', 'Cafe', 'Library', 'Office']
Note: Admissible means never overestimate: A heuristic is admissible if it never overestimates the true cost. Straight-line distance is admissible for road navigation because you can never drive less than the straight-line distance. If your heuristic overestimates, A* might miss the optimal path — so choosing a good heuristic is an art.

Where A* Shows Up in Real Life

A* is one of the most widely used algorithms in the world:

  • Video games — every time an NPC walks around obstacles to reach you, that's A*.
  • GPS apps — Google Maps and Waze use variants of A* to find the fastest route.
  • Robotics — robots use A* to plan paths around furniture, people, and other obstacles.
  • Puzzle solvers — A* can solve sliding puzzles, mazes, and even Rubik's Cubes efficiently.

The beauty of A* is that it's simple, optimal, and flexible. Change the heuristic, and the same algorithm works for completely different problems.

Quick check

What does A* combine to decide which node to explore next?
Challenge

Continue reading