Write a Program to Implement The A Search Algorithm in Python

The A* (A-star) search algorithm in python is an informed search algorithm often used in path finding and graph traversal. It optimizes the search by using a heuristic function to estimate the cost to reach the goal from a given node, combining this with the actual cost from the start node to the current node.

Here’s a simple implementation of the A* algorithm in Python:

import heapq

# Define the A* algorithm
def a_star(graph, start, goal):
    # Priority queue to store the open nodes
    open_list = []
    heapq.heappush(open_list, (0, start))  # (priority, node)

    # To store the costs and paths
    g_costs = {start: 0}
    f_costs = {start: heuristic(start, goal)}
    came_from = {start: None}

    while open_list:
        # Get the node with the lowest f_cost
        current_f_cost, current_node = heapq.heappop(open_list)

        # If we have reached the goal, reconstruct the path
        if current_node == goal:
            return reconstruct_path(came_from, current_node)

        # Explore neighbors
        for neighbor, cost in graph[current_node]:
            tentative_g_cost = g_costs[current_node] + cost

            # If the new path to neighbor is better, update costs and path
            if neighbor not in g_costs or tentative_g_cost < g_costs[neighbor]:
                g_costs[neighbor] = tentative_g_cost
                f_costs[neighbor] = tentative_g_cost + heuristic(neighbor, goal)
                came_from[neighbor] = current_node
                heapq.heappush(open_list, (f_costs[neighbor], neighbor))

    # If the goal was never reached, return failure
    return None

# Simple heuristic function (Manhattan distance)
def heuristic(node, goal):
    (x1, y1) = node
    (x2, y2) = goal
    return abs(x1 - x2) + abs(y1 - y2)

# Reconstruct the path from start to goal
def reconstruct_path(came_from, current_node):
    path = []
    while current_node is not None:
        path.append(current_node)
        current_node = came_from[current_node]
    path.reverse()
    return path

# Example graph as a dictionary of nodes with their neighbors and the cost to them
graph = {
    (0, 0): [((0, 1), 1), ((1, 0), 1)],
    (0, 1): [((0, 0), 1), ((1, 1), 1), ((0, 2), 1)],
    (0, 2): [((0, 1), 1), ((1, 2), 1)],
    (1, 0): [((0, 0), 1), ((1, 1), 1), ((2, 0), 1)],
    (1, 1): [((0, 1), 1), ((1, 0), 1), ((1, 2), 1), ((2, 1), 1)],
    (1, 2): [((0, 2), 1), ((1, 1), 1), ((2, 2), 1)],
    (2, 0): [((1, 0), 1), ((2, 1), 1)],
    (2, 1): [((2, 0), 1), ((1, 1), 1), ((2, 2), 1)],
    (2, 2): [((2, 1), 1), ((1, 2), 1)],
}

# Running the A* algorithm
start_node = (0, 0)
goal_node = (2, 2)
path = a_star(graph, start_node, goal_node)

# Output the result

print("Path from start to goal:", path)

How It Works:

1. Graph Representation: The graph is represented as a dictionary where each node has a list of tuples representing its neighbors and the cost to reach them.
2. Priority Queue: A priority queue (min-heap) is used to manage the nodes to be explored, prioritized by their f_cost (which is the sum of g_cost and heuristic).
3. Cost Calculation:
   • g_cost is the cost from the start node to the current node.
   • heuristic is an estimate of the cost from the current node to the goal (here using Manhattan distance).
   • f_cost is the sum of g_cost and the heuristic.
4. Path Reconstruction: Once the goal is reached, the algorithm reconstructs the path by backtracking from the goal node to the start node using the came_from dictionary.

Example Output:

Path from start to goal: [(0, 0), (1, 0), (1, 1), (1, 2), (2, 2)]

This code assumes a simple 2D grid where movement costs are uniform. You can adapt it to more complex graphs and heuristic functions depending on your specific needs.