Search algorithms are algorithms designed to search for or retrieve elements from a data structure, where they are stored. They are essential to access desired elements in a data structure and retrieve them when a need arises. A vital aspect of search algorithms is Path Finding, which is used to find paths that can be taken to traverse from one point to another, by finding the most optimum route.
In this tutorial titled ‘A* Algorithm - An Introduction To The powerful search algorithm’, you will be dealing with the A* algorithm, which is a search algorithm that finds the shortest path between two points.
What is an A* Algorithm?
It is a searching algorithm that is used to find the shortest path between an initial and a final point.
It is a handy algorithm that is often used for map traversal to find the shortest path to be taken. A* was initially designed as a graph traversal problem, to help build a robot that can find its own course. It still remains a widely popular algorithm for graph traversal.
It searches for shorter paths first, thus making it an optimal and complete algorithm. An optimal algorithm will find the least cost outcome for a problem, while a complete algorithm finds all the possible outcomes of a problem.
Another aspect that makes A* so powerful is the use of weighted graphs in its implementation. A weighted graph uses numbers to represent the cost of taking each path or course of action. This means that the algorithms can take the path with the least cost, and find the best route in terms of distance and time.
Figure 1: Weighted Graph
A major drawback of the algorithm is its space and time complexity. It takes a large amount of space to store all possible paths and a lot of time to find them.
[Related reading: Top 45 Data Structure Interview Questions and Answers for 2022]
The Basic Concept of A* Algorithm
A heuristic algorithm sacrifices optimality, with precision and accuracy for speed, to solve problems faster and more efficiently.
All graphs have different nodes or points which the algorithm has to take, to reach the final node. The paths between these nodes all have a numerical value, which is considered as the weight of the path. The total of all paths transverse gives you the cost of that route.
Initially, the Algorithm calculates the cost to all its immediate neighboring nodes,n, and chooses the one incurring the least cost. This process repeats until no new nodes can be chosen and all paths have been traversed. Then, you should consider the best path among them. If f(n) represents the final cost, then it can be denoted as :
f(n) = g(n) + h(n), where :
g(n) = cost of traversing from one node to another. This will vary from node to node
h(n) = heuristic approximation of the node's value. This is not a real value but an approximation cost
How Does the A* Algorithm Work?
Figure 2: Weighted Graph 2
Consider the weighted graph depicted above, which contains nodes and the distance between them. Let's say you start from A and have to go to D.
Now, since the start is at the source A, which will have some initial heuristic value. Hence, the results are
f(A) = g(A) + h(A)
f(A) = 0 + 6 = 6
Next, take the path to other neighbouring vertices :
f(A-B) = 1 + 4
f(A-C) = 5 + 2
Now take the path to the destination from these nodes, and calculate the weights :
f(A-B-D) = (1+ 7) + 0
f(A-C-D) = (5 + 10) + 0
It is clear that node B gives you the best path, so that is the node you need to take to reach the destination.
Pseudocode of A* Algorithm
The text below represents the pseudocode of the Algorithm. It can be used to implement the algorithm in any programming language and is the basic logic behind the Algorithm.
- Make an open list containing starting node
- If it reaches the destination node :
- Make a closed empty list
- If it does not reach the destination node, then consider a node with the lowest f-score in the open list
We are finished
- Else :
Put the current node in the list and check its neighbors
- For each neighbor of the current node :
- If the neighbor has a lower g value than the current node and is in the closed list:
Replace neighbor with this new node as the neighbor’s parent
- Else If (current g is lower and neighbor is in the open list):
Replace neighbor with the lower g value and change the neighbor’s parent to the current node.
- Else If the neighbor is not in both lists:
Add it to the open list and set its g
How to Implement the A* Algorithm in Python?
Consider the graph shown below. The nodes are represented in pink circles, and the weights of the paths along the nodes are given. The numbers above the nodes represent the heuristic value of the nodes.
Figure 3: Weighted graph for A* Algorithm
You start by creating a class for the algorithm. Now, describe the open and closed lists. Here, you are using sets and two dictionaries - one to store the distance from the starting node, and another for parent nodes. And initialize them to 0, and the start node.
Figure 4: Initializing important parameters
Now, find the neighboring node with the lowest f(n) value. You must also code for the condition of reaching the destination node. If this is not the case, put the current node in the open list if it's not already on it, and set its parent nodes.
Figure 5: Adding nodes to open list and setting parents of nodes
If the neighbor has a lower g value than the current node and is in the closed list, replace it with this new node as the neighbor's parent.
Figure 6: Checking distances and updating the g values
If the current g is lower than the previous g, and its neighbor is in the open list, replace it with the lower g value and change the neighbor's parent to the current node.
If the neighbor is not in both lists, add it to the open list and set its g value.
Figure 7: Checking distances, updating the g values, and adding parents
Now, define a function to return neighbors and their distances.
Figure 8: Defining neighbors
Also, create a function to check the heuristic values.
Figure 9: Defining a function to return heuristic values
Let’s describe our graph and call the A star function.
Figure 10: Calling A* function
The algorithm traverses through the graph and finds the path with the least cost
which is through E => D => G.
Looking forward to making a move to the programming field? Take up the Python Training Course and begin your career as a professional Python programmer
In this tutorial, an introduction to the powerful search algorithm’, you learned about everything about the algorithm and saw the basic concept behind it. You then looked into the working of the algorithm, and the pseudocode for A*. You finally saw how to implement the algorithm in Python.
If you are looking to learn further and get a more comprehensive and work-ready understanding of Python, Simplilearn’s Python Certification Course should be your next destination. A complete training course in Python will help you master all the fundamentals of Python including conditional statements, data operations, shell scripting, Django, and more. Learn from active practitioners in the field and nonoutdated trainers in this course designed to help you master Python and build a flourishing career in the field.
Do you have any doubts or questions for us on this topic? Mention them in the comments section of this tutorial, and we'll have our experts answer them for you at the earliest!