Heuristics
A heuristic is a practical strategy that finds good solutions quickly without any guarantee of optimality or worst-case quality.
What a heuristic is
A heuristic is a rule of thumb that trades guarantees for practicality. It aims for good-enough solutions to hard problems in reasonable time, accepting that it may sometimes produce poor results. Unlike an approximation algorithm, it carries no proven quality bound.
Why they are used
Many real problems are NP-hard, yet decisions must still be made. Heuristics deliver usable answers fast and often perform far better on typical inputs than the worst case would suggest. They are the workhorses of routing, scheduling, and search when exact methods are too slow.
Common families
- Greedy: make the locally best choice at each step
- Local search: start with a solution and improve by small changes
- Simulated annealing: allow occasional worse moves to escape local optima
- Genetic algorithms: evolve a population of candidate solutions
- Nearest-neighbor and insertion rules for routing
The local optimum trap
Many heuristics can get stuck at a local optimum: a solution better than all its neighbors but worse than the global best. Techniques like random restarts, annealing, and tabu search exist specifically to escape these traps, though none guarantees finding the global optimum.
Heuristics in search
In pathfinding, a heuristic estimates the remaining distance to the goal, guiding algorithms like A* toward promising directions. If the estimate never overshoots the true cost (an admissible heuristic), A* still returns the exact shortest path, showing heuristics and guarantees can sometimes combine.
Judging a heuristic
Because heuristics lack worst-case guarantees, they are judged empirically: run them on representative instances and measure quality and speed. A heuristic that is excellent on your real data may be worthless on adversarial inputs, so honest evaluation matters more than for provably bounded methods.