Heuristic Search

Heuristic search, or informed search, is a family of algorithms that explores a state space using a heuristic function—an estimate of the cost remaining to reach the goal—to head toward the most promising regions, instead of exploring blindly. That function brings knowledge of the problem: on a map, for example, the straight-line distance to the destination.

The algorithms, with their notation

Greedy best-first search is guided only by the heuristic, f(n) = h(n): it is fast, but does not guarantee finding the best path. The A* (A-star) algorithm combines the cost already traveled with the estimate of what remains: f(n) = g(n) + h(n), where g(n) is the actual cost accumulated from the start and h(n) the estimate to the goal. With this it guarantees the optimal path if the heuristic is admissible, that is, if it never overestimates the real cost. There are variants such as IDA*, which uses far less memory, or weighted A*, which sacrifices optimality for speed.

Not to be confused with metaheuristics

Classic heuristic search should be distinguished from the optimization metaheuristics, such as simulated annealing, genetic algorithms or tabu search. Although both use the word “heuristic” in a broad sense, they are different things: informed search traverses a state space guided by h(n), whereas metaheuristics explore a space of candidate solutions—often stochastically—to approximate an optimum when exact search is infeasible, with no guarantee of optimality.

What it is for

Heuristic search underpins automated planning, route computation and navigation—A* is the standard in video games and GPS systems—and the solving of puzzles such as the 15-puzzle or the Rubik's cube. It is a search technique, distinct from other areas of artificial intelligence with which it is sometimes conflated.