A*
How do I find the cheapest path without exploring everywhere?
Orders the frontier by cost so far plus an estimate of what remains, so it heads for the goal like greedy search and still finds the cheapest path.
A* combines the two previous ideas. Each cell gets f = g + h. Here g is the exact cost from the start, which is what Dijkstra’s algorithm uses, and h is an estimate of the cost to the goal, which is what greedy search uses. It always expands the cell with the lowest f.
If h never overestimates the true remaining cost (an admissible heuristic), A* is optimal, and it expands far fewer cells than Dijkstra because cells that lead away from the goal get a high f and wait. The closer h is to the truth, the fewer cells it needs.
Multiplying h by a weight above 1 makes it greedier: faster, with a path that may be up to that factor longer than optimal. The demo has a slider for exactly this.
Loading the demo…
The grid with A* selected. Change the heuristic and its weight, then use “Compare all” to see how many cells each search expanded.
- 01Set g(start) = 0 and queue the start with f = h(start).
- 02Take the cell with the lowest f.
- 03If it is the goal, follow the stored parents back to the start.
- 04For each neighbour, work out g(cell) plus the step cost. If that beats the neighbour’s recorded g, store it, remember the parent and queue the neighbour with f = g + w · h.
- 05Repeat until the queue is empty.
function a_star(start, goal, h, w = 1):
g = {start: 0}
parent = {}
heap = [(w * h(start), start)]
while heap is not empty:
_, cell = heap.pop_min()
if cell == goal: return path_from(parent, goal)
for n, step in neighbours(cell):
new = g[cell] + step
if new < g.get(n, infinity):
g[n] = new
parent[n] = cell
heap.push((new + w * h(n), n))
return no_pathThe running time depends on the heuristic: with a perfect one it walks straight to the goal, with h = 0 it becomes Dijkstra’s algorithm. Memory is like Dijkstra’s.
- Optimal when the heuristic is admissible.
- Usually expands far fewer cells than Dijkstra.
- One weight trades path quality for speed.
- Needs a good heuristic for the problem.
- Memory grows with the frontier, like Dijkstra’s algorithm.
- Loses its guarantee once the weight is above 1.
- 01PathfindingFour heuristics (octile, Manhattan, Euclidean, Chebyshev) and a weight slider, with a count of the cells expanded.