30

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?

lale liley
  • 333
  • 3
  • 8
  • 3
    How about wikipedia's [history section](http://en.wikipedia.org/wiki/A*_search_algorithm#History)? – greybeard Apr 06 '15 at 11:31
  • 1
    I think, this section is not complete in its describtion how/why it comes to A"Star". compare: answer of jkbot, – lale liley Apr 06 '15 at 12:43

1 Answers1

35

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.

Akiva Weinberger
  • 103
  • 4
Jakub Kotowski
  • 7,411
  • 29
  • 38
  • 2
    "...includes all possible version numbers...", thank u very much for that – lale liley Apr 06 '15 at 12:44
  • 1
    Their stated source for this information is [Wikipedia's article on A*](https://en.wikipedia.org/wiki/A*_search_algorithm); however, [the claim that the star refers to all possible version numbers was removed from that article](https://en.wikipedia.org/w/index.php?title=A*_search_algorithm&diff=584905561&oldid=584901498) as it lacked a citation. – reinierpost Jul 23 '18 at 09:04