AI & Deep Learning with TensorFlow
- 16k Enrolled Learners
- Live Class
Path Finding has been one of the oldest and most popular applications in computer programming. You could virtually find the most optimal path from a source to a destination by adding costs which would represent time, money etc. A* is one of the most popular algorithms for all the right reasons. In this article, let’s find out just why.
The article comprises of the following sections:
Let’s get started :)
Moving from one place to another is a task that we humans do almost every day. We try to find the shortest path that enables us to reach our destinations faster and make the whole process of travelling as efficient as possible. In the old days, we would trial and error with the paths available and had to assume which path taken was shorter or longer.
Now, we have algorithms that can help us find the shortest paths virtually. We just need to add costs (time, money etc.) to the graphs or maps and the algorithm finds us the path that we need to take to reach our destination as quick as possible. Many algorithms were developed through the years for this problem and A* is one the most popular algorithms out there.
So what exactly is the A* algorithm? It is an advanced BFS algorithm that searches for shorter paths first rather than the longer paths. A* is optimal as well as a complete algorithm.
What do I mean by Optimal and Complete? Optimal meaning that A* is sure to find the least cost from the source to the destination and Complete meaning that it is going to find all the paths that are available to us from the source to the destination.
So that makes A* the best algorithm right? Well, in most cases, yes. But A* is slow and also the space it requires is a lot as it saves all the possible paths that are available to us. This makes other faster algorithms have an upper hand over A* but it is nevertheless, one of the best algorithms out there.
So why choose A* over other faster algorithms?
Let the graphs below answer that for you. I have taken the Dijkstra’s algorithm and A* Algorithm for comparison.
You can see here that the Dijkstra’s Algorithm finds all the paths that can be taken without finding or knowing which is the most optimal one for the problem that we are facing. This leads to the unoptimized working of the algorithm and unnecessary computations.
A* algorithm, on the other hand, finds the most optimal path that it can take from the source in reaching the destination. It knows which is the best path that can be taken from its current state and how it needs to reach its destination.
Now that you know why we choose A*, let’s understand a bit of theory about it as it is essential to help you understand how this algorithm works.
A*, as we all know by now, is used to find the most optimal path from a source to a destination. It optimizes the path by calculating the least distance from one node to the other.
There is one formula that all of you need to remember as it is the heart and soul of the algorithm.
So what are these 3 variables and why are they so important? Let’s understand it now.
So once that you have understood this formula, let me just show you a simple example to help you understand how this algorithm works.
Suppose we have a small graph with the vertices: S, A, B, E where S is the source and E is the destination.
Remember that the cost to enter the source and destination is always 0.
The heuristic values are:
Let’s use the formula and calculate the shortest path from the source to the destination now.
f = g + h where g is cost to travel and h is the heuristic value.
To reach Source:
f(S) = 0 + 5 = 5
The paths from S to other vertices:
f(S-A) = 1 + 4 = 5
f(S-B) = 2 + 5 = 7
So, we firstly will choose the path of S -> A as it is the least.
The paths from A and B to the Destination:
f(S-A-E) = (1 + 13) + 0 = 14
f(S-B-E) = (2 + 5) + 0 = 7
After calculation, we have now found that B later has given us the least path. So, we change our least path to S-B-E and have reached our destination. That is how we use the formula to find out the most optimal path.
With having understood the usage of the formula, let’s take a look at how the algorithm works:
Firstly create 2 lists which will help you understand the path, let’s name them the open and closed list.
The Pseudo-Code of the Algorithm goes like this.
let the openList equal empty list of nodes let the closedList equal empty list of nodes put the startNode on the openList (leave it's f at zero) while the openList is not empty let the currentNode equal the node with the least f value remove the currentNode from the openList add the currentNode to the closedList if currentNode is the goal You've found the end! let the children of the currentNode equal the adjacent nodes for each child in the children if child is in the closedList continue to beginning of for loop child.g = currentNode.g + distance between child and current child.h = distance from child to end child.f = child.g + child.h if child.position is in the openList's nodes positions if the child.g is higher than the openList node's g continue to beginning of for loop add the child to the openList
A* is brilliant when it comes to finding paths from one place to another. It also makes sure that it finds the paths which are the most efficient. I will be showing you 2 codes for now. One with Dijkstra and the other with A* and from that, you can understand why A* is the best when it comes to finding the path from a source to a destination.
Let’s first begin with the Dijkstra’s Implementation.
def Dijkstra(maze, source): infinity = float('infinity') n = len(maze) dist = [infinity] * n previous = [infinity] * n dist = 0 Q = list(range(n)) while Q: u = min(Q, key=lambda n: dist[n]) Q.remove(u) if dist[u] == infinity: break for v in range(n): if maze[u][v] and (v in Q): alt = dist[u] + maze[u][v] if alt < dist[v]: dist[v] = alt previous[v] = u return dist, previous def display_solution(predecessor): cell = len(predecessor) - 1 while cell: print(cell, end='<') cell = predecessor[cell] print(0) maze = ((0, 0, 0, 0, 1, 0), (0, 0, 0, 0, 1, 0), (0, 0, 0, 0, 1, 0), (0, 0, 0, 0, 1, 0), (0, 0, 0, 0, 1, 0), (0, 0, 0, 0, 0, 0)) graph = ( (0, 1, 0, 0, 0, 0,), (1, 0, 1, 0, 1, 0,), (0, 1, 0, 0, 0, 1,), (0, 0, 0, 0, 1, 0,), (0, 1, 0, 1, 0, 0,), (0, 0, 1, 0, 0, 0,), ) values = Dijkstra(graph, 0) print(values) display_solution(values) values = Dijkstra(maze, 0) print(values) display_solution(values)
([0, 1, 2, 3, 2, 3], [inf, 0, 1, 4, 1, 2]) 5<2<1<0 ([0, inf, inf, inf, 1, inf], [inf, inf, inf, inf, 0, inf]) 5<inf<Traceback (most recent call last): File "C:/Users/AkashkumarJainS/PycharmProjects/A Star/dijkstra.py", line 50, in <module> display_solution(values) File "C:/Users/AkashkumarJainS/PycharmProjects/A Star/dijkstra.py", line 26, in display_solution cell = predecessor[cell] TypeError: list indices must be integers or slices, not float
You can see here that there are 2 graphs and Dijkstra fails for one and works for the other. The place where there is an obstruction or does not have a clear path, Dijkstra fails there. It is not able to find the exact ways and methods of how and why it needs to traverse the graph. The output shows that it needs float values and all that but in reality, Dijkstra was not able to find a way between the nodes and because of that, it has marked many ways as infinite. Which our program then says that there is no way to work for this graph and throws an error.
Let’s do the same thing but with the A* Implementation.
class Node(): def __init__(self, parent=None, position=None): self.parent = parent self.position = position self.g = 0 self.h = 0 self.f = 0 def __eq__(self, other): return self.position == other.position def astar(maze, start, end): start_node = Node(None, start) start_node.g = start_node.h = start_node.f = 0 end_node = Node(None, end) end_node.g = end_node.h = end_node.f = 0 open_list =  closed_list =  open_list.append(start_node) while len(open_list) > 0: current_node = open_list current_index = 0 for index, item in enumerate(open_list): if item.f < current_node.f: current_node = item current_index = index open_list.pop(current_index) closed_list.append(current_node) if current_node == end_node: path =  current = current_node while current is not None: path.append(current.position) current = current.parent return path[::-1] children =  for new_position in [(0, -1), (0, 1), (-1, 0), (1, 0), (-1, -1), (-1, 1), (1, -1), (1, 1)]: node_position = (current_node.position + new_position, current_node.position + new_position) if node_position > (len(maze) - 1) or node_position < 0 or node_position > ( len(maze[len(maze) - 1]) - 1) or node_position < 0: continue if maze[node_position][node_position] != 0: continue new_node = Node(current_node, node_position) children.append(new_node) for child in children: for closed_child in closed_list: if child == closed_child: continue child.g = current_node.g + 1 child.h = ((child.position - end_node.position) ** 2) + ( (child.position - end_node.position) ** 2) child.f = child.g + child.h for open_node in open_list: if child == open_node and child.g > open_node.g: continue open_list.append(child) def main(): maze = [[0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 0, 0]] graph = [[0, 1, 0, 0, 0, 0], [1, 0, 1, 0, 1, 0], [0, 1, 0, 0, 0, 1], [0, 0, 0, 0, 1, 0], [0, 1, 0, 1, 0, 0], [0, 0, 1, 0, 0, 0] ] start = (0, 0) end = (5, 5) end1 = (5, 5) path = astar(maze, start, end) print(path) path1 = astar(graph, start, end1) print(path1) if __name__ == '__main__': main()
[(0, 0), (1, 1), (2, 2), (3, 3), (4, 3), (5, 4), (5, 5)] [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5)]
A*, on the other hand, shines here as it knows the graph clearly and knows when there is an obstruction. It is then able to drive itself accordingly to the output that is needed. This is a very practical example of where A* wins where the others fail.
So I hope that you now have a clear idea about what is the A* algorithm, its working and implementation and much more. That is all I have for you guys today. Till next time, take care and happy learning :)
Now that you know about the A* Algorithm, check out the Masters Program in Machine Learning and Artificial Intelligence by Edureka, a trusted online learning company with a network of more than 250,000 satisfied learners spread across the globe.
Edureka’s Machine Learning and Artificial Intelligence Masters’ Program course is designed for students and professionals who want to master this field in the most efficient way. The course offers to code in Python with its introduction and all necessary concepts, Predictive Analysis concepts and Machine Learning, Graphic models, Reinforcement Learning, Natural Language Processing, Deep Learning and AI with lots of projects and assignments.
Got a question for us? Please mention it in the comments section of this “What is the A* Algorithm and How does it work?” blog and we will get back to you as soon as possible.