a星算法python

Sure! Here's an example implementation of the A* algorithm in Python:

import heapq

def heuristic(node, goal):
    # Calculate the Euclidean distance between two points
    return ((node[0] - goal[0]) ** 2 + (node[1] - goal[1]) ** 2) ** 0.5

def astar(graph, start, goal):
    open_set = [(0, start)]  # Priority queue for nodes to be explored
    came_from = {}  # Store the parent of each node
    g_score = {start: 0}  # Cost from start along best known path
    f_score = {start: heuristic(start, goal)}  # Estimated total cost from start to goal

    while open_set:
        current = heapq.heappop(open_set)[1]  # Get the node with the lowest f_score
        if current == goal:
            # Reached the goal
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            path.reverse()
            return path

        for neighbor in graph[current]:
            # Calculate the tentative g_score for the neighbor
            new_g_score = g_score[current] + heuristic(current, neighbor)
            if neighbor not in g_score or new_g_score < g_score[neighbor]:
                # Update the g_score and f_score for the neighbor
                g_score[neighbor] = new_g_score
                f_score[neighbor] = new_g_score + heuristic(neighbor, goal)
                came_from[neighbor] = current
                heapq.heappush(open_set, (f_score[neighbor], neighbor))

    return None  # No path found

# Example usage:
graph = {
    'A': {'B': 5, 'C': 10},
    'B': {'D': 7, 'E': 3},
    'C': {'F': 2},
    'D': {'G': 11},
    'E': {'F': 2},
    'F': {'H': 5},
    'G': {},
    'H': {}
}
start_node = 'A'
goal_node = 'H'
path = astar(graph, start_node, goal_node)
print(path)

In this example, the `graph` dictionary represents a weighted graph where the keys are nodes and the values are dictionaries of neighbors with their corresponding edge weights. The `heuristic` function calculates the heuristic (estimated) distance between two nodes, and the `astar` function implements the A* algorithm to find the shortest path from the `start` node to the `goal` node.

Please note that this is a simplified implementation and may not cover all possible scenarios. You may need to modify it based on your specific requirements.