liveBook · Manning

Informed search

As explained in Algorithms Every Programmer Should Know

Informed search is a search strategy that uses an estimate of remaining cost to guide which candidate to explore next.

When a route finder searches a city map, checking streets equally in every direction wastes effort. Informed search uses an estimate of the remaining cost to favor nodes closer to the destination. section 12.1

A* uses two costs to guide that search:

  • g(n) is the actual cost paid to reach node n; h(n) estimates the cost still ahead. A* selects the node with the smallest f(n) = g(n) + h(n). section 12.4
  • The heuristic must be admissible: it cannot overestimate the true remaining cost. This preserves A*’s guarantee of finding a shortest path. section 12.1
  • A* does not stop just because it first discovers the goal; it waits until the goal is the lowest-priority node in the queue. section 12.4

A route through six intersections

In a worked map, A* first finds a route to the goal costing 11. It continues searching, then finds a route through D costing 10 and returns S → B → D → G. section 12.4

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 heuristic choices for roads, grid movement, and sliding-tile puzzles. section 12.4

How Algorithms Every Programmer Should Know covers it

How deep it goes
Works through A* scores, queue updates, pseudocode, and complexity, including why the search continues after first finding the goal.
Examples
Uses road routing, grid movement, sliding-tile puzzles, and a six-intersection graph to illustrate heuristic choices and A*.
What you can do after
Build it from scratch by implementing A* with a priority queue, path costs, heuristic estimates, and parent pointers.
How it connects
Connects informed search to A*, Dijkstra’s algorithm, heuristics, admissibility, consistency, and IDA*.

Also explained in

Compare how 3 books explain informed search →

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.