用Python实现A*算法的代码

在Python中，A*（A-Star）算法通常用于寻找从起点到终点的最短路径，特别是在图或网格搜索中。下面是一个简单的A*算法实现示例，它使用了heapq库来进行优先队列操作：

import heapq

def heuristic(a, b):
    # 这里假设距离函数是对角线距离，对于实际应用可能需要替换为更合适的计算方式
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

class Node:
    def __init__(self, pos, g=0, h=0, f=0):
        self.pos = pos
        self.g = g  # 从起点的距离
        self.h = h  # 目标点的启发式估计
        self.f = f  # 合计值g+h

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

def a_star_search(graph, start, goal):
    open_list = [Node(start)]
    closed_list = set()

    while open_list:
        current = heapq.heappop(open_list)
        if current.pos == goal:
            path = []
            while current is not None:
                path.append(current.pos)
                current = graph[current.pos]
            return path[::-1]  # 返回路径，从终点到起点

        closed_list.add(current.pos)

        for neighbor in graph.neighbors(current.pos):
            tentative_g = current.g + graph.cost(current.pos, neighbor)
            if neighbor not in closed_list or tentative_g < graph.get_cost(neighbor):
                neighbor_node = Node(neighbor, tentative_g, heuristic(neighbor, goal), tentative_g + heuristic(neighbor, goal))
                graph.set_cost(neighbor, tentative_g)  # 更新邻接节点的成本
                if neighbor_node not in open_list:
                    heapq.heappush(open_list, neighbor_node)

    return None  # 如果找不到路径，则返回None

# 示例：假设graph是一个字典，键是位置，值是邻居和成本
# graph = {...}
# start = ...  # 起点坐标
# goal = ...   # 终点坐标
# a_star_search(graph, start, goal)

这个例子中，你需要自定义`Node`类、`graph`结构以及`heuristic`函数以适应你的具体场景。记得在`graph`类中提供邻居查找和成本获取的方法。