The A* algorithm
Shortest-path search guided by an estimate: cost paid, estimate of the rest, open and closed lists, admissible and consistent heuristics, and what A* becomes with a zero heuristic (Dijkstra) or with the heuristic alone (greedy search).
- 26 cards
- 5 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Scenarios
A few cards from the deck
A* algorithm: what is it?
Show the answer
A shortest-path search that always expands the node with the smallest sum: cost already paid from the start plus estimated remaining cost.
The sum f(n) = g(n) + h(n) estimates the cost of the best path through n; with an admissible estimate, the path found when the goal leaves the open list is a shortest one.
A grid contains walls and moves go in the four directions, at cost 1. A* uses the Manhattan distance. Is the returned path a shortest one?
- Yes, because a wall can only lengthen the real path
- No, the Manhattan distance must count the walls to be admissible
- No, A* is optimal only on a grid with no obstacle at all
- Yes, but only if the goal is in the same row as the start
Show the answer
Yes, because a wall can only lengthen the real path
The Manhattan distance is the cost of a path with no walls, hence a lower bound on the real cost: it never overestimates, and walls do not make it inadmissible.
A* ranks nodes by f(n) = … + …, where g is the cost already paid from the start and h the estimate of the remaining cost.
Show the answer
A* ranks nodes by f(n) = g(n) + h(n), where g is the cost already paid from the start and h the estimate of the remaining cost.
g is known exactly; h is an estimate. Dropping g gives greedy search, dropping h gives Dijkstra.
Heuristic: what is it?
Show the answer
A quick-to-compute estimate of the cost remaining to the goal; it guides the search without guaranteeing the result on its own.
A good estimate avoids exploring cells that lead away from the goal. Its quality sets the time saved, and its properties decide whether the returned path is optimal.