What is the A* algorithm?
Get Started With Machine Learning
Learn the fundamentals of Machine Learning with this free course. Future-proof your career by adding ML skills to your toolkit — or prepare to land a job in AI or Data Science.
A * algorithm is a searching algorithm that searches for the shortest path between the initial and the final state. It is used in various applications, such as maps.
In maps the A* algorithm is used to calculate the shortest distance between the source (initial state) and the destination (final state).
How it works
Imagine a square grid which possesses many obstacles, scattered randomly. The initial and the final cell is provided. The aim is to reach the final cell in the shortest amount of time.
Here A* Search Algorithm comes to the rescue:
Explanation
A* algorithm has 3 parameters:
-
g : the cost of moving from the initial cell to the current cell. Basically, it is the sum of all the cells that have been visited since leaving the first cell.
-
h : also known as the heuristic value, it is the estimated cost of moving from the current cell to the final cell. The actual cost cannot be calculated until the final cell is reached. Hence, h is the estimated cost. We must make sure that there is never an over estimation of the cost.
-
f : it is the sum of g and h. So, f = g + h
The way that the algorithm makes its decisions is by taking the f-value into account. The algorithm selects the smallest f-valued cell and moves to that cell. This process continues until the algorithm reaches its goal cell.
Example
A* algorithm is very useful in graph traversals as well. In the following slides, you will see how the algorithm moves to reach its goal state.
Suppose you have the following graph and you apply A* algorithm on it. The initial node is A and the goal node is E.
At every step, the f-value is being re-calculated by adding together the g and h values. The minimum f-value node is selected to reach the goal state. Notice how node B is never visited.
class box():"""A box class for A* Pathfinding"""def __init__(self, parent=None, position=None):self.parent = parentself.position = positionself.g = 0self.h = 0self.f = 0def __eq__(self, other):return self.position == other.positiondef astar(maze, start, end):"""Returns a list of tuples as a path from the given start to the given end in the given board"""# Create start and end nodestart_node = box(None, start)start_node.g = start_node.h = start_node.f = 0end_node = box(None, end)end_node.g = end_node.h = end_node.f = 0# Initialize both open and closed listopen_list = []closed_list = []# Add the start nodeopen_list.append(start_node)# Loop until you find the endwhile len(open_list) > 0:# Get the current nodecurrent_node = open_list[0]current_index = 0for index, item in enumerate(open_list):if item.f < current_node.f:current_node = itemcurrent_index = index# Pop current off open list, add to closed listopen_list.pop(current_index)closed_list.append(current_node)# Found the goalif current_node == end_node:path = []current = current_nodewhile current is not None:path.append(current.position)current = current.parentreturn path[::-1] # Return reversed path# Generate childrenchildren = []for new_position in [(0, -1), (0, 1), (-1, 0), (1, 0), (-1, -1), (-1, 1), (1, -1), (1, 1)]: # Adjacent squares# Get node positionnode_position = (current_node.position[0] + new_position[0], current_node.position[1] + new_position[1])# Make sure within rangeif 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# Make sure walkable terrainif maze[node_position[0]][node_position[1]] != 0:continue# Create new nodenew_node = box(current_node, node_position)# Appendchildren.append(new_node)# Loop through childrenfor child in children:# Child is on the closed listfor closed_child in closed_list:if child == closed_child:continue# Create the f, g, and h valueschild.g = current_node.g + 1child.h = ((child.position[0] - end_node.position[0]) ** 2) + ((child.position[1] - end_node.position[1]) ** 2)child.f = child.g + child.h# Child is already in the open listfor open_node in open_list:if child == open_node and child.g > open_node.g:continue# Add the child to the open listopen_list.append(child)def main():board = [[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],[0, 0, 0, 0, 1, 0, 0, 0, 0, 0]]start = (0, 0)end = (6, 6)path = astar(board, start, end)print(path)if __name__ == '__main__':main()
RELATED TAGS
