Sometimes algorithms in computer science might not have very obvious uses to non-technical people. However some, like A* Search, have very evident uses. Just by stating that it is a shortest-path finding algorithm, you can automatically deduce that it is used in finding the fastest route when you set a destination on your electronic maps.
A Brief History
The algorithm was published by Peter Hart, Nils Nilsson and Bertram Raphael of Stanford Research Institute in 1968. It is an evolved version of Dijkstra’s Algorithm, created as part of the Shakey project and utilizes an extra heuristic that helps it make smarter choices in choosing the next node to expand.
Best of Both Worlds
A* is a combination of both Dijkstra’s Algorithm and Best-First-Search. Dijkstra’s algorithm visits vertices starting from the starting vertex and expands outwards till it finds its goal. It is guaranteed to find the shortest path given that there are no edges with a negative cost. Whereas the Best-First-Search algorithm is a greedy algorithm uses a heuristic of how far the goal is from the current vertex. In typical greedy manner it chooses the vertices based on how close to the goal they are. Which is why, even though it is way quicker in finding a path, it does not necessarily choose the fastest and shortest path. Below is a visual difference in both the algorithms.
The light blue nodes are the visited nodes and the yellow path is the path determined by the algorithm. It is evident how Best-First-Search is way faster in determining the route, but also how it is not the best route.
That is where A* Search algorithm comes in. It takes a combined heuristic of both the distance from starting node and distance from ending node. What this does is it gives it a general sense of direction to traverse while also assuring that the fastest route will be taken. It is very similar to Dijkstra’s algorithm, the only difference being it avoids traversing the nodes away from the ending nodes and therefore saves a lot of time.
Now that we have discussed the basic logic behind A* algorithm and how it is different from other shortest path finding algorithms, let us solve an example to get a better understanding of how it works
This is an undirected graph with 13 vertices and 17 edges. The numbers written in yellow are the edge weights and the numbers written in blue are the extra heuristic that we will provide to the algorithm. Though the graph is not up to scale, the numbers in blue are a rough Euclidean distance from our destination node. The highlighted nodes are S and E, which stand for Starting node and Ending Node respectively.
For the implementation of the algorithm, we utilize a priority queue which is filled with nodes we need to expand in the future. The node at the top will be the node we expand. The sorting in the queue will done based on the combined total of the numbers in blue and yellow. In Dijkstra’s algorithm this sorting would be done on the basis of just the numbers in yellow.
We will maintain 3 critical points of information for each node in this example; Which node we used to visit this node, What is distance from start to this node, What is the combined total of each node (made up from previous parameter and the blue number for given node)
The basic algorithm is:
Step 1: Expand the Starting/Current Node
Step 2: Update parameters of all nodes connected to current node and insert in Priority Queue. Pop the current Node out of the Priority Queue and put in a finished stack.
Step 3: Choose The top node in the Priority Queue and repeat Step 1 and Step 2 till the Ending Node is at the top of the Priority Queue.
Let us apply the algorithm to our example,
Step 1: Expand Node ‘S’ , Update Nodes ‘A’, ‘B’ and ‘C’ and insert in Queue. Put Node ‘S’ in finished stack.
Step 2: Choose and expand ‘B’ since it has the lowest combined score and therefore at the top of the Priority Queue. Update Nodes ‘A’, ‘D’ and ‘H’ and insert in Queue. Put Node ‘B’ in finished stack.
Note that Node ‘A’ is now coming from Node ‘B’ instead of Node ‘S’ because the path S->B->A is a shorter route to ‘A’ then S->A.
Step 3: Choose and expand ‘H’ and update Nodes ‘F’ and ‘G’. Insert them in the Priority Queue. Put Node ‘H’ in finished stack.
Step 4: Choose and expand ‘G’ and update Node ‘E’. Insert ‘E’ into the Priority Queue and put Node ‘G’ in the finished stack. Node ‘E’ has a default heuristic value of 0 since it is our destination node.
Step 5: Choose Node ‘E’. Since it is actually our destination Node, we have found the the fastest path to our destination. Backtrack through the parameter of ‘Prev Node’ till you reach the starting Node.
Therefore our shortest path is S->B->H->G->E with a cost of 7.
The time complexity of A* generally depends on the heuristic being implemented. However, for a general implementation of A* search algorithm with the Euclidean Distance heuristic, we have:
Time complexity: O(E)
Auxiliary Space: O(V)
where V is the number of vertices in the graph and E is the number of edges present.