CQH103: What is a Heuristic?

You’ve seen us mention heuristics in our discussions of pathfinding (like A*) and optimization problems—but what exactly is a heuristic?

In short, a heuristic is a rule of thumb: a strategy for making decisions or estimates that are “good enough” for practical use, especially when an exact solution is too expensive or slow to compute.

Formal Definition

In algorithms, a heuristic is a function or method used to guide a search or estimate a value, usually with the goal of improving speed or performance.

It’s not guaranteed to be perfect, but it should be fast and helpful.

Where Have We Used Heuristics?

A* Search Algorithm: We use a heuristic to estimate the cost from a node to the goal. This helps prioritize which paths to explore first.
- Example: In a grid, we used Manhattan distance as a heuristic.
Greedy Algorithms: The greedy step is often guided by a heuristic—choosing what looks best now.
Backtracking with Pruning: Heuristics help decide which branches to try first (e.g., Sudoku solvers that prioritize the most constrained cell).

Heuristics in the Real World

Navigation apps estimate travel time based on speed limits, traffic, and distance.
Search engines rank results using heuristics like keyword density, link popularity, and recency.
Games use heuristics to choose the next best move based on board evaluation functions.

Good vs. Bad Heuristics

A good heuristic:

Gets you close to the goal fast
Never overestimates (if used in A*, it keeps the algorithm optimal)
Is quick to compute

A bad heuristic can:

Mislead your algorithm
Waste time exploring bad paths
Break correctness guarantees if assumptions are violated

Challenge Time! 🔍

Try implementing A* with both Manhattan and Euclidean distance. How does the behavior change?
In a greedy algorithm, experiment with different heuristics—do some choices give better or worse results?

Heuristics aren’t magic—but they’re often the key to solving hard problems fast. Use them wisely, and your algorithms will thank you!