A* search is an informed search algorithm used for path-finding and graph traversal. It combines the advantages of both Dijkstra’s algorithm (in that it can find a shortest path) and Greedy Best-First-Search (in that it can use a heuristic to guide search). It combines the information that Dijkstra’s algorithm uses (favoring vertices that are close to the starting point) and information that Best-First-Search uses (favoring vertices that are closer to the goal).
Let g(n) represent the exact cost of the path from the starting point to any vertex n, and h(n) represent the heuristic estimated cost from vertex n to the goal. Dijkstra’s algorithms builds a priority queue of nodes ordered on their g(n) values. Best-First-Search employs a priority queue of nodes ordered on h(n) values. A* balances the two as it moves from the starting point to the goal. It builds a priority queue of nodes ordered on f(n) = g(n) + h(n) which is the total estimated path cost through the node n.
A* tree search algorithm:
| def A*-TREE-SEARCH (start): | |
| Let pq be an empty min priority queue | |
| g(start) = 0 | |
| f(start) = h(start) | |
| path(start) = [] | |
| pq.push(start, f(start)) | |
| while not pq.empty(): | |
| top = pq.pop() | |
| if isGoal(top): | |
| return f(top), path(top) | |
| foreach next in succ(top): | |
| g(next) = g(top) + cost(top, next) | |
| f(next) = g(next) + h(next) | |
| path(next) = path(top).append(next) | |
| pq.push(next, f(next)) |
A*-TREE-SEARCH is optimal only if the heuristic used is admissible (i.e., it never overestimates the cost of reaching the nearest goal). The algorithm is called tree search because it builds a search tree (as opposed to a search graph). Failure to detect repeated states can cause exponentially more work as evident in this example:
State Graph
Search Tree
We can eliminate the repeated work by maintaining a closed set of expanded nodes and adding only those nodes to the priority queue which are not in the closed set, thus yielding a graph search algorithm.
A* graph search algorithm:
| def A*-GRAPH-SEARCH (start): | |
| Let pq be an empty min priority queue | |
| Let closed be an empty set | |
| g(start) = 0 | |
| f(start) = h(start) | |
| path(start) = [] | |
| pq.push(start, f(start)) | |
| while not pq.empty(): | |
| top = pq.pop() | |
| if isGoal(top): | |
| return f(top), path(top) | |
| closed.add(top) | |
| foreach next in succ(top): | |
| if next not in closed: | |
| g(next) = g(top) + cost(top, next) | |
| f(next) = g(next) + h(next) | |
| path(next) = path(top).append(next) | |
| pq.push(next, f(next)) |
The optimality of A*-GRAPH-SEARCH places stronger demands on the heuristic, requiring it to be consistent. A heuristic is consistent if it approximates the actual path cost in an incremental way without taking any step back. Formally, for every node N and for every successor P of N, h(N) <= h(P) + cost(N, P). Fortunately, most natural heuristic functions (particularly those obtained by relaxing problem constraints) are consistent.
A*-GRAPH-SEARCH can be made to be optimal in the presence of an admissible heuristic (and not a consistent heuristic) by using a cost-sensitive closed set. The closed set is now a map, mapping from expanded states n to f(n). While iterating through successors of the current state, we add those successors, say n, to the priority queue which either haven’t yet been visited (i.e., n not in closed) or whose f values are smaller than when they were visited earlier (i.e., f(n) < closed[n]) and update the closed set appropriately. It is important that we return a goal state when it is popped off the queue and not when it is pushed onto the queue to guarantee optimality as evident from the following example:
State Graph
Lets work through this example. First, S is expanded and nodes A (f(A)=4) and B (f(B)=3) are pushed onto the queue. Then, B (having smaller f value) is expanded and G (f(G)=5) is pushed onto the queue. If we declare victory as soon as we push it onto the queue, we will choose the path S->B->G (having cost 5) and not the shorter path S->A->G (having cost 4).
For an application of A* search, see N-puzzle problem and its solution in python using A*-GRAPH-SEARCH and Manhattan distance as heuristic.
References:
Everything Under The Sun 
Pingback: Informed Search Algorithms | Everything Under The Sun