liveBook · Manning

Heuristic

As explained in Algorithms Every Programmer Should Know

An estimate used to guide choices in a search or optimization problem.

A heuristic is a quick estimate used to guide a search. In A*, h(n) estimates the cost from a node to the goal; an admissible heuristic never overestimates that cost, preserving the shortest-path guarantee while influencing which nodes are explored first. section 12.1 section 12.4

The estimate depends on the problem:

  • For A*, straight-line distance can estimate road distance; Manhattan distance estimates movement on a four-direction grid. section 12.1
  • In ant colony optimization, the heuristic represents a path’s immediate desirability, often measured as the inverse of its distance; pheromone records past success. section 8.4

Choosing a grid estimate

On a grid where movement is only horizontal or vertical, Manhattan distance adds the horizontal and vertical separation from a node to the goal. It is admissible because no route can cover that displacement in fewer moves. section 12.1

Table 12.1 Common admissible heuristics
Problem Domain
Heuristic h(n)
Why it never overestimates
Road network routing
Euclidean Distance (Straight Line)
A road can only be longer than a straight line between two points, never shorter
Grid-based movement (4 directions)
Manhattan Distance
No sequence of horizontal/vertical moves can cover the required displacement in fewer steps
Grid-based movement (8 directions, diagonals allowed)
Chebyshev Distance
A diagonal move covers one unit of both axes at once, so this is the true minimum move count on an open grid.
Sliding-tile puzzle
Sum of each tile Manhattan distance from its goal position
Every tile must travel at least that many rows and columns, even if no tile were in the way.

Compare admissible estimates for road routing, grid movement, and sliding-tile puzzles. section 12.1

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines cheap estimates, explains admissibility and its shortest-path guarantee, and distinguishes consistency as a stronger property.
Examples
Uses straight-line road distance, Manhattan grid distance, sliding-tile displacement, and inverse-distance path desirability.
What you can do after
Understand how admissible estimates guide shortest-path search and how local desirability informs probabilistic ant choices.
How it connects
Connects informed search with A* and Dijkstra, and pairs ant colony optimization heuristics with pheromone.

Also explained in

Compare how 12 books explain heuristic →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.