A* search

A delivery app planning a route across a city map can score each partial route by the distance already driven plus the straight-line distance still left to the destination. Straight-line distance is never longer than the real road distance, so it is a safe heuristic: A* explores the most promising routes first and still ends with a shortest route. Peter Hart, Nils Nilsson and Bertram Raphael introduced the algorithm in 1968.

Textbooks write the score as f(n) = g(n) + h(n), where g is the cost from the start to point n and h is the estimate from n to the goal. With h set to zero, A* spreads out evenly in every direction like uniform-cost search. A better-informed estimate that still never overestimates lets it skip more of the map. An estimate that sometimes overestimates may finish faster, but it can return a route that is not the cheapest. When the search can reach the same point by different routes, the estimate also needs to be consistent, or the search has to revisit points when it finds a cheaper way to them.

A* is classical search, not machine learning: nothing is trained from data. It needs a problem that can be described as states, moves with known costs and a usable estimate, which is why it shows up in games, robot navigation and planning software. It also keeps every route it is still considering in memory, which can become the limit on very large problems.