Definition
A maps app finds the fastest route across a city of a million road segments in a fraction of a second. It cannot check every road. It uses a sense of direction: roads heading towards your destination are tried first.
Informed search uses a heuristic function h(n), an estimate of the cost from a state to the goal, to explore promising states first. A* search expands the state with the lowest f(n) = g(n) + h(n), where g(n) is the cost so far. If the heuristic is admissible, never overestimating the true remaining cost, A* is guaranteed to find an optimal path, usually exploring far fewer states than uninformed search.
In simple words
To walk to a temple you can see on a hill, you naturally head towards it. That sense of "how far is it from here?" is a heuristic. A* combines how far you have already walked with how far the temple still looks, and always continues from the spot where that total is smallest.
Overview
- Informed (heuristic) search uses an estimate of the distance to the goal to search more efficiently.
- A heuristic h(n) estimates the cost from node n to the goal; g(n) is the cost so far.
- A* expands the node with the lowest f(n) = g(n) + h(n).
- If h never overestimates (admissible), A* is guaranteed to find an optimal solution.
- A* was published by Hart, Nilsson and Raphael in 1968 for the Shakey robot.
- Better heuristics expand fewer nodes; a perfect heuristic would walk straight to the goal.
Why it matters
A* is one of the most used algorithms in AI and computing: route planning, robot navigation, video-game characters, puzzle solving and many planning systems rely on it. Designing good heuristics is a core skill in classical AI.
Key terms
- Heuristic h(n)
- An estimate of the remaining cost from state n to the goal.
- g(n)
- The actual cost of the path from the start to n.
- f(n) = g(n) + h(n)
- The estimated total cost of a path through n.
- Admissible heuristic
- One that never overestimates the true remaining cost.
- Greedy best-first search
- Expands the state with the lowest h(n) only; fast but not optimal.
- Manhattan distance
- The sum of horizontal and vertical distances; a common grid heuristic.
Types
Several informed search algorithms exist, and heuristics themselves come in types. These are the main ones.
1. Greedy best-first search
Expanding the node that looks closest to the goal by h(n) alone.
- How it works: It ignores the cost already paid, so it is fast but not optimal and can be misled by dead ends.
- Example: Driving towards whichever junction is closest to the destination as the crow flies, even if the road loops back.
- When to use it: Use it when a quick, good-enough path matters more than the best path.
2. A* search
Best-first search ordered by f(n) = g(n) + h(n).
- How it works: It balances the cost so far with the estimated cost remaining; with an admissible and consistent heuristic it is complete and optimal.
- Example: Map apps and game characters finding shortest paths around obstacles.
- When to use it: Use it as the standard choice for shortest-path problems where a good heuristic exists.
3. Memory-bounded variants (IDA* and beam search)
Versions of heuristic search that limit memory.
- How it works: IDA* runs depth-first searches with an increasing f-limit; beam search keeps only the k best nodes at each level, losing optimality.
- Example: Language models use beam search with k = 4 or 5 to choose likely word sequences.
- When to use it: Use them when A*'s memory use is too large for the problem.
4. Admissible and consistent heuristics
Admissible heuristics never overestimate the true cost; consistent ones also satisfy h(n) ≤ cost(n, n′) + h(n′).
- How it works: Straight-line distance is admissible for road travel because no road is shorter than a straight line; consistency makes A* never revisit nodes.
- Example: For the 8-puzzle, the number of misplaced tiles and the Manhattan distance of tiles are both admissible.
- When to use it: Use them whenever you need guaranteed optimal paths from A*.
5. Relaxed-problem and learned heuristics
Heuristics built by solving an easier version of the problem, or learned from data.
- How it works: Removing a rule, such as letting tiles pass over each other, gives an easier problem whose exact cost is an admissible heuristic; pattern databases and neural networks can also estimate costs.
- Example: Manhattan distance comes from relaxing "tiles may only slide into the blank" to "tiles may move to any neighbour".
- When to use it: Use relaxation to design heuristics systematically, and learned heuristics for very large domains.
Explained in detail
Why combine g and h?
Uniform-cost search uses only g(n), the cost so far, so it spreads out evenly in all directions, wasting effort on paths heading away from the goal. Greedy best-first search uses only h(n), rushing towards the goal, but it can be lured down a path that looks close but turns out long. A*, published by Peter Hart, Nils Nilsson and Bertram Raphael at the Stanford Research Institute in 1968 for the Shakey robot project, balances both. A path is promising if it is cheap so far and looks close to the goal. When h is admissible, A* never rejects the optimal path, because its estimated total can never look worse than its true cost.
Good heuristics
| Problem | Heuristic | Why it is admissible |
|---|---|---|
| Road route between cities | Straight-line distance to the destination | No road can be shorter than a straight line |
| Grid moves up, down, left, right | Manhattan distance | Each move covers at most one row or column |
| 8-puzzle | Sum of each tile's Manhattan distance to its target | Each move shifts one tile one square |
| Any problem | h = 0 | Trivially admissible, but A* becomes uniform-cost search |
Among admissible heuristics, larger is better: a heuristic closer to the true cost prunes more states. A common way to invent one is to solve a relaxed version of the problem, ignoring some rule. Ignoring walls gives the Manhattan distance; ignoring that tiles block each other gives the 8-puzzle heuristic.
A* in practice
- On a grid with obstacles, A* with Manhattan distance typically explores a narrow band towards the goal rather than the whole map.
- Its weakness is memory: it keeps every frontier state. Variants such as IDA* and weighted A* trade optimality or speed for memory.
- Large-scale route planners add pre-processing, such as precomputed shortcuts between important junctions, so queries take milliseconds.
- Video games have used A* for decades to move characters around obstacles.
Tie-breaking matters too: when several states have the same f, preferring the one with the smaller h, the one closer to the goal, avoids exploring many equally promising states and makes A* much faster on open maps, as the example below shows.
How it works
- Formulate the problem with step costs.
- Design an admissible heuristic, often by relaxing a rule.
- Keep a priority queue ordered by f = g + h.
- Repeatedly expand the lowest-f state, updating g for cheaper paths found.
- Stop when the goal is removed from the queue; its path is optimal.
In code
import heapq
grid = [
"S...............",
"................",
"..........#.....",
"..........#.....",
"..........#.....",
"..........#.....",
"...............G",
]
rows, cols = len(grid), len(grid[0])
find = lambda ch: next((r, c) for r in range(rows) for c in range(cols) if grid[r][c] == ch)
start, goal = find("S"), find("G")
def neighbours(r, c):
for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "#":
yield nr, nc
def search(heuristic):
frontier, g, expanded = [(heuristic(start), heuristic(start), 0, start)], {start: 0}, 0
while frontier:
f, h, cost, node = heapq.heappop(frontier) # ties broken by smaller h
if cost > g[node]:
continue
expanded += 1
if node == goal:
return cost, expanded
for nxt in neighbours(*node):
if cost + 1 < g.get(nxt, float("inf")):
g[nxt] = cost + 1
h_next = heuristic(nxt)
heapq.heappush(frontier, (cost + 1 + h_next, h_next, cost + 1, nxt))
manhattan = lambda n: abs(n[0] - goal[0]) + abs(n[1] - goal[1])
print("Uniform-cost (h = 0): path length %d, states expanded %d" % search(lambda n: 0))
print("A* (Manhattan): path length %d, states expanded %d" % search(manhattan))Output
Uniform-cost (h = 0): path length 21, states expanded 108 A* (Manhattan): path length 21, states expanded 22
Try it yourself
Heading for the temple
A pilgrim crosses a town of winding lanes towards a hilltop temple.
Admissible or not?
For shortest road distance between cities, is each heuristic admissible?
Actual road distance plus 10 km
Zero
Straight-line distance
Twice the straight-line distance
Common mistakes
- Using an overestimating heuristic and assuming the result is optimal.
- Using greedy best-first search when the shortest path matters.
- Forgetting A*'s memory demands on very large problems.
Check yourself
Summary
- Informed search uses a heuristic estimate of the remaining cost.
- A* expands the lowest g + h and is optimal with an admissible heuristic.
- Good heuristics come from relaxed problems and dramatically reduce the states explored.
Read it. Now try it yourself.
Open the interactive activityFinished reading?
Sources: Red Blob Games: Introduction to the A* algorithm · Russell and Norvig, Artificial Intelligence: A Modern Approach (4th edition)