Informed Search
Give the search a sense of direction. Using a heuristic to head toward the goal leads to greedy search and the most famous algorithm in AI: A star.
Last week's blind searches had one glaring weakness: they had no idea where the goal was, so they explored in every direction equally. Informed search fixes that. It uses a heuristic, a quick, rough estimate of how far each state is from the goal, to explore promising directions first. This one addition takes us from wandering to purposeful searching, and gives us A star, the algorithm behind game pathfinding, route planners, and countless real systems.
From blind to informed
Uniform cost search, from last week, always expands the cheapest node so far. It is optimal, but it has no sense of direction: it spreads outward in every direction equally, wasting huge effort exploring away from the goal. Imagine looking for a friend's house by walking down every street the same distance in all directions, even the ones pointing the wrong way.
A human would not do that. You would head roughly toward where you think the house is. That rough sense of "which way is the goal" is exactly what a heuristic gives an algorithm. Informed search is simply uninformed search plus a heuristic to prefer promising directions.
What a heuristic is
A heuristic function, written h(n), estimates the cost from a state to the goal. It is a guess, not a guarantee, and it must be cheap to compute, otherwise you spend more time estimating than searching. The art of informed search is choosing a good heuristic.
Two heuristics you must know:
- Straight-line (Euclidean) distance: for maps, the direct as-the-crow-flies distance to the goal. You cannot usually travel in a straight line, but it never overestimates the real road distance.
- Manhattan distance: for grids where you move up, down, left, and right, the number of horizontal plus vertical steps to the goal, ignoring walls. Perfect for tile puzzles and grid maps.
h(n) ignores obstacles and detours on purpose, to stay fast. A wall might make the true distance far longer than the heuristic says. That is fine, as long as the estimate never overshoots the real cost, a property we make precise in section 5.
Greedy best-first search
The simplest way to use a heuristic is to trust it completely: always expand the node that looks closest to the goal, the one with the smallest h(n). This is greedy best-first search.
Greedy search is fast and often heads straight for the goal. But it is short-sighted. It only ever looks at how far it still has to go, and completely ignores how much it has already spent getting there. So it can charge toward the goal down a path that turns out to be a long, expensive detour, and it will not notice.
| Property | Greedy best-first |
|---|---|
| Uses | Only h(n), the estimated cost to the goal |
| Complete | No, it can get stuck in loops without checks |
| Optimal | No, it ignores the cost already paid |
| Speed | Usually fast, expands few nodes |
The fix is almost obvious once you see the flaw: do not only look ahead, also account for what you have already spent. That is A star.
A star search
A star (written A*) is the most important search algorithm in AI, and it comes from one beautifully simple idea: balance the cost so far against the estimated cost to come. For each node it computes:
A star always expands the node with the smallest f(n). That single rule combines the strengths of both earlier algorithms: like uniform cost search it respects the real cost paid (g), and like greedy search it aims toward the goal (h). The result is an algorithm that heads in the right direction without being fooled by expensive detours.
h is zero, A star becomes uniform cost search. If g is ignored, it becomes greedy search. A star is the balance between them.
Admissible heuristics
A star is only guaranteed to find the optimal path if its heuristic is admissible. An admissible heuristic never overestimates the true cost to the goal. It is allowed to guess low, but never high.
The reason is intuitive. If h never overestimates, then A star can never be tricked into ignoring a path that is actually cheap, because it will never wrongly believe a good path is expensive. Straight-line distance is admissible for maps, and Manhattan distance is admissible for grids, which is exactly why they are the standard choices.
You are searching a map. A node N is 5 km from the start along the roads you took, and the straight-line distance from N to the goal is 8 km.
Watch them pathfind
This is where it clicks. Below is a grid with a start on the left, a goal on the right, and walls in between. Switch between greedy and A star, then run the search and watch which cells each one explores and the path it returns. Greedy rushes the goal and can be led astray, A star explores a little more but guarantees the shortest path.
Manhattan distance is the heuristic. Amber cells are on the frontier, indigo cells have been expanded, and the green line is the final path.
The comparison table
| Algorithm | Ranks nodes by | Complete | Optimal | Notes |
|---|---|---|---|---|
| Uniform cost (week 2) | g(n) | Yes | Yes | No direction, explores everywhere |
| Greedy best-first | h(n) | No | No | Fast but short-sighted |
| A star | f(n) = g(n) + h(n) | Yes | Yes, if h is admissible | The balanced, trusted choice |
Notice how A star sits exactly between the other two. Set h to zero and you are back to uniform cost search. Ignore g and you have greedy search. A star is not a separate idea so much as the right combination of the two you already know.
Key points and practice
- A heuristic
h(n)estimates the remaining cost to the goal and points the search in the right direction. - Greedy best-first uses only
h: fast, but not complete or optimal. - A star uses
f = g + h: optimal wheneverhis admissible. - An admissible heuristic never overestimates the true cost.
- With
h = 0, A star is uniform cost search; ignoringg, it is greedy search.
A star ranks nodes by f(n) = g(n) + h(n). Here g(n) is the actual cost of the path from the start to node n, and h(n) is the heuristic estimate of the cost from n to the goal. f(n) is therefore the estimated total cost of a path that goes through n, and A star always expands the node with the smallest f.
An admissible heuristic never overestimates the true cost to reach the goal. It matters because A star is only guaranteed to find the optimal path when its heuristic is admissible. If the heuristic overestimates, A star may wrongly reject the best path and return a suboptimal one.
Greedy search ranks nodes only by h(n), the estimated distance still to go, and ignores g(n), the cost already paid. So it can commit to a path that looks close to the goal but is actually a long detour. A star adds g(n), so it accounts for the real cost of each path and will not be fooled by an expensive route that merely looks close.
