As this snippet doesn't really help a lot to know what A* search actually is, here is the explanation from Artificial Intelligence: A Modern Approach (from Russel and Norvig):<p><i>The most widely-known form of best-first search is called A-start search (pronounced "A-star search"). It evaluates nodes by combining g(n) - the cost to reach the node, and h(n) - the cost to get from the node to the goal:</i><p><pre><code> f(n) = g(n) + h(n)
</code></pre>
<i>Since g(n) gives the path cost from the start node to node n, and h(n) is the estimated cost of the cheapest path from n to the goal, we have</i><p><pre><code> f(n) = estimated cost of the cheapest solution through n*
</code></pre>
<i>Thus, if we are trying to find the cheapest solution, a reasonable thing to try first is the node with the lowest value of g(n) + h(n). It turns out that this strategy is more than just reasonable: provided that the heuristic function h(n) satisfies certain conditions, K search is both complete and optimal.</i><p><i></i><p>So, for the following graph (tree actually):<p><pre><code> +---A---+
| |
B h:1 E h:4
|
C h:2
|
D h:3
</code></pre>
Where the function g(x) is the depth of the node in the tree, and the heuristic function h(x) is presented next to the node (random values), A-star will search for a solution first in the nodes with smaller values of f(n). So a traversal starting at node A will visit nodes in the following order: {A, B, C, E, D}<p><pre><code> f(B) = h(B) + g(B) = 1 + 1 = 2
f(C) = 2 + 2 = 4
f(E) = 4 + 1 = 5
f(D) = 3 + 3 = 6
</code></pre>
If there's anything wrong with my explanation please correct me.<p>P.S.: I know my heuristic function is probably not admissible.
10 second explanation of A star: you have a graph + matrix of node-node distances. You want to find shortest path from origin to destination. Standard Dijsktra only allows lookahead of one node at a time. A star allows you to incorporate a long range heuristic, like Euclidean distance from current node to destination. This gives a lower bound on current candidate path length and allows you to discard bad paths more rapidly.<p>Note that in all cases you need some basis for this heuristic (eg lat/lng of each node). Also, while 2D maps/nodes as cities is a great way to build your intuition for the algorithm, you can generalize it to arbitrary node types as long as heuristic function gives a good lower bound.