Making of “Introduction to A*” • Hacker News Board

Re: Making of “Introduction to A*”

#11

Post by unwind » Mon, Oct 13, 2014, 10:08 AM UTC

userbinator wrote: post #7

"A* " may be one of the most un-Google-able algorithm names I've come across, since the {asterisk} is used as a wildcard too. (Edit: and is significant for formatting here too.) As of this post, Googling "A* algorithm" gives more relevant hits about the algorithm than the experience I had many years ago when I tried to learn about it, but it still uses * as a wildcard so you get various other algorithm pages mixed in…

It was first published in 1968 (not sure if the name was established then, didn't read the paper) but there's a paper with "A*" in the title from 1985 too. I'm pretty sure "being easy to Google" wasn't a goal with naming things, back then. :)

Re: Making of “Introduction to A*”

#12

Post by nerdy » Mon, Oct 13, 2014, 11:10 AM UTC

You might recognize this as being similar to the Stanford page but a slightly different header:

http://theory.stanford.edu/~amitp/GameProgramming/AStarCompa...

The Stanford page links to a redblobgames e-mail so it's probably the same person

Re: Making of “Introduction to A*”

#13

Post by glenra » Mon, Oct 13, 2014, 4:50 PM UTC

unwind wrote: post #11

userbinator wrote: post #7

"A* " may be one of the most un-Google-able algorithm names I've come across, since the {asterisk} is used as a wildcard too. (Edit: and is significant for formatting here too.) As of this post, Googling "A* algorithm" gives more relevant hits about the algorithm than the experience I had many years ago when I tried to learn about it, but it still uses * as a wildcard so you get various other algorithm pages mixed in…

It was first published in 1968 (not sure if the name was established then, didn't read the paper) but there's a paper with "A*" in the title from 1985 too. I'm pretty sure "being easy to Google" wasn't a goal with naming things, back then. :)

The name was established in 1968. The relevant wiki page is:

http://en.wikipedia.org/wiki/A*_search_algorithm

Peter Hart (one of the three co-authors of the paper) discusses naming on the talk page, to wit:

> In response to this question about why it's called A* : The notation is borrowed from the statistical literature. Statisticians use a hat (also called a circumflex) to indicate an estimate for a quantity, and often use a star to indicate an estimate that's optimal with respect to a stated criterion (like, say, a minimum variance criterion). When I (Peter E. Hart) was developing this algorithm and especially the theory behind it with my colleagues Nils Nilsson and Bertram Raphael, we adopted this traditional notation. We used hats to indicate estimates of heuristic functions, and went on to compare any other algorithm, call it A, with our provably-optimal (by the criterion of number of nodes expanded) A*. Hart 02:16, 7 March 2006 (UTC)