A* search
Dijkstra with a sense of direction. To each place’s cost it adds an estimate of the cost still to go, so it tries first the places that look closest to the goal.
- time O((V + E) log V)
- space O(V)
- uses a priority queue
What do these mean?
- Cost: what a move costs. On the maze, stepping onto ground costs 1, onto mud 3 and into water 9; on the graph, the number on the edge.
- Priority queue: a waiting line where the cheapest one goes first, not the one that came first.
- Estimate (h): a guess of the cost still to go. A* stays exact only if the guess is never too high.
- Relaxing an edge: checking whether going through the current place gives a neighbour a cheaper cost, and taking it if it does.
- in the queue
- current
- done
- cheapest way
- ground · 1
- mud · 3
- water · 9
- wall
New: Start at A1 with cost 0 and an estimate of 26 to the goal. It is the only one in the queue.
Space: play or pause. Left and right arrows: step. Home and End: jump.
Try this: Pick the open field and switch between Dijkstra and A*: both find a way of the same cost, but A* takes far fewer cells off the queue.
How it works
A* works like Dijkstra, but orders the queue by f = cost so far + h, where h estimates the cost still to go. On the maze h is the number of moves to M, ignoring walls and mud; on the graph it is the straight-line distance divided by 10. As long as h never guesses too high, the way A* has when it takes the goal is the cheapest one, exactly as with Dijkstra. The better the estimate, the fewer places it has to look at.
When it is a good choice
Use A* when you look for one goal and can estimate how far it is: pathfinding in games, robots, route planners on a map. With h = 0 it is exactly Dijkstra. An estimate that can guess too high makes A* faster but may cost you the cheapest way.