A* search algorithm Code With Python

a classic problem in computer science and graph theory. This problem is use to find the shortest path from a starting node to a goal node in a weighted graph, taking into account both the cost of the path already taken and an estimate of the cost of the remaining path to the goal.

The primary aim of utilizing the A* search algorithm is to determine the most optimal route from an initial node to a target node in a graph with assigned weights. This process factors in the cost of the path taken so far and an approximation of the cost of the remaining path leading to the target node.


The A* search algorithm is a pathfinding algorithm that is commonly used in artificial intelligence and robotics. It is a best-first search algorithm that uses a heuristic function to estimate the cost of the remaining path to the goal. The algorithm works by maintaining two lists: an open list of nodes that are to be expanded and a closed list of nodes that have already been expanded.

The algorithm starts by adding the starting node to the open list. Then, it repeatedly selects the node with the lowest f value (the sum of the cost of the path already taken and the estimated cost of the remaining path) from the open list, expands it by generating its child nodes, and adds them to the open list if they have not already been visited. The algorithm continues until the goal node is found or the open list is empty.

					import heapq

class Node:
    def __init__(self, state, parent=None, g=0, h=0):
        self.state = state
        self.parent = parent
        self.g = g
        self.h = h
        self.f = g + h

    def __lt__(self, other):
        return self.f < other.f

def a_star_search(initial_state, goal_state, heuristic_func):
    # Initialize the start node with a zero g value and the given heuristic value
    start_node = Node(initial_state, None, 0, heuristic_func(initial_state, goal_state))

    # Create a priority queue to store the nodes to be expanded
    open_list = []
    heapq.heappush(open_list, start_node)

    # Create a set to keep track of already visited states
    closed_set = set()

    while open_list:
        # Pop the node with the lowest f value from the priority queue
        current_node = heapq.heappop(open_list)

        # Check if the current node is the goal state
        if current_node.state == goal_state:
            # If so, return the solution path
            solution_path = []
            while current_node:
                current_node = current_node.parent
            print("Solution path:", solution_path)
            print("Solution cost:", solution_path[-1].g)

        # Generate the child nodes and add them to the priority queue
        for next_state in get_next_states(current_node.state):
            next_g = current_node.g + get_cost(current_node.state, next_state)
            next_h = heuristic_func(next_state, goal_state)
            next_node = Node(next_state, current_node, next_g, next_h)

            # Check if the next state has already been visited
            if next_state in closed_set:

            # Otherwise, add the next node to the priority queue
            heapq.heappush(open_list, next_node)

        # Add the current state to the set of visited states

    # If no solution is found, return None
    print("No solution found.")

def get_next_states(state):
    # Function to generate the next possible states
    # Implement this function according to your problem

def get_cost(state1, state2):
    # Function to compute the cost of moving from state1 to state2
    # Implement this function according to your problem

def heuristic_func(state, goal_state):
    # Function to compute the heuristic value for a given state
    # Implement this function according to your problem


Table of Contents

Leave a Reply

Your email address will not be published. Required fields are marked *