Introduction
Uniform-cost search explores in every direction equally, like a ripple in a pond. A person planning a trip does better: they head roughly towards the destination. Informed search gives the algorithm that sense of direction with a heuristic, an estimate of the remaining cost. A* search, which combines the cost so far with the heuristic, is the standard algorithm for pathfinding in games, robots and maps.
How it works
A heuristic h(n) estimates the cheapest cost from state n to the goal. On a map it can be the straight-line distance; on a grid where you move in four directions it can be the Manhattan distance |row difference| + |column difference|.
Greedy best-first search expands the state with the smallest h(n). It rushes towards the goal and often finds a solution quickly, but it ignores how much the path has cost so far, so the solution can be expensive.
A* expands the state with the smallest
f(n) = g(n) + h(n)
where g(n) is the cost of the path found to n so far. f(n) estimates the cost of the best complete solution through n.
A heuristic is admissible if it never overestimates the real remaining cost. Then A* is optimal: when it takes the goal out of the frontier, no cheaper solution can exist, because every other path in the frontier already has an f value at least as large, and f never exceeds the true cost. A heuristic is consistent if, for every step from n to n′, h(n) ≤ cost(n, n′) + h(n′). With a consistent heuristic, A* never needs to expand a state twice.
Heuristics are often found by relaxing the problem: Manhattan distance is the exact cost if walls were removed; for the 8-puzzle, the number of misplaced tiles is the cost if a tile could jump anywhere. The closer an admissible heuristic is to the true cost, the fewer states A* expands; h = 0 turns A* back into uniform-cost search.
Syntax
heapq.heappush(frontier, (g + h(state), h(state), state)) # A*
heapq.heappush(frontier, (h(state), state)) # greedy
heapq.heappush(frontier, (g, state)) # uniform-cost
Example
import heapq
roads = {
"Home": {"Bridge": 4, "Market": 3},
"Bridge": {"Home": 4, "Station": 3, "Hill": 6},
"Market": {"Home": 3, "Station": 5, "Tunnel": 7},
"Station": {"Bridge": 3, "Market": 5, "Airport": 6},
"Hill": {"Bridge": 6, "Airport": 4},
"Tunnel": {"Market": 7, "Airport": 2},
"Airport": {"Station": 6, "Hill": 4, "Tunnel": 2},
}
straight_line = {"Home": 11, "Market": 9, "Bridge": 8, "Station": 5, "Hill": 4, "Tunnel": 2, "Airport": 0}
def search(start, goal, priority):
frontier = [(priority(0, start), start)]
best, parent, order, done = {start: 0}, {start: None}, [], set()
while frontier:
_, town = heapq.heappop(frontier)
if town in done:
continue
done.add(town)
order.append(town)
if town == goal:
break
for nxt, step in roads[town].items():
cost = best[town] + step
if nxt not in best or cost < best[nxt]:
best[nxt], parent[nxt] = cost, town
heapq.heappush(frontier, (priority(cost, nxt), nxt))
path = [goal]
while parent[path[-1]]:
path.append(parent[path[-1]])
return path[::-1], best[goal], order
strategies = [
("uniform-cost", lambda g, town: (g,)),
("greedy", lambda g, town: (straight_line[town],)),
("A*", lambda g, town: (g + straight_line[town], straight_line[town])),
]
for name, priority in strategies:
path, cost, order = search("Home", "Airport", priority)
print(f"{name}: {' -> '.join(path)}, cost {cost}")
print(f" expanded {len(order)}: {', '.join(order)}")Line by line
straight_lineis the heuristic: the straight-line distance to the Airport, which can never be longer than a road route.- One
searchfunction runs all three strategies; only the priority changes. - Greedy rushes to Bridge and Hill because they look closest, and returns a route costing 14.
- A* weighs cost and estimate, and finds the cheapest route, through Market and Tunnel, costing 12.
- Uniform-cost search finds the same route but expands 7 towns; A* expands 6, and on large maps the saving is far bigger.
Expected result
uniform-cost: Home -> Market -> Tunnel -> Airport, cost 12
expanded 7: Home, Market, Bridge, Station, Hill, Tunnel, Airport
greedy: Home -> Bridge -> Hill -> Airport, cost 14
expanded 4: Home, Bridge, Hill, Airport
A*: Home -> Market -> Tunnel -> Airport, cost 12
expanded 6: Home, Bridge, Station, Market, Tunnel, Airport
In the real world
A* moves characters in almost every video game, often on a grid or a navigation mesh. Robot planners and logistics systems use it with heuristics built from geography, and route planners combine it with precomputed data to answer queries in milliseconds. Variants such as weighted A* trade a little optimality for much more speed.
Common mistakes
- Using an overestimating heuristic and expecting optimal answers.
- Ordering the frontier by h alone when the cheapest solution is required.
- Stopping when the goal is first generated instead of when it is taken out of the frontier.
- Using Manhattan distance when diagonal moves are allowed, which can overestimate.
Best practices
- Check admissibility: for every state, h must be no more than the true remaining cost.
- Break ties between equal f values in favour of smaller h, which usually reaches the goal sooner.
- Compare expansions with h = 0 to measure how much the heuristic helps.
Summary
A heuristic estimates the remaining cost. Greedy best-first search follows it alone and can return expensive solutions; A* adds the cost so far, f = g + h, and with an admissible heuristic returns an optimal solution while expanding fewer states than uniform-cost search.
Quick check
Key takeaways
- Greedy search is fast but can return an expensive solution.
- A* with an admissible heuristic returns an optimal solution, usually expanding far fewer states than uniform-cost search.
- A better (larger but still admissible) heuristic means fewer expansions.
Practice problems for this lesson
My notes
Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.