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.
And if you are looking to get certified and learn all the amazingness of Artificial Intelligence and Machine Learning, join the Post Graduate program by Edureka today!
The article comprises of the following sections:
- What is a Search Algorithm?
- Why A* Algorithm?
- The in-and-out of A* Algorithm
- A* Algorithm in Practicality
Let’s get started :)
What is a Search Algorithm?
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.
Why A* Algorithm?
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.
The in-and-out of A* Algorithm
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.
- F – F is the parameter of A* which is the sum of the other parameters G and H and is the least cost from one node to the next node. This parameter is responsible for helping us find the most optimal path from our source to destination.
- G – G is the cost of moving from one node to the other node. This parameter changes for every node as we move up to find the most optimal path.
- H – H is the heuristic/estimated path between the current code to the destination node. This cost is not actual but is, in reality, a guess cost that we use to find which could be the most optimal path between our source and destination.
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.
A* Algorithm():
- Add start node to list
- For all the neighbouring nodes, find the least cost F node
- Switch to the closed list
- For 8 nodes adjacent to the current node
- If the node is not reachable, ignore it. Else
- If the node is not on the open list, move it to the open list and calculate f, g, h.
- If the node is on the open list, check if the path it offers is less than the current path and change to it if it does so.
- Stop working when
- You find the destination
- You cannot find the destination going through all possible points
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
That is all the theory that we need to know for A* algorithm. Let’s see how A* is used in practical cases.
A* Algorithm in Practicality
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[source] = 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[1])
values = Dijkstra(maze, 0)
print(values)
display_solution(values[1])
Output:
([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[1])
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 floatYou 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[0]
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[0] + new_position[0], current_node.position[1] + new_position[1])
if node_position[0] > (len(maze) - 1) or node_position[0] < 0 or node_position[1] > (
len(maze[len(maze) - 1]) - 1) or node_position[1] < 0:
continue
if maze[node_position[0]][node_position[1]] != 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[0] - end_node.position[0]) ** 2) + (
(child.position[1] - end_node.position[1]) ** 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()Output:
[(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.