| | |
Both the Breadth First Search and Dijkstra's Algorithm produce a spanning tree for the graph to which they are applied by continually considering a set of vertices that might be connected to an existing (initially degenerate) tree. (These are the vertices on the priority queue at any point during the algorithm.) Let us call this set of vertices at each step through the algorithm the "frontier".
Notice that in both algorithms, the frontier expands in all directions away from the tree built so far. This is reasonable if you're trying to find a path to all locations or to many locations. However, a common case is to find a path to only one location. As such, it will be advantageous to make the frontier expand towards this goal location more than it expands in other directions.
To accomplish this, let us define a heuristic function that tells us how close we are to the goal. In the case of edge-weighted graphs where the vertices represent physical locations, and the edge weights represent the lengths of paths that can be taken to get from one starting location $(x_1, y_1)$ to another $(x_2,y_2)$, the heuristic used might be as simple as the Euclidean distance between the two vertices.
$$h(n) = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$$In general, you can think of the heuristic function as providing an estimate of the cost of the cheapest path from a vertex to the "destination" vertex.
To minimize time spent exploring directions that aren't promising while still doing well in finding the shortest path, the A* algorithm makes a slight modification to Dijkstra's algorithm. The priority attached to a particular vertex is no longer the distance/cost required to get back to the starting vertex from the current vertex, as discovered so far -- but rather, it is the sum of this AND an estimate made by some heuristic function of the remaining distance to get to the destination vertex from the current vertex.)
Dijkstra's Version of Relaxing an Edge:
// if we can get to vertex w from the source vertex faster
// through vertex v, then relax the distance between the
// source and w, update edgeTo[] to reflect that one should travel
// to w through v, and add (or update) the priority queue
// appropriately
if (distTo[w] > distTo[v] + e.weight()) {
distTo[w] = distTo[v] + e.weight();
edgeTo[w] = e;
// now update priority queue...
if (pq.contains(w))
pq.decreaseKey(w, distTo[w]);
else
pq.insert(w, distTo[w]);
}
The A* Version of Relaxing an Edge:
// if we can get to vertex w from the source vertex faster
// through vertex v, then relax the distance between the
// source and w, update edgeTo[] to reflect that one should travel
// to w through v, and add (or update) the priority queue
// appropriately
if (distTo[w] > distTo[v] + e.weight()) {
distTo[w] = distTo[v] + e.weight();
edgeTo[w] = e;
// now update priority queue...
if (pq.contains(w))
pq.decreaseKey(w, distTo[w]+h(w,destination));
else {
pq.insert(w, distTo[w]+h(w,destination));
}
}
As one final modification to minimize the time spent searching for the shortest path between two vertices, one should stop analyzing the graph once the shortest path to the destination has been found (i.e., once the destination vertext has been pulled off of the priority queue.)
One can show that A* will find a shortest path if the heuristic used (which can vary) never overestimates the cost to reach the destination vertex (which we abbreviate by saying the heuristic is admissible) and if the search space is a tree.
Supposing that $h(n)$ is the heuristic function and $c(n,m)$ gives the cost of traveling from vertex $n$ to vertex $m$ -- one way to guarantee that a heuristic is admissible is to ensure that if for every vertex $n$ and for every adjacent successor vertex $n'$ of $n$, we have $h(n) \le c(n,n') + h(n')$. Heuristic functions with this property are called consistent. One should note that, as said before, whenever $h$ is consistent $h$ will definitely also be admissible, but the reverse need not be the case (although frequently they do go hand-in-hand).