Textbook of AI

Also known as: A*, A-star

A* ("A-star") is the best-first graph-search algorithm introduced by Peter Hart, Nils Nilsson and Bertram Raphael in 1968. It maintains a priority queue of frontier nodes ordered by the function f(n) = g(n) + h(n), where g(n) is the actual cost from the start node to n along the best path found so far, and h(n) is a heuristic estimate of the remaining cost from n to a goal.

A* is provably optimal, guaranteed to find a minimum-cost path, whenever the heuristic h is admissible (never overestimates the true remaining cost). It is complete on finite graphs and on infinite graphs with positive edge costs. With a consistent heuristic (h satisfies the triangle inequality h(n) ≤ c(n, n′) + h(n′) for every successor n′), A* never re-expands a node and runs in time proportional to the number of nodes expanded.

A* generalises Dijkstra's algorithm (which is A* with h(n) = 0) and best-first greedy search (which is A* with g(n) = 0). Variants extend it: IDA* uses iterative deepening to bound memory; D* and LPA* support replanning when the graph changes; bidirectional A* searches simultaneously from start and goal; weighted A* trades optimality for speed by inflating h.

A* is the workhorse of robotics path planning, computer-game AI (every video-game NPC's pathfinding), GPS route planning, and many AI search problems including theorem proving, puzzle solving and operations-research applications. Modern neural-network-guided search systems (AlphaGo, AlphaZero) generalise the f = g + h decomposition: g comes from the prior, h from a learned value function.