StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>OK, since you asked me to post an answer…. </p> <p>Before you understand A*, you must first understand <a href="http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm" rel="nofollow">Dijkstra's algorithm</a>. Given a graph (a set of nodes, and edges between nodes) and the (positive) "distance" of each edge (e.g. the road distance), Dijkstra's algorithm gives the shortest distance between a certain source node and each destination node. For instance, in your graph, the nodes may be road-intersections, the edges may be the roads, and the weight/distance you put on an edge may be the length of that road, or the time it takes to traverse it, or whatever.</p> <p>Please understand: Dijkstra's algorithm always gives the correct distance according to the weights you have put on the edges. In fact, the graph need not even be embeddable in a plane, i.e., there may be no notion of "straight line distance" in the first place. It can be any arbitrary graph.</p> <p>Now, A* can be thought of as a particular heuristic to speed up Dijkstra's algorithm. You can think of it as using a heuristic to decide the order in which to consider nodes in the graph.</p> <p>Formally: you have a graph G, two nodes s and t in it, and you want to find the distance d(s,t) between s and t. (The distance is according to the graph, e.g. according to road distance in your example.) To find d(s,t), in A* you use a heuristic function h(x) which satisfies h(x) ≤ d(x,t). For <em>instance</em> (just one possibility), you can choose h(x) to be the straight line distance from x to t. The better h(x) is as an estimate of d(x,t), the faster the A* algorithm will run, but the choice of h affects only the speed, not the answer: it will always give the shortest distance according to d, not h. </p> <p>So to find the road distance s to t, just set d(u,v) to be the road distance for every pair of nodes u and v with a road between them, run A*, and you'll find the d(s,t) you want.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload