A* Algorithm : An Introduction To The Powerful Search Algorithm

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.

The topics covered in this article are as follows :

  • What is an A* Algorithm?
  • The Basic Concept of A* Algorithm
  • How does A* Algorithm work?
  • Pseudocode of A* Algorithm
  • How to Implement A* Algorithm in Python?

Python Training Course

Learn Data Operations in PythonExplore Course
Python Training Course

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.

AAlgorithm_Fig1

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.

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?

A_Algorithm_Fig2

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
    • 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
      • If it reaches the destination node :

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

FREE Data Science With Python Course

Start Learning Data Science with Python for FREEStart Learning
FREE Data Science With Python Course

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.

AAlgorithm_Fig3.

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.

AAlgorithm_Fig4.

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.

AAlgorithm_Fig5

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.

AAlgorithm_Fig6.

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.

AAlgorithm_Fig7.

Figure 7: Checking distances, updating the g values, and adding parents

Now, define a function to return neighbors and their distances.

AAlgorithm_Fig8

                                              Figure 8: Defining neighbors

Also, create a function to check the heuristic values.

AAlgorithm_Fig9.

Figure 9: Defining a function to return heuristic values

Let’s describe our graph and call the A star function.

AAlgorithm_Fig10

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

Conclusion

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!

About the Author

SimplilearnSimplilearn

Simplilearn is one of the world’s leading providers of online training for Digital Marketing, Cloud Computing, Project Management, Data Science, IT, Software Development, and many other emerging technologies.

View More
  • Disclaimer
  • PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, and OPM3 are registered marks of the Project Management Institute, Inc.