A heuristic algorithm finds a good-enough solution to a problem quickly, without guaranteeing the mathematically perfect answer. Heuristics are essential when a problem is too complex to solve exactly in a reasonable time — including route planning, scheduling, and game artificial intelligence.
Why do some problems need heuristics?
Consider the travelling salesman problem (TSP): a delivery driver must visit ten towns and return home — what is the shortest possible route? With ten towns there are 10! ÷ 2 = 1,814,400 possible routes to check. With 20 towns the number exceeds 60 quadrillion. Even a modern processor checking a billion routes per second would take longer than the age of the universe to check them all.
Problems like TSP are classified as computationally intractable — they belong to a category where the time to find the exact solution grows so rapidly with input size that brute-force checking becomes impossible. For these problems, the practical answer is: find a solution that is good enough, fast enough, using a heuristic.
What exactly is a heuristic?
The word "heuristic" comes from the Greek heuriskein — to discover. In computer science, a heuristic is any strategy that:
- Finds a solution quickly (polynomial time, not exponential)
- Usually finds a good solution, but does not guarantee the optimal one
- Is informed by domain knowledge or clever observation about the problem structure
Think of it as an expert's rule of thumb rather than a guaranteed proof. A chess engine cannot evaluate every possible game — it uses heuristics (prefer controlling the centre; protect the king; prioritise material advantage) to estimate which moves are promising.
How does a nearest-neighbour heuristic work for TSP?
The nearest-neighbour heuristic is one of the simplest approaches to TSP:
- Start at any town.
- At each step, travel to the nearest unvisited town.
- After visiting all towns, return to the start.
| Step | Current town | Nearest unvisited | Distance |
|---|---|---|---|
| Start | A | — | 0 |
| 1 | A | C (12 km) | 12 |
| 2 | C | B (8 km) | 20 |
| 3 | B | D (15 km) | 35 |
| 4 | D | Return to A (10 km) | 45 |
This produces a route in O(n²) time — far faster than checking all n! possibilities. However, it is not guaranteed to be the shortest route. Depending on the town layout, it may produce a route 20–25% longer than the true optimum.
What are the properties of a good heuristic?
| Property | Description |
|---|---|
| Admissibility | Never overestimates the cost to reach the goal (important in pathfinding) |
| Consistency | The estimate is always consistent with the actual costs along any path |
| Efficiency | Runs in polynomial time, not exponential |
| Quality | Produces solutions close to optimal in practice |
In pathfinding algorithms such as A*, a heuristic function estimates the distance from the current node to the goal. Using straight-line distance ("as the crow flies") as the heuristic is admissible because the actual road distance is always at least as long. This guides the search towards the goal efficiently without guaranteeing absolute optimality.
How are heuristics used in real systems?
Heuristics are everywhere in practical computing:
Route planning (satnavs) — Google Maps does not evaluate every road in the country for every journey. It uses heuristic search to find a near-optimal route within milliseconds.
Spam filters — rules such as "if the subject line is all uppercase and contains 'FREE MONEY', increase spam score" are heuristics: fast, usually correct, occasionally wrong.
Game AI — a chess engine evaluating millions of positions per second uses heuristic evaluation functions to score board positions without exploring to the end of every game.
Compiler optimisation — deciding which variables to store in CPU registers is an NP-hard problem; compilers use heuristics to make good decisions quickly.
Scheduling — hospital appointment scheduling and university timetabling use heuristic search because finding the perfect schedule is computationally intractable.
How do heuristics compare with exact algorithms?
Exact algorithm: Guarantees the optimal answer.
May be too slow for large inputs (exponential time).
Example: brute-force TSP, Bellman-Ford.
Heuristic: Does NOT guarantee the optimal answer.
Fast even for large inputs (polynomial time).
Example: nearest-neighbour TSP, A* pathfinding.
The trade-off is accuracy for speed. For intractable problems, heuristics are not a compromise — they are the only viable option.
Frequently asked questions
What is the difference between a heuristic and a greedy algorithm?
All greedy algorithms can be considered heuristics (they make locally optimal choices without backtracking), but not all heuristics are greedy. A heuristic is any rule of thumb that finds a good-enough answer quickly. A greedy algorithm specifically always picks the locally best option at each step. Heuristics can involve backtracking, randomisation, or other strategies that a pure greedy approach does not use.
Do GCSE students need to know specific heuristic algorithms?
AQA and OCR specifications require students to understand what a heuristic is and why heuristics are used for computationally intractable problems. You should be able to explain the concept, give an example (such as nearest-neighbour TSP or A* search), and justify why an exact algorithm is impractical for the same problem. You do not need to memorise complex heuristic implementations.
Why can a heuristic solution sometimes be good enough?
In practice, a 5% longer delivery route or a slightly suboptimal schedule is often perfectly acceptable if it is produced in a millisecond rather than computed exactly over months. The cost of a slightly worse solution is small compared with the benefit of having any usable answer quickly. For real-time applications like route planning or game AI, heuristics are the only feasible approach.
Is a heuristic the same as an approximation algorithm?
Not exactly. An approximation algorithm provides a provable guarantee — for example, "this algorithm always finds a solution within 10% of the optimal". A heuristic provides no such guarantee; it may find the optimal answer on some inputs and a poor answer on others. Approximation algorithms are mathematically rigorous; heuristics are practical strategies with empirically good performance.
Struggling to explain heuristics in your own words? Professor Turing at aitutors.me uses the Socratic method to build your understanding step by step.