algorithmgraph-algorithmdijkstrashortest-patha-star

AStar - explanation of name


I am looking for an explanation why the AStar / A* algorithm is called AStar. All similar (shortest path problem) algorithms are often named like its developer(s), so what is AStar standing for?


Solution

  • There were algorithms called A1 and A2. Later, it was proved that A2 was optimal and in fact also the best algorithm possible, so he gave it the name A* which symbolically includes all possible version numbers.

    Source:

    In 1964 Nils Nilsson invented a heuristic based approach to increase the speed of Dijkstra's algorithm. This algorithm was called A1. In 1967 Bertram Raphael made dramatic improvements upon this algorithm, but failed to show optimality. He called this algorithm A2. Then in 1968 Peter E. Hart introduced an argument that proved A2 was optimal when using a consistent heuristic with only minor changes. His proof of the algorithm also included a section that showed that the new A2 algorithm was the best algorithm possible given the conditions. He thus named the new algorithm in Kleene star syntax to be the algorithm that starts with A and includes all possible version numbers or A*

    Nosrati, Masoud, Ronak Karimi, and Hojat Allah Hasanvand. "Investigation of the * (star) search algorithms: Characteristics, methods and approaches." World Applied Programming 2.4 (2012): 251-256.