A* Search

Peter Hart, Nils Nilsson & Bertram Raphael, 1968

Published in 1968 by Peter Hart, Nils Nilsson, and Bertram Raphael at Stanford Research Institute, A* combines the actual cost from the start (g) with a heuristic estimate to the goal (h) to guide its search. It expands the most promising node first, guaranteeing an optimal path when the heuristic is admissible. The visualization shows a grid with walls, the open frontier in light gold, explored cells in light teal, and the final shortest path highlighted in coral.