Sign In

Communications of the ACM


A* Search: What's in a Name?

A and asterisk, illustration

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

Log in to Read the Full Article

Sign In

Sign in using your ACM Web Account username and password to access premium content if you are an ACM member, Communications subscriber or Digital Library subscriber.

Need Access?

Please select one of the options below for access to premium content and features.

Create a Web Account

If you are already an ACM member, Communications subscriber, or Digital Library subscriber, please set up a web account to access premium content on this site.

Join the ACM

Become a member to take full advantage of ACM's outstanding computing information resources, networking opportunities, and other benefits.

Subscribe to Communications of the ACM Magazine

Get full access to 50+ years of CACM content and receive the print version of the magazine monthly.

Purchase the Article

Non-members can purchase this article or a copy of the magazine in which it appears.
Sign In for Full Access
» Forgot Password? » Create an ACM Web Account