A* search algorithm

A* search is a popular pathfinding algorithm used in various applications, such as robotics, video games, and navigation systems. It is a best-first search algorithm that combines uniform-cost and greedy search advantages. Like uniform-cost search, it evaluates the cost of each potential path from the start node and selects the path with the lowest cost. However, it also uses a heuristic function to estimate the remaining cost to the goal, allowing it to focus its search on the most promising paths, like a greedy search.

The A* search algorithm maintains a priority queue of the new nodes and their tentative distances from the start node, which is the sum of the path cost so far and the heuristic estimate of the remaining cost to the goal. The heuristic function must be admissible, meaning it never overestimates the actual cost to the goal, and is consistent, meaning it satisfies the triangle inequality. This ensures that the A* search algorithm always finds the optimal path to the goal if one exists.

from heapq import heappush, heappop

class Node:
    def __init__(self, name, x, y):
        self.name = name
        self.x = x
        self.y = y
        self.adjacent = []
        self.visited = False
        self.parent = None
        self.g_score = float("inf")
        self.f_score = float("inf")

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

# A* search function
def astar(start, goal):
    open_set = [start]
    start.g_score = 0
    start.f_score = heuristic(start, goal)

    while open_set:
        current = heappop(open_set)

        if current == goal:
            return reconstruct_path(current)

        current.visited = True

        for neighbor in current.adjacent:
            tentative_g_score = current.g_score + distance(current, neighbor)

            if tentative_g_score < neighbor.g_score:
                neighbor.parent = current
                neighbor.g_score = tentative_g_score
                neighbor.f_score = tentative_g_score + heuristic(neighbor, goal)

                if not neighbor.visited:
                    heappush(open_set, neighbor)

    return None

# Helper function to compute the Euclidean distance between two nodes
def distance(node1, node2):
    return ((node1.x - node2.x) ** 2 + (node1.y - node2.y) ** 2) ** 0.5

# Helper function to compute the heuristic estimate of the remaining cost to the goal
def heuristic(node, goal):
    return distance(node, goal)

# Helper function to reconstruct the path from the goal to the start node
def reconstruct_path(current):
    path = []
    while current.parent:
        path.append(current)
        current = current.parent
    path.append(current)
    return list(reversed(path))

# Create a graph
node1 = Node("A", 0, 0)
node2 = Node("B", 1, 1)
node3 = Node("C", 2, 2)
node4 = Node("D", 3, 3)
node5 = Node("E", 4, 4)

node1.adjacent = [node2]
node2.adjacent = [node1, node3]
node3.adjacent = [node2, node4]
node4.adjacent = [node3, node5]
node5.adjacent = [node4]

# Run A* search
start_node = node1
goal_node = node5
path = astar(start_node, goal_node)

# Print the path
if path is not None:
    print([node.name for node in path])
else:
    print("No path found")

In this implementation, the Node the class has an additional x and y attribute to represent its position in 2D space, as well as parent, g_score, and f_score attributes. The g_score represents the cost of the path from the start node to the current node, and the f_score represents the estimated total cost of the path from the start node to the goal node passing through the current node. The heappush and heappop functions are used to maintain a priority queue of nodes to be explored.

The astar the function takes a start node and a goal node as input and uses a priority queue to keep track of the nodes to be explored. It starts by adding the start node to the priority queue, with a g_score of 0 and an .