Article title
Someone moved this from A Star Search algorithm, but it should be located at A Star search algorithm since "Star" is part of the title. It is usually written A*, but pronounced like the title of the article. It is "A Star," not "A star" like "A square" or "A circle." It is a specific algorithm—using lowercase makes it sound like it describes a generic sort of algorithm. Anyone else have any input on this? -Frecklefoot
- I think A-Star search algorithm is about right. Better would be A* search algorithm, but apparently that's not an option?
- A* search algorithm as a topic works fine, as you can see. :) --ZeroOne 21:55, 17 Nov 2004 (UTC)
Bogus link
I removed the link to B* search algorithm. I determined it was bogus--it failed the Google test. —Frecklefoot 15:32, 12 Dec 2003 (UTC)
- Well, it's referenced by the article on Maven (Scrabble), which supposedly uses that search algorithm. An article on how that algorithm works would be enlightening. RSpeer 08:06, Dec 25, 2004 (UTC)
- B* is mentioned in (the classic) Artificial_Intelligence:_A_Modern_Approach, in the GamePlaying chapter, if I recall as an alternative to MinMax-alpha-beta.
Admissible heuristics
A bit of pervasive misinformation about A* search is that, as long as the heuristic never overestimates the distance to the goal, then the search is admissible. This is wrong.
As a counterexample: make a graph that you want to search, with a start and goal node, and give it an inadmissible heuristic, one that overestimates the distance somewhere so that A* chooses the wrong path. For the purpose of this counterexample, this heuristic shouldn't have any values over 1000000.
Now extend this graph by adding a new goal node, connecting it to the old goal node with an edge with a cost of 1000000. Suddenly the heuristic isn't an overestimate anywhere; if you're anywhere but the goal, it will cost at least 1000000 to get to the goal, and the heuristic is lower than that everywhere. So by the commonly-stated requirement for A* search, it should find the right path - but it doesn't. It finds the same path it found before, plus the new edge.
The requirement is that the heuristic can't overestimate the distance to anywhere; that is, if there's a path from A to B, then h(A) - h(B) is not greater than the shortest-path distance from A to B.
Course web pages, teaching assistants, and even textbooks leave this part out and make a provably false statement. Should I expand on this more in the article? RSpeer 08:06, Dec 25, 2004 (UTC)