A * Algorithm in artificial intelligence that you need to know in 2022

What is the A * algorithm?

This is a search algorithm that is used to find the shortest path between the start and end point.

This is a handy algorithm that is often used to crawl a map to find the shortest route. A * was originally designed as a graphics crawl problem to help build a robot that can find its own course. It still remains a widely used graphics traversal algorithm.

First it looks for shorter paths, which makes it an optimal and complete algorithm. The optimal algorithm will find the lowest result for a given problem, while the full algorithm will find all possible results from a given problem.

Another aspect that makes A * so powerful is the use of weighted graphs in its implementation. The weighted graph uses numbers to represent the cost of taking each trip or course of action. This means that algorithms can take the road with the lowest cost and find the best route in terms of distance and time.

Figure 1: Weighted graph

The main disadvantage of the algorithm is its spatial and temporal complexity. It takes a lot of space to store all possible roads and a lot of time to find them.

[Related reading: Top 45 Data Structure Interview Questions and Answers for 2022]

The basic concept of the A * algorithm

The heuristic algorithm sacrifices optimality, with precision and accuracy for speed, to solve problems faster and more efficiently.

All graphs have different nodes or points that the algorithm must take to reach the final node. All roads between these nodes have a numerical value, which is considered the weight of the road. The total amount of all cross roads gives you the price of this route.

Initially, the algorithm calculates the cost of all its immediate neighbors, n, and selects the one with the lowest cost. This process is repeated until new nodes can be selected and all paths are traversed. Then you need to think about the best path among them. If f (n) represents the final price, then it can be denoted as:

f (n) = g (n) + h (n), where:

g (n) = price to switch from one node to another. This will vary from knot to knot

h (n) = heuristic approximation of the node value. This is not a real value, but an approximate price

How does the A * algorithm work?

Figure 2: Weighted graph 2

Consider the weighted graph shown above, which contains the nodes and the distance between them. Let’s say you start with A and you have to go to D.

Now, since the beginning is in source A, which will have some initial heuristic value. Therefore, the results are

f (A) = g (A) + h (A)
f (A) = 0 + 6 = 6

Then take the road to other neighboring peaks:

f (AB) = 1 + 4

f (AC) = 5 + 2

Now take the path to the destination from these nodes and calculate the weights:

f (ABD) = (1+ 7) + 0

f (ACD) = (5 + 10) + 0

Clearly, Node B gives you the best route, so this is the node you need to take to get to your destination.

FREE course in data science with Python

Gain mastery of data science with Python nowStart learning

Algorithm A pseudocode *

The text below represents the pseudocode of the algorithm. It can be used to execute the algorithm in any programming language and is the basic logic behind the algorithm.

• Make an open list containing the starting node
  • If it reaches the destination node:
• Make a closed empty list
• If it does not reach the destination node, then consider the node with the lowest f-score in the open list

We are ready

Put the current node in the list and check its neighbors

• For each neighbor of the current node:
• If the neighbor has a lower value of g than the current node and is in the closed list:

Replace a neighbor with this new node as the neighbor’s parent

• Otherwise If (current g is lower and the neighbor is in the open list):

Replace the neighbor with the lower value of g and change the parent of the current node neighbor.

• Otherwise If the neighbor is not on both lists:

Add it to the open list and set its g

How to implement the A * algorithm in Python?

Consider the graph below. The knots are presented in pink circles and the weights of the paths along the knots 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 use kits and two dictionaries – one to store the distance from the starting node and the other for the parent nodes. And initialize them to 0 and the initial node.

Figure 4: Initialization of important parameters

Data science with Python

The best ticket for the best roles in data scienceTake a course

Now find the adjacent node with the lowest value of f (n). You must also code the condition for reaching the destination node. If this is not the case, put the current node in the open list, if it is not already in it, and set its parent nodes.

Figure 5: Adding nodes to an open list and setting up node parents

If the neighbor has a lower value of g 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 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 value of g and change the parent of the neighbor of the current node.

If the neighbor is not in both lists, add it to the open list and set its value to g.

Figure 7: Checking distances, updating 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 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 function A *

The algorithm goes through the graph and finds the path with the lowest price

which is through E => D => G.

Are you looking forward to moving into the field of programming? Take a Python training course and start your career as a professional Python programmer

Conclusion

In this tutorial, an introduction to the powerful search algorithm, you learned all about the algorithm and saw the basic concept behind it. Then you looked at the operation of the algorithm and the pseudocode for A *. Finally, you saw how to implement the algorithm in Python.

If you want to learn more and gain a more comprehensive and ready-to-understand understanding of Python, Simplilearn’s Python certification course should be your next destination. A complete Python training course will help you master all the basics of Python, including conditional expressions, data operations, shell scripts, Django and more. Learn from active practitioners in the field and outdated trainers in this course designed to help you master Python and build a thriving career in the field.

Do you have any doubts or questions to us on this topic? Mention them in the comments section of this tutorial and we will get our experts to answer you as soon as possible!