Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

maps
graphs
a*
algorithm

# What is the A* algorithm? Educative Answers Team

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

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. To explain the traversal of the graph above, check out the slides below.

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. 1 of 4
class box():    """A box class for A* Pathfinding"""    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.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 node    start_node = box(None, start)    start_node.g = start_node.h = start_node.f = 0    end_node = box(None, end)    end_node.g = end_node.h = end_node.f = 0    # Initialize both open and closed list    open_list = []    closed_list = []    # Add the start node    open_list.append(start_node)    # Loop until you find the end    while len(open_list) > 0:        # Get the current node        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        # Pop current off open list, add to closed list        open_list.pop(current_index)        closed_list.append(current_node)        # Found the goal        if current_node == end_node:            path = []            current = current_node            while current is not None:                path.append(current.position)                current = current.parent            return path[::-1] # Return reversed path        # Generate children        children = []        for new_position in [(0, -1), (0, 1), (-1, 0), (1, 0), (-1, -1), (-1, 1), (1, -1), (1, 1)]: # Adjacent squares            # Get node position            node_position = (current_node.position + new_position, current_node.position + new_position)            # Make sure within range            if node_position > (len(maze) - 1) or node_position < 0 or node_position > (len(maze[len(maze)-1]) -1) or node_position < 0:                continue            # Make sure walkable terrain            if maze[node_position][node_position] != 0:                continue            # Create new node            new_node = box(current_node, node_position)            # Append            children.append(new_node)        # Loop through children        for child in children:            # Child is on the closed list            for closed_child in closed_list:                if child == closed_child:                    continue            # Create the f, g, and h values            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            # Child is already in the open list            for open_node in open_list:                if child == open_node and child.g > open_node.g:                    continue            # Add the child to the open list            open_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

maps
graphs
a*
algorithm 