### Python 实现 A* 算法 A*算法作为一种启发式搜索方法，在处理大规模节点网络时表现出色[^4]。下面是一个简单的Python实现例子，该实例展示了如何在一个二维网格上应用A*来寻找最短路径。 ```python import heapq class Node: """定义单个节点""" def __init__(self, parent=None, position=None): self.parent = parent self.position = position self.g = 0 # Cost from start to current node self.h = 0 # Heuristic cost estimate for moving from given node to goal self.f = 0 # Total cost of node def __eq__(self, other): return self.position == other.position def astar(maze, start, end): """执行A*搜索算法""" # 创建起始节点和目标节点 start_node = Node(None, start) start_node.g = start_node.h = start_node.f = 0 end_node = Node(None, end) end_node.g = end_node.h = end_node.f = 0 open_list = [] closed_list = [] # 将起始节点加入开放列表并堆化 heapq.heappush(open_list, (start_node.f, start_node)) while len(open_list) > 0: # 获取当前节点 _, current_node = heapq.heappop(open_list) closed_list.append(current_node) # 如果找到了终点则返回路径 if current_node == end_node: path = [] current = current_node while current is not None: path.append(current.position) current = current.parent return path[::-1] children = [] for new_position in [(0, -1), (0, 1), (-1, 0), (1, 0)]: # 获得节点位置 node_position = ( current_node.position[0] + new_position[0], current_node.position[1] + new_position[1] ) # 确认此位置可行(边界内且无障碍物) if (node_position[0] >= 0 and node_position[0] < len(maze)) \ and (node_position[1] >= 0 and node_position[1] < len(maze[0]))\ and maze[node_position[0]][node_position[1]] != 1: new_node = Node(current_node, node_position) children.append(new_node) for child in children: skip_child = False # 计算f,g,h值 child.g = current_node.g + 1 child.h = ((child.position[0] - end_node.position[0]) ** 2 + (child.position[1] - end_node.position[1]) ** 2) child.f = child.g + child.h for closed_child in closed_list: if child == closed_child and child.g > closed_child.g: skip_child = True break if skip_child: continue for opened_item in open_list: if child == opened_item[1]: if child.g > opened_item[1].g: skip_child = True break if skip_child: continue heapq.heappush(open_list, (child.f, child)) return None ``` 上述代码实现了基本的A*算法逻辑，并通过`heapq`模块维护了一个优先队列以高效获取下一个要探索的最佳候选节点。注意这里采用的是欧几里得距离作为估计代价h(n)，也可以根据具体应用场景调整为其他形式的距离计算方式。