A* algorithm
A pathfinding algorithm combining actual cost from start with estimated cost to goal (heuristic). A* finds optimal paths efficiently by prioritizing promising directions. Heuristic quality affects performance.
Formula
f(n) = g(n) + h(n)
Real World
Google Maps uses A* with straight-line distance as its heuristic to find the fastest driving route, exploring far fewer roads than Dijkstra's algorithm would by prioritising directions toward the destination.
Exam Focus
Define g(n) and h(n) explicitly; state that an admissible heuristic guarantees the optimal path is found.
How well did you know this?