A* (A-star)

A* (A-star) is an informed search algorithm that finds the least-cost path between a starting point and a goal in a graph. Peter Hart, Nils Nilsson and Bertram Raphael published it in 1968. It combines the best of two strategies: the optimality guarantee of uniform-cost search (Dijkstra's algorithm) and the speed of greedy search guided by a heuristic.

The formula

At each step, A* expands the node with the lowest value of f(n) = g(n) + h(n), where g(n) is the actual cost accumulated from the start to that node and h(n) is a heuristic estimate of the cost remaining to the goal. It thus balances what it has already cost to get there with what is estimated to remain. An example of a heuristic, on a map, is the straight-line distance to the destination.

When it guarantees the optimal path

A* finds the optimal path if the heuristic is admissible, that is, if it never overestimates the real remaining cost. With a consistent heuristic, a somewhat stronger condition, the guarantee also holds when nodes are reached again by different paths. Two limiting cases help to understand it: if the heuristic is always zero, A* reduces to Dijkstra's algorithm; and if it were perfect, it would go straight to the goal without exploring extra nodes.

Uses and limit

Its main limit is memory: it retains generated nodes and can exhaust it in large spaces. The least-cost guarantee depends on the conditions imposed on the heuristic.