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)
- 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)
I agree. Also it would be nice to know who first developed it. --Kubiak 19:30, 29 November 2005 (UTC)
- Hm, I hope the new article is a bit better in this regard :-) Regnaron 18:59, 15 December 2005 (UTC)
Rewriting of article
Hi, I just translated my article for the A* search algorithm I wrote for the german wikipedia (which was once founded on the old version of this article) into english, and uploaded it here. But since my mothertounge is german, I am sure there are not just dozens of typos, but also tons of wordings where native speakers just want to run away screeming :-) So I would be very pleased if some of you could correct my choice of words :-) Regnaron 18:58, 15 December 2005 (UTC)
- I think your translated article is very comprehensive, if a bit overly "textbooky" for Wikipedia. (Have you considered Wikibooks?) However, it's full of typos, grammatical atrocities, and just generally things that are wrong in English. It's very difficult to get any sense of what A* is or what it does simply by reading the article from start to finish, because nobody who starts reading will finish! So I'm reverting to the old English article — but with an encouraging word for any native English speaker who wants to try to translate the German article from scratch. (But please, less wordy!) --Quuxplusone 02:50, 16 December 2005 (UTC)
- Hi! Hm, well, in fact I tried to make the article somewhat comprehensive through the big example section and explaining how it works, and I still would say this can help the reader to grasp the idea of "how an A* search works". (Nevertheless, all aspects of the algorithm had been covered in the article) But as I stated in my initial post here: I already assumed that there is (or now was :-)) a lot of wording that would simply be wrong in english. (I just did not expect it to be that much *g*) Getting to the point: I belive you that your comments and critics are correct, so I will not start yelling and hunting for you for reverting the article. Despite, in case anyone still wants to invest some time "translating" my old article: It will stay being acessible via my Playground on my userpage Regnaron 08:32, 16 December 2005 (UTC)
Relation to uniform-cost search
"Uniform-cost search, aka Dijkstra's algorithm, is a special case of A*..." - even a quick glance at the linked articles shows that "Dijkstra's algorithm" is not the same thing as "uniform-cost search". That said, I'm not knowledgeable enough on this topic to feel comfortable rewriting the sentence. Rizome 20:07, 8 May 2006 (UTC)
- Hi! Hm, if I have a look at what is written at Uniform-cost search (UCS) it quite fits the description of Dijkstras Algorithm. If you just replace root with source you will get a description of Dijkstras Algorithm. I am not absolutely certain why there are two Pages describing the same algorithm, but at the current state of the UCS article it (in a very simplified way) does describe Dijkstras Algorithm. (Always expand the globally cheapest node) Regnaron 18:48, 22 May 2006 (UTC)
Ditto, as far as I can see Dijkstra is the same thing as uniform cost-search. I also have trouble seeing how Dijkstra is a special case of A* considering A* came after Dijkstra published his algorithm, the fact that the earlier can be seen as a derivation of the latter doesn't mean that it is a special case of A*.
- Dijkstra's is a special case in the mathematical sense, this has nothing to do with historical derivation. Qwertyus 14:10, 26 May 2006 (UTC)
- Well, use A* with the heuristics h(x) = 0 for all x. (meaning using no heuristics at all)
- What you will get is just Dijkstras Algorithm. So in this sense Dijkstra is a special case of A* (namely one where the heuristcs is 0 for all nodes) Regnaron 21:14, 26 May 2006 (UTC)
Intuition about why A* is not computationally optimal
This section points out that A* may not be computationally optimal for non-planar graphs.
The proof of the optimality of A* relies on the fundamental assumption that the triangle inequality is satisfied for every 3-node subset of the graph being searched. A non-planar graph may violate this assumption.
Huw: Actually the way I read this section it states that is not computationally optimal for planar graphs because does not take advantage of certain features of planar graphs. I claim that this is nonsense. I claim that depends for its quality entirely on the heuristic being used. For example, if : then will walk straight to the solution regardless of the type of graph being examined. Typically, for planar graphs, is defined to be the linear planar distance from to the goal. This makes take advantage of precisely the planar features that the author claims it does not. This means that will be computationally optimal for these graphs.
complexity
polynomial... what polynomial, n^2 is mutch mutch better than n^3
- I would doubt the correctness of that paragraph as a whole... First of all I do not see any exponential running time of the algorithm. It has to visit each vertex in a graph exactly once, as well as it has to consider every edge once. That is linear in the number of vertices and edges. You get some overhead from maintaining the priority queue, but still nothing exponential. Furthermore: If you have a graph that is a list, you can have the best heuristic, but still will do no better than with no heuristic at all, since you have to go the complete path up to the goal node. E.g. where s is the start node and g the goal node. Here you may have a perfect heuristic, but the running time does not change at all since you cannot skip any nodes. Regnaron 17:24, 14 July 2006 (UTC)
Huw: I agree. This paragraph is simply not true. I'm not even sure what even means in this context since represents a vertex in a graph and should imply that is the dominant term in the cost of an algorithm when .
- is the asymptotic growth of the perfect heuristic . I explained this and inserted a reference. Btw., visiting each edge and each node once is only possible for finite graphs. A* can be used for infinite graphs, or at least graphs that do not fit in any computer memory using an "explicit" representation. Qwertyus 00:44, 21 July 2006 (UTC)
