A星算法做最短路径优化的代码

下面是一个简单的使用A星算法求解最短路径的示例代码：

import heapq

# 计算两个节点之间的距离
def distance(node1, node2):
    return ((node1[0] - node2[0]) ** 2 + (node1[1] - node2[1]) ** 2) ** 0.5

# 计算启发函数的值（即估计从当前节点到目标节点的距离）
def heuristic(node, goal):
    return distance(node, goal)

# A星算法求解最短路径
def astar(start, goal, graph):
    # 初始化起点的信息（距离为0，路径为空）
    start_info = {'node': start, 'distance': 0, 'path': []}
    # 使用堆来存储待处理的节点
    heap = [start_info]
    # 使用集合来存储已处理的节点
    closed = set()

    while heap:
        # 取出堆中距离起点最近的节点
        current_info = heapq.heappop(heap)
        current_node = current_info['node']

        # 如果该节点已处理过，则跳过
        if current_node in closed:
            continue

        # 如果该节点是目标节点，则返回路径
        if current_node == goal:
            return current_info['path'] + [goal]

        # 将该节点标记为已处理
        closed.add(current_node)

        # 处理该节点的所有邻居
        for neighbor in graph[current_node]:
            # 如果邻居已处理过，则跳过
            if neighbor in closed:
                continue

            # 计算从起点到该邻居的距离
            distance_to_neighbor = current_info['distance'] + distance(current_node, neighbor)

            # 如果该邻居还未加入堆中，则将其加入，并更新距离和路径信息
            for info in heap:
                if info['node'] == neighbor:
                    if distance_to_neighbor < info['distance']:
                        info['distance'] = distance_to_neighbor
                        info['path'] = current_info['path'] + [current_node]
                    break
            else:
                neighbor_info = {'node': neighbor, 'distance': distance_to_neighbor,
                                  'path': current_info['path'] + [current_node]}
                heapq.heappush(heap, neighbor_info)

    # 如果无法找到路径，则返回空列表
    return []

在上面的代码中，`start`和`goal`分别代表起点和目标节点，`graph`是一个字典，表示节点之间的连接关系。例如，如果`graph[node]`返回一个列表，其中包含了所有与节点`node`直接相邻的节点，则可以使用下面的代码来构建这个字典：

graph = {}
for node in nodes:
    graph[node] = []
    for other_node in nodes:
        if node != other_node and distance(node, other_node) < max_distance:
            graph[node].append(other_node)

其中，`nodes`是所有节点的列表，`max_distance`是两个节点之间的最大距离（如果两个节点之间的距离超过了这个值，则认为这两个节点不相邻）。