A* Search

Originally published in 1968 by Hart, Nilsson, and Raphael,2 the well-known A* search algorithm is a foundational pathfinding algorithm in computer science and artificial intelligence (AI) for traversing trees and graphs. The method provides the optimal path from the initial state to the target goal state, given the use of an admissible heuristic (must not overestimate the remaining distance to the goal). The A* algorithm is included in nearly all AI textbooks and courses worldwide. Given its widespread fame, however, there is no reliably documented evidence as to the origin of the name "A*": What does it really stand for and what does it mean? This Communications Viewpoint answers the question.