A* Algorithm in Python: Explained and Implemented

Introduction

In this article, we will explore the A* algorithm, a widely-used pathfinding algorithm, and understand how it can be implemented in Python. We will discuss the problem statement, dive into the algorithmic approach, provide step-by-step explanations, and demonstrate a practical implementation. By the end, you will have a solid understanding of the A* algorithm and its application in graph-based problems.

Problem Statement

The A* algorithm is commonly used for finding the shortest path between two nodes in a graph. It considers both the actual cost of reaching a node from the start node and the estimated cost of reaching the goal node from the current node. This estimated cost is calculated using a heuristic function, which guides the algorithm towards the goal while also considering the actual path cost.

Algorithm

The A* algorithm follows a strategy of exploring nodes with the lowest total cost, which is the sum of the cost from the start node to the current node (known as g-cost) and the estimated cost from the current node to the goal node (known as h-cost). Here are the key steps of the algorithm:

Initialize an open set containing the start node and an empty closed set.
While the open set is not empty, do the following:
- Select the node with the lowest total cost (f-cost) from the open set.
- If the selected node is the goal node, stop and return the path.
- Move the selected node from the open set to the closed set.
- Generate all neighbouring nodes from the selected node.
- For each neighbouring node, calculate the g-cost (path cost from the start to the neighbouring node) and h-cost (estimated cost from the neighbouring node to the goal).
- If the neighbouring node is already in the closed set with a lower f-cost, skip it.
- If the neighbouring node is not in the open set or has a lower f-cost, update its f-cost, g-cost, and parent node, and add it to the open set.
If the open set becomes empty and no path is found, the problem is unsolvable.

Pseudo Code

function AStar(start_node, goal_node, heuristic_function):
    open_set = {start_node}
    closed_set = {}

    while open_set is not empty:
        current_node = node with lowest total cost (f-cost) from open_set

        if current_node is goal_node:
            return reconstruct_path(current_node)

        move current_node from open_set to closed_set

        generate neighboring nodes from current_node

        for each neighboring_node in neighboring_nodes:
            calculate g-cost from start_node to neighboring_node
            calculate h-cost from neighboring_node to goal_node

            if neighboring_node is in closed_set with lower f-cost:
                skip to next neighboring_node

            if neighboring_node is not in open_set or has lower f-cost:
                update f-cost, g-cost, and parent_node of neighboring_node
                add neighboring_node to open_set

    return "No path found"

Implementation

Now, let's dive into the Python implementation of the A* algorithm for graph-based problems:

from queue import PriorityQueue

def AStar(start

_node, goal_node, heuristic_function):
    open_set = PriorityQueue()
    open_set.put((0, start_node))
    g_costs = {start_node: 0}
    parents = {start_node: None}

    while not open_set.empty():
        _, current_node = open_set.get()

        if current_node == goal_node:
            return reconstruct_path(parents, current_node)

        for neighbor in current_node.neighbors:
            g_cost = g_costs[current_node] + current_node.distance_to(neighbor)
            if neighbor not in g_costs or g_cost < g_costs[neighbor]:
                g_costs[neighbor] = g_cost
                f_cost = g_cost + heuristic_function(neighbor, goal_node)
                open_set.put((f_cost, neighbor))
                parents[neighbor] = current_node

    return "No path found"

def reconstruct_path(parents, current_node):
    path = [current_node]
    while parents[current_node]:
        current_node = parents[current_node]
        path.append(current_node)
    return list(reversed(path))

Explanation

Let's break down the key parts of the implementation:

The AStar function takes the start node, goal node, and a heuristic function as input.
We use a PriorityQueue to store the nodes in the open set, prioritized based on their f-cost.
We maintain two dictionaries: g_costs to store the g-cost (path cost from the start node) for each node, and parents to store the parent node for each node in the path.
In each iteration, we retrieve the node with the lowest f-cost from the open set.
We check if the current node is the goal node, and if so, we reconstruct the path and return it.
We generate neighbouring nodes from the current node and calculate their g-costs and f-costs.
If a neighbouring node is not in the open set or has a lower f-cost, we update its g-cost, f-cost, and parent node, and add it to the open set.
If no path is found and the open set becomes empty, we return a "No path found" message.

Example

Let's consider an example where we have a graph representing cities and we want to find the shortest path from the start city to the goal city using the A* algorithm.

class Node:
    def __init__(self, name):
        self.name = name
        self.neighbors = []

    def add_neighbor(self, neighbor, distance):
        self.neighbors.append((neighbor, distance))

    def distance_to(self, neighbor):
        for n, d in self.neighbors:
            if n == neighbor:
                return d
        return float('inf')

# Create the nodes representing cities
A = Node('A')
B = Node('B')
C = Node('C')
D = Node('D')
E = Node('E')

# Define the connections between cities
A.add_neighbor(B, 5)
A.add_neighbor(C, 3)
B.add_neighbor(D, 2)
B.add_neighbor(E, 4)
C.add_neighbor(E, 6)
D.add_neighbor(E, 1)

# Define the heuristic function (Euclidean distance between cities)
def heuristic_function(node, goal):
    distances = {
        'A': 7,
        'B': 6,
        'C': 4,
        'D': 2,
        'E': 0
    }
    return distances[node.name]

start_node = A
goal_node = E

path = AStar(start_node, goal_node, heuristic_function)
print("Shortest path:", [node.name for node in path])

Output:

Shortest path: ['A',

 'B', 'D', 'E']

In this example, the A* algorithm finds the shortest path from city A to city E, which is ['A', 'B', 'D', 'E'].

Conclusion

In this article, we explored the A* algorithm, a powerful pathfinding algorithm commonly used in graph-based problems. We discussed the problem statement, explained the algorithmic approach, provided the pseudo-code, implemented the algorithm in Python, and demonstrated an example usage. The A* algorithm combines actual path costs with estimated costs using a heuristic function, enabling efficient and optimal pathfinding. By understanding and implementing the A* algorithm, you can solve a wide range of graph-based problems efficiently and effectively.