4

I'm quite sure the * (star) in the A* algorithm means that the algorithm is admissible, i.e. it is guaranteed that it finds the shortest path in the graph if this path exists (when the heuristic employed is optimistic).

Am I right? I was unsuccessfully looking for any info about the topic but I couldn't find any reference. Hopefully, most experienced users in this community know something else about the history of A* than I do.

By the way, I think that other algorithms like IDA*, D*, SMA*, MOA*, NAMOA*, ... that are based on A* follow the same name convention.

Kedar Mhaswade
  • 4,535
  • 2
  • 25
  • 34
FrankS101
  • 2,112
  • 6
  • 26
  • 40

1 Answers1

7

The reason is that scientists first came up with an improved version of the Dijkstra algorithm they called A1. Later on, the inventors of A* discovered an improvement of A1 that they called A2. These people then managed to prove that A2 was actually optimal under some assumptions on the heuristic in use. Because A2 was optimal, it was renamed A*. In science, and in optimisation in particular, a " * " symbol is often used to denote optimal solutions. Some also interpret the " * " as meaning "any version number" since it was proven impossible to build an "A3" algorithm that would outperform A2/A*.

By the way, in this context, "optimal" doesn't mean that it reaches the optimal solution, but that it does so while exploring the minimum number of nodes. Of course, A* is also complete, which means it reaches the optimal solution (if we use an admissible heuristic).

francoisr
  • 4,407
  • 1
  • 28
  • 48
  • 1
    I have also read this entry from the Wikipedia: https://en.wikipedia.org/wiki/A*_search_algorithm. I was particularly looking for a reference to this name convention (in a research paper or prestigious source). – FrankS101 Mar 09 '16 at 15:57
  • 1
    Digging a bit, I found this post that may interest you: http://stackoverflow.com/a/29470434/2174693 – francoisr Mar 10 '16 at 10:49
  • 1
    Thanks. I see that my question is a duplicate of that one. The funny thing is that the accepted answer is quoting a published paper. The authors of that paper cited the Wikipedia to introduce the paragraph in their text. So who wrote that in the Wikipedia in the first place? Maybe it was Hart, maybe were that authors before the paper, who knows ... – FrankS101 Mar 10 '16 at 11:39
  • 1
    https://en.wikipedia.org/w/index.php?title=A*_search_algorithm&dir=prev&action=history - okay, SO comment formatting doesn't like that * in the URL, so you'll have to cut and paste it. :/ – beaker Mar 10 '16 at 21:39
  • 1
    The first mention I find of the meaning of the * is in this 19 March 2006 edit by Qwertyus: https://en.wikipedia.org/w/index.php?title=A*_search_algorithm&oldid=44552281 diff: https://en.wikipedia.org/w/index.php?title=A*_search_algorithm&diff=prev&oldid=44552281 – beaker Mar 10 '16 at 21:49