Dijkstra algorithm is a well known algorithm for finding exact distance from a source to a destination. In order to improve the path finding speed, A* algorithm combines heuristics and known distances to find the heuristically best path towards a goal. A common A* implementation maintains an open set for discovered yet not evaluated nodes and a closed set for already evaluated nodes.
Here is the pseudo-code of A* (copied from Wikipedia):
function A*(start, goal)
// The set of nodes already evaluated.
closedSet := {}
// The set of currently discovered nodes that are not evaluated yet.
// Initially, only the start node is known.
openSet := {start}
// For each node, which node it can most efficiently be reached from.
// If a node can be reached from many nodes, cameFrom will eventually contain the
// most efficient previous step.
cameFrom := the empty map
// For each node, the cost of getting from the start node to that node.
gScore := map with default value of Infinity
// The cost of going from start to start is zero.
gScore[start] := 0
// For each node, the total cost of getting from the start node to the goal
// by passing by that node. That value is partly known, partly heuristic.
fScore := map with default value of Infinity
// For the first node, that value is completely heuristic.
fScore[start] := heuristic_cost_estimate(start, goal)
while openSet is not empty
current := the node in openSet having the lowest fScore[] value
if current = goal
return reconstruct_path(cameFrom, current)
openSet.Remove(current)
closedSet.Add(current)
for each neighbor of current
if neighbor in closedSet
continue // Ignore the neighbor which is already evaluated.
// The distance from start to a neighbor
tentative_gScore := gScore[current] + dist_between(current, neighbor)
if neighbor not in openSet // Discover a new node
openSet.Add(neighbor)
else if tentative_gScore >= gScore[neighbor]
continue // This is not a better path.
// This path is the best until now. Record it!
cameFrom[neighbor] := current
gScore[neighbor] := tentative_gScore
fScore[neighbor] := gScore[neighbor] + heuristic_cost_estimate(neighbor, goal)
return failure
function reconstruct_path(cameFrom, current)
total_path := [current]
while current in cameFrom.Keys:
current := cameFrom[current]
total_path.append(current)
return total_path
In the code, the closed set prevents evaluated nodes from being evaluated again. One may think about not using closed set at all because it is not a big deal if we allow a node being added to the open set or its $latex f$ value being updated multiple times. Anyway, we only pick the node with the least $latex f$ value, right? Wrong. We can only safely drop using the closed set if “new nodes are added to the open set only if they have a lower $latex f$ value than at any previous iteration” (from Wikipedia). Without such mechanism, A* will never terminate in some extreme cases. Here is the version when the closed set is dropped out:
function A*(start, goal)
// The set of currently discovered nodes that are not evaluated yet.
// Initially, only the start node is known.
openSet := {start}
// For each node, which node it can most efficiently be reached from.
// If a node can be reached from many nodes, cameFrom will eventually contain the
// most efficient previous step.
cameFrom := the empty map
// For each node, the cost of getting from the start node to that node.
gScore := map with default value of Infinity
// The cost of going from start to start is zero.
gScore[start] := 0
// For each node, the total cost of getting from the start node to the goal
// by passing by that node. That value is partly known, partly heuristic.
fScore := map with default value of Infinity
// For the first node, that value is completely heuristic.
fScore[start] := heuristic_cost_estimate(start, goal)
while openSet is not empty
current := the node in openSet having the lowest fScore[] value
if current = goal
return reconstruct_path(cameFrom, current)
openSet.Remove(current)
for each neighbor of current
// The distance from start to a neighbor
tentative_gScore := gScore[current] + dist_between(current, neighbor)
if neighbor not in openSet // Discover a new node
openSet.Add(neighbor)
else if tentative_gScore >= gScore[neighbor]
continue // This is not a better path.
// This path is the best until now. Record it!
cameFrom[neighbor] := current
gScore[neighbor] := tentative_gScore
fScore[neighbor] := gScore[neighbor] + heuristic_cost_estimate(neighbor, goal)
return failure
function reconstruct_path(cameFrom, current)
total_path := [current]
while current in cameFrom.Keys:
current := cameFrom[current]
total_path.append(current)
return total_path
And here is the example when neither using the closed set nor the memory of previous iteration will cause A* never terminate:
The shortest path is supposed to be A->B->C->D->G. Starting from A:
Pick A from the open set. Update B’s $latex f$ value as $latex f(B)=g(A) + d(A,B) + h(B) = 0 + 1 + 1 = 2$. Update B’s $latex g$ value as $latex g(B)=g(A)+d(A,B)=0+1=1$. Add B to the open set.
Pick B from the open set. Update C’s $latex f$ value as $latex f(C)=g(B)+d(B,C)+h(C)=1+1+1=3$. Update C’s $latex g$ value as $latex g(C)=g(B)+d(B,C)=1+1=2$. Add C to the open set.
Pick C from the open set. Update D’s $latex f$ value as $latex f(D)=g(C)+d(C,D)+h(D)=2+1+100=103$. Add D to the open set. Since there is no closed set, the algorithm is ignorant of the fact that A has been checked. Therefore, the algorithm continues to update $latex f(A)=g(C)+d(C,A)+h(A)=2+1+1=4$. Because there is no memory recording what $latex A$’s previous $latex f$ values are, the algorithm stupidly assigns $latex f(A)=4$, a larger $latex f$ value than before, to A. A is then added to the open set. $latex g(A)$ and $latex g(D)$ will be updated similarly as before.
Now, picking the next node from the open set. A will be picked because it has the least $latex f$ value ($latex f(A)<f(D)$. Then, the loop will go on from A to B to C then to A again. Note that every time when you reach C, $latex f(D)$ and $latex f(A)$ will increase by $latex g(C) – g(C)_{old}$. A will always be favored over D because $latex h(A) < h(D)$. As a result, A* will never return.
Now, suppose both versions of A* (with or without the closed set) work thanks to proper implementation. Let’s see when A* returns the optimal distance.
For the version without the closed set, we claim A* is optimal when the heuristic function is admissible, i.e., $latex h(n)$ is never overestimated, i.e., $latex h(n) \leq h^*(n)$ for all nodes, where $latex h^*(n)$ is the shortest distance from n to the goal.
We can prove as follows: say the goal node is G, the start node is A. The optimal path from A to G has the distance $latex d^*$. If a non-optimal path propagates to G with $latex f(G)=d_{fake}$, then we must know $latex d^* < d_{fake}$. Since all heuristic values are not overestimated, before we pick G as the next node from the open set, there must be other nodes on the optimal path with a smaller f value than $latex d^*$ that get picked. Until the optimal path propagates its distance to G, G will never be picked from the open set with its non-optimal $latex f$ value.
For the version with the closed set, we claim A* is optimal when the heuristic function is both admissible and monotonic. A monotonic heuristic function means for any pair of adjacent nodes $latex x$ and $latex y$, where $latex d(x,y)$ denotes the length of the edge between them, we must have: $latex h(x) \leq d(x,y) + h(y)$. I don’t have a good proof why we require the heuristic function must also be monotonic but I can give an example that A* does not return the optimal distance when monotonicity is not satisfied.
Since $latex h(A) \leq h^*(A)$, $latex h(B) \leq h^*(B)$, $latex h(C) \leq h^*(C)$ and $latex h(D) \leq h^*(D)$, admissibility is satisfied. However, $latex h(B) > d(B,C)+h(C)$, therefore monotonicity is not satisfied. Now let’s see how the break of monotonicity makes A* not return the optimal distance.
We first pick A as it is the start point. Add B and C to the open set, with $latex f(B)=g(B)+h(B)=1+100=101$ and $latex f(C)=g(C)+h(C)=1+30=31$.
Then, we pick C from the open set because of $latex f(C)<f(B)$, evaluate C, and finally add C to the close set. During the evaluation, D will be added to the open set, with $latex f(D)=g(C)+d(C,D)+h(D)=1+5+90=96$ and $latex g(D)=g(C)+d(C,D)=1+5=6$. At this moment, B is not in the closed set. Since $latex f'(B)=g(C)+d(C,B)+h(B)=1+1+100=102$, which is less than current $latex f(B)$, we do not update $latex f(B)$.
Then, since $latex f(B)<f(D)$, we pick D from the open set and evaluate D. G and B are D’s neighbors. $latex f(G)=g(D)+d(D,G)=6+96=102$ and $latex f'(B)=g(D)+d(D,B)+h(B)=6+4+100=110$. Since $latex f'(B) > f(B)$, we do not update $latex f(B)$. We add D to the closed set.
Next, since $latex f(B) < f(G)$, we process B. However, the B’s neighbors C and D are all in the closed set. Therefore, we do nothing.
Finally, we pick G and turns out it is the goal. So we return with its $latex f$ value 102, which is not optimal. The optimal distance should be 101, which is achieved by the path A->B->D->G.
Actually, monotonicity implies admissibility when $latex h(G)=0$. Suppose for a node $latex v_0$, the shortest distance $latex h^*(v_0)$ from $latex v_0$ to $latex G$ is achieved by the path $latex v_0,v_1, v_2, v_3, \cdots, v_n, G$. Then, we can show that $latex h(v_0) \leq h^*(v_0)$:
$latex h(v_0) \leq d(v_0, v_1) + h(v_1) \leq d(f, v_1) + d(v_1, v_2) + h(v_2) \leq \cdots \leq \sum\limits_{i=0}d(v_i, v_{i+1}) + h(G) =h^*(v_0)$
Reference:
http://www.algostructure.com/search/a-star.php