A* Search Algorithm

 A* Search Algorithm

A* search algorithm is a heuristic search algorithm used to find the shortest path between two nodes in a graph. It uses a heuristic function to estimate the distance from a node to the goal node, and combines this with the actual cost to reach the node to determine the best path to take.

python

# A* search algorithm function

def a_star_search(graph, start, goal):

    queue = [(0, start, [])]

    visited = set()

    while queue:

        cost, node, path = heapq.heappop(queue)

        if node == goal:

        return path + [node]

    if node in visited:

        continue

    visited.add(node)

    for neighbor, neighbor_cost in graph[node].items():

        heapq.heappush(queue, (cost + neighbor_cost + heuristic(neighbor, goal), neighbor, path + [node]))

raise ValueError("No path found")

Heuristic function for A* search

def heuristic(node, goal):

return abs(node[0] - goal[0]) + abs(node[1] - goal[1])

Example usage

graph = {

(0, 0): {(0, 1): 1, (1, 0): 1},

(0, 1): {(0, 0): 1, (1, 1): 1},

(1, 0): {(0, 0): 1, (1, 1): 1},

(1, 1): {(0, 1): 1, (1, 0): 1}

}

start = (0, 0)

goal = (1, 1)

path = a_star_search(graph, start, goal)

print(path) # Output: [(0, 0), (1, 0), (1, 1)]

In this example, we use A* search to find the shortest path between the start node (0,0) and the goal node (1,1) in a 2D grid graph. We define the heuristic function to be the Manhattan distance between two nodes. The function returns the path [(0, 0), (1, 0), (1, 1)] which is the shortest path between the start and goal nodes.