Communications of the ACM
A* Search: What's in a Name?
Credit: Andrij Borys Associates
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.
At Ohio State University, we offer a specialty course on AI designed for non-computer science students1 (due to the large interest and demand in AI from multiple disciplines). During the course offering this year while teaching the A* algorithm, a student raised his hand and asked: "What does A* stand for?". Out of all my years teaching AI, I have never been asked that question! I realized I did not know the answer myself, and therefore would need to seek the explanation. After an exhaustive search online (including reading the original publication2) and a thorough inspection of the classic AI textbooks on my bookshelf, I could not find a definitive answer. During the next class, I stated the lack of evidence available and therefore put out a challenge to the class to see if anyone could find a credible source for the answer.
No entries found