Talk:A* search algorithm
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.
- The fact is, you shouldn't use the Google test on AI terms. When you're just doing AI-related stuff, you don't tend to classify exactly what algorithms or ideas you're using using standardized terminology (unless it's a popular buzzword and you want funding); the only place that so much precision is used is in textbooks, which you can't Google. RSpeer 17:53, Dec 26, 2004 (UTC)
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)
Hmm. I've looked up a little more, and found a possible reason why the second condition is often left out; you can use a less efficient version of A* that always finds the correct path without that condition. However, the usually-stated algorithm requires both conditions. These notes describe both algorithms, and call the second condition "monotonic". RSpeer 18:04, Dec 26, 2004 (UTC)
Blah. I screwed up. The page was describing that less-efficient version all along. I moved the thing about monotonic heuristics to its own section. Sorry. RSpeer 19:23, Dec 27, 2004 (UTC)
Intuition on why A* is admissible and optimal
I added this section because it reflects exactly how I initially recognized that the search algorithm proposed by Nils Nilsson and Bert Raphael was "the best we'll ever find".
See the original A* paper (which incidentally we had a hard time publishing, leading journals of the day were pleased to reject it as trivial or of no interest):
Hart, P. E., N. J. Nilsson, and B. Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths in Graphs," IEEE Trans. on Systems Science and Cybernetics, Vol. SSC-4, No. 2, pp 100-107, (July 1968)
It seems to me that this intuitive view is still of interest, I hope that it's more than a purely historical curiousity.
Missing details
1. Description on path reconstruction from closed priority queue: The article claims that the path can be reconstructed from the closed priority queue, without storing the path so far at each node. The article directs the reader to "see below" for a description of the advertised technique, but that description is nowhere to be found.
2. Check candidate nodes to see if they're already in Closed AND Open: The article mentions that you must check if a candidate node is already in the closed priority queue. I have read other descriptions such as Amit Patel's which is linked at the bottom of the page which states that you should also check if the candidate node is already in the open priority queue. Experimentally I determined that the algorithm runs at unacceptable speeds unless I perform this additional check.
Since I am in no position of authority on A* I have not made any edits to the article. Hopefully someone else can address these two issues.
Monotonicity
- The "open" and "closed" bookkeeping is not necessary...
Would someone add an explanation of why this is the case, i.e. how an algorithm might be implemented for a monotonic heuristic? This document says that there is no need for a closed list, but the article implies that the open list isn't necessary either. It's not obvious how the backtracking would work. Thanks. — Lee J Haywood 19:13, 28 August 2005 (UTC)
You don't really backtrack. Every time you reach a node, you have found the shortest path to that node. So, you just want to make sure you don't revisit nodes. I guess it would make sense to consider the mechanism that does that to be an "open list", even though there's no "closed list" to contrast it with. I'll rephrase that. RSpeer 03:20, August 29, 2005 (UTC)
- Only one list of visited nodes needs to be maintained, so that nodes are not unnecessarily revisited.
Doesn't this wording seem to imply a closed list rather than an open list? Also, when I said 'backtracking' I was referring to the situation where a search hits a dead-end (where the remaining distance is low but there is no valid path) and the choice has to be made as to which open list entry to expand next... I could really do with an example of a valid, monotonic heuristic in action to understand what's going on. Thanks. — Lee J Haywood 08:48, 29 August 2005 (UTC)
how does it work
Right now, the article doesn't explain how the algorithm works in detail.
Also, it'll be great to explain why it's called "A*". --Abdull 15:47, 27 November 2005 (UTC)
I agree. Also it would be nice to know who first developed it. --Kubiak 19:30, 29 November 2005 (UTC)