Skip to content
learn
  1. Learn
  2. Artificial Intelligence
  3. Intelligent Agents and Problem Solving by Search

AI AI-01.04

Informed search and A*

Heuristics, greedy best-first search, A* with f = g + h, admissible and consistent heuristics, why A* is optimal, and where it runs today.

Intermediate 16 min Last reviewed

The big idea

Uniform-cost search is careful but blind. On the road map from the last lesson it expanded every one of the 11 towns before it was sure of the best route to Kingsport, including towns that lie in the opposite direction. A human planner would never do that. You glance at the map, see that Kingsport is to the east, and ignore the towns to the west unless the eastern roads turn out to be terrible.

That glance is a heuristicA function h(n) that estimates the cost of the cheapest path from state n to a goal. It is cheap to compute and need not be exact.: a quick, rough estimate of how far a state is from the goal. Informed searchSearch that uses a heuristic estimate of the remaining cost to decide which state to expand next. uses it to decide which state to expand next. The classic heuristic for maps is straight-line distance, the distance "as the crow flies". It is easy to compute, and no road can be shorter than it.

Think of hiking toward a peak you can see. You do not walk in every direction equally. You head toward the peak, but you also keep track of how far you have already walked, so you notice when a tempting shortcut has turned into a long detour. A* is exactly that balance, written as one line of arithmetic.

How it works

Step 1: Two numbers per state

For any state on the frontier, the search can know two things:

  • : the cost of the path from the start to that the search has found so far. This is a fact.
  • : the heuristic estimate of the cost from to the goal. This is a guess.

Uniform-cost search orders the frontier by alone. It knows where it has been but not where it is going. The next two algorithms add .

Greedy best-first searchInformed search that always expands the frontier state with the smallest heuristic value h(n), ignoring the cost already paid. orders the frontier by alone: always expand the state that looks closest to the goal. It is fast, often reaching the goal after very few expansions, but it ignores the cost already paid. Once it commits to a direction it keeps going, even if that direction turns out to be expensive. It is not optimal, and on graphs with dead ends it can wander a long way before backing out.

Step 3: A*, both numbers at once

A*Best-first search that expands the frontier state with the smallest f(n) = g(n) + h(n): cost so far plus estimated cost to go. (pronounced "A star") orders the frontier by

which is an estimate of the total cost of the cheapest solution that passes through . Everything else is the frontier loop from the last lesson: pop the state with the lowest , stop if it is the goal, otherwise expand it and push its successors with their own values.

Here is the road map again, with each town's straight-line distance to Kingsport, in km:

The road map with straight-line distances to Kingsport, and the routes found by greedy search and A* Eleven towns joined by roads with distances in km. Each town shows h, its straight-line distance to Kingsport: Ashford 324, Crane 205, Fairview 121, Glenn 168, Juniper 85 and so on. The A* route Ashford, Crane, Glenn, Juniper, Kingsport, 418 km, glows in the track colour. The greedy route Ashford, Crane, Fairview, Kingsport, 450 km, is drawn as a red dashed line. 75 140 118 71 151 99 80 111 160 146 97 138 211 101 Ashford h 324 Bexley h 387 Elmwood h 333 Dunmore h 423 Hollis h 338 Crane h 205 Fairview h 121 Glenn h 168 Ivy h 202 Juniper h 85 Kingsport goal Figure 1. Each town shows h, its straight-line km to Kingsport. Greedy search (red, dashed) follows the smallest h through Fairview and pays 450 km. A* (glowing) weighs road cost against h and finds the 418 km route.

Trace A* by hand. From Ashford, Crane has , far better than Bexley () or Dunmore (). Expanding Crane adds Fairview () and Glenn (). Fairview has the lower , so A* expands it and finds Kingsport at a total of 450, but it does not stop: 450 is only on the frontier, and Glenn's 388 is lower. Expanding Glenn and then Juniper () reaches Kingsport at 418. Now 418 is the smallest on the frontier, A* pops it, and stops. Six towns expanded instead of eleven, and the answer is still the cheapest.

Try it

This interactive needs JavaScript. The diagrams and text above cover the same idea.

The heuristic here is Manhattan distance: the number of horizontal plus vertical steps to the goal, ignoring walls and mud. Try this:

  1. Run Dijkstra (uniform-cost search on a graph) on the preset grid, then A*. Both find a path of cost 49, the cheapest, but A* expands 265 cells to Dijkstra's 347: it skips most of the area behind the start.
  2. Run Greedy. It expands only 82 cells, by far the fewest, but its path costs 53 because it ploughs straight through the mud that A* walks around.
  3. Press Clear grid and run all three again. Dijkstra floods about 300 cells; greedy and A* walk almost straight to the goal in about 24. With no obstacles, the heuristic is nearly perfect.

Step 4: The same idea in code

The road map, searched three ways. The only difference between the algorithms is the priority function:

astar.pyruns with python3 (standard library)
import heapq

# The road map from AI-01.03: town -> {neighbour: km}
ROADS = {
    "Ashford": {"Bexley": 75, "Crane": 140, "Dunmore": 118},
    "Bexley": {"Ashford": 75, "Elmwood": 71},
    "Crane": {"Ashford": 140, "Elmwood": 151, "Fairview": 99, "Glenn": 80},
    "Dunmore": {"Ashford": 118, "Hollis": 111},
    "Elmwood": {"Bexley": 71, "Crane": 151},
    "Fairview": {"Crane": 99, "Kingsport": 211},
    "Glenn": {"Crane": 80, "Juniper": 97, "Ivy": 146},
    "Hollis": {"Dunmore": 111, "Ivy": 160},
    "Ivy": {"Hollis": 160, "Glenn": 146, "Juniper": 138},
    "Juniper": {"Glenn": 97, "Ivy": 138, "Kingsport": 101},
    "Kingsport": {"Fairview": 211, "Juniper": 101},
}
# h(n): straight-line km from each town to Kingsport. Roads are never shorter.
STRAIGHT = {"Ashford": 324, "Bexley": 387, "Crane": 205, "Dunmore": 423,
            "Elmwood": 333, "Fairview": 121, "Glenn": 168, "Hollis": 338,
            "Ivy": 202, "Juniper": 85, "Kingsport": 0}

def search(start, goal, priority):
    frontier, done = [(priority(0, start), 0, [start])], []
    while frontier:
        _, g, path = heapq.heappop(frontier)
        town = path[-1]
        if town in done:
            continue
        done.append(town)
        if town == goal:
            return path, g, done
        for nxt, km in ROADS[town].items():
            if nxt not in done:
                heapq.heappush(frontier, (priority(g + km, nxt), g + km, path + [nxt]))

ALGOS = {
    "UCS    f = g    ": lambda g, n: g,                # cost so far only
    "Greedy f = h    ": lambda g, n: STRAIGHT[n],      # guess to go only
    "A*     f = g + h": lambda g, n: g + STRAIGHT[n],  # both
}
for name, f in ALGOS.items():
    path, km, done = search("Ashford", "Kingsport", f)
    print(f"{name}: {' -> '.join(path)}")
    print(f"{'':18}{km} km, expanded {len(done)}: {', '.join(done)}")

Output

UCS    f = g    : Ashford -> Crane -> Glenn -> Juniper -> Kingsport
                  418 km, expanded 11: Ashford, Bexley, Dunmore, Crane, Elmwood, Glenn, Hollis, Fairview, Juniper, Ivy, Kingsport
Greedy f = h    : Ashford -> Crane -> Fairview -> Kingsport
                  450 km, expanded 4: Ashford, Crane, Fairview, Kingsport
A*     f = g + h: Ashford -> Crane -> Glenn -> Juniper -> Kingsport
                  418 km, expanded 6: Ashford, Crane, Fairview, Glenn, Juniper, Kingsport

Uniform-cost search expands all 11 towns. Greedy reaches Kingsport after 4, through Fairview, at 450 km. A* expands 6 and returns the 418 km route.

Going deeper

Admissible heuristics, and why A* is optimal

A heuristic is admissibleA heuristic that never overestimates the true cheapest cost from a state to the goal: h(n) is at most h*(n) for every n. if it never overestimates: , where is the true cheapest cost to the goal. Straight-line distance is admissible because no road is shorter than a straight line. Manhattan distance on a four-direction grid is admissible because every step moves at most one cell closer.

With an admissible heuristic, A* (as tree search) is optimal. The argument is short. Suppose A* is about to return a goal reached at cost that is worse than the optimal cost . Some state on the optimal path must still be on the frontier, and for it

So has a lower than the bad goal and would have been popped first. A* never pops a suboptimal goal while a piece of the optimal path is still waiting. That is exactly what happened at Fairview in the trace: the 450 km goal sat on the frontier while 388 and 402 were expanded ahead of it.

Consistent heuristics

A heuristic is consistentA heuristic for which h(n) is at most c(n, n') + h(n') for every action from n to n'. Consistent heuristics are also admissible. (or monotone) if for every action from to with cost ,

It is a triangle inequality: the estimate cannot drop by more than the cost of the step you take. On the map, Crane has and Glenn , and the road between them is 80 km, so holds. Consistency matters for graph search with an explored set: it guarantees that never decreases along a path, so the first time A* expands a state it has already found the cheapest way there and never needs to reopen it. Every consistent heuristic is admissible, and most natural admissible heuristics, such as straight-line and Manhattan distance, are also consistent.

Better heuristics, fewer expansions

If everywhere, A* is uniform-cost search. If , the perfect heuristic, A* walks straight down the optimal path. Between those, a larger admissible heuristic is better: if for every state, dominatesh2 dominates h1 when h2(n) is at least h1(n) for every state n. An A* search with the dominating admissible heuristic never expands more states. , and A* with never expands more states. For the 8-puzzle, "number of misplaced tiles" and "sum of each tile's Manhattan distance to its home" are both admissible, and the second dominates the first and solves puzzles with far fewer expansions.

A good way to invent heuristics is to solve a relaxed problem, one with some rules removed. Manhattan distance is the exact cost of a grid with the walls removed; straight-line distance is the exact cost if you could drive anywhere. The relaxed problem is easier, and because it removes constraints its cost can never exceed the real one.

Bending the guarantee

Weighted A*A* with the heuristic multiplied by a weight w greater than 1. Faster, and the path found costs at most w times the optimum when h is admissible. uses with . It behaves more greedily and expands fewer states, and with an admissible its path is guaranteed to cost at most times the optimum. Games and robots often accept a 10 or 20 percent worse path to answer within a frame. A* also stores every frontier state, so on very large problems memory runs out first; iterative-deepening A* (IDA*) trades time for memory the same way iterative deepening did in Uninformed search: BFS, DFS, uniform cost .

Trade-offs

OptionWins whenLoses when
Uniform-cost (Dijkstra) You have no useful heuristic, or you need costs to many destinations at once Expands in every direction, including away from the goal
Greedy best-first Any reasonable path will do and it must be found with very little work Not optimal; can be lured into long detours and dead ends
A* with an admissible h You need the cheapest path and can estimate the distance to the goal Memory: it keeps the whole frontier; weak heuristics save little
Weighted A* Real-time settings where a slightly worse path is fine Optimality, bounded by the weight w

Common mistakes

  • Stopping when the goal is generated rather than when it is expanded. In the trace, Kingsport first appears at 450 km; stopping there returns the wrong route.
  • Using a heuristic that overestimates, such as road distance times a fudge factor, and still calling the result optimal.
  • Mixing units: a heuristic in km with step costs in minutes is neither admissible nor meaningful.
  • Using Manhattan distance on a grid that allows diagonal moves. A diagonal step covers two Manhattan units at a cost of about 1.4, so the heuristic overestimates.
  • Expecting A* to be fast with a weak heuristic. With close to 0 it does about as much work as Dijkstra, plus the cost of computing .

In the wild

Where you will see this: route planners in navigation apps build on A* and its descendants, often with precomputed landmarks or shortcuts that make the heuristic much stronger than straight-line distance. Video games use A* on grids and navigation meshes to move characters around obstacles, often in its weighted form. Robot motion planners, puzzle solvers and some program-synthesis and theorem-proving systems use the same ordering, with heuristics that are sometimes learned by a neural network instead of hand-written.

Check yourself

  1. A* orders its frontier by which quantity?

    Show answer

    C. g(n) + h(n) f = g + h estimates the total cost of the best solution through n. g alone is uniform-cost search, h alone is greedy.

  2. On a grid with only up, down, left and right moves, each costing 1, which heuristic is admissible?

    Show answer

    B. Manhattan distance Each move changes the Manhattan distance by at most 1, so the true cost is at least that distance. Doubling or squaring it can overestimate.

  3. A* first finds a goal on the frontier with f = 450, while another frontier state has f = 388. What should it do?

    Show answer

    B. Expand the f = 388 state first A goal is only accepted when it is popped as the lowest f. With an admissible h, the 388 state might lead to a cheaper solution, and here it does: 418.

  4. Heuristic h2 is admissible and h2(n) >= h1(n) for every n. Which is true?

    Show answer

    B. A* with h2 never expands more states than with h1 Both give optimal paths. The larger estimate is closer to the true cost, so it prunes more of the frontier.

  5. Why might a game use weighted A* with f = g + 1.5h?

    Show answer

    C. It expands fewer states, with a path at most 1.5 times the optimum Weighting h makes the search greedier and faster, and with an admissible h the cost of the path is bounded by the weight.

Recap

  • A heuristic h(n) is a cheap estimate of the remaining cost; straight-line and Manhattan distance are the classics.
  • Greedy best-first expands the lowest h: fast, but not optimal.
  • A* expands the lowest f = g + h and stops only when a goal is popped from the frontier.
  • With an admissible h (never overestimates), A* finds the cheapest path; consistency lets graph search skip reopening states.
  • Stronger admissible heuristics, often from relaxed problems, mean fewer expansions.

Get new lessons by email

Get new posts on backend and AI internals. No spam, unsubscribe anytime.

Your email is only used to send new posts. Privacy