### A星搜索算法的实现代码 以下是基于 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 (estimated distance to goal) self.f = 0 # Total cost def __eq__(self, other): return self.position == other.position def __lt__(self, other): # For priority queue comparison return self.f < other.f def a_star(maze, start, end): 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) 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] >= len(maze) or node_position[0] < 0 or node_position[1] >= len(maze[0]) or node_position[1] < 0 ): continue if maze[node_position[0]][node_position[1]] != 0: continue new_node = Node(current_node, node_position) children.append(new_node) for child in children: if child in closed_list: continue child.g = current_node.g + 1 child.h = ((child.position[0] - end_node.position[0]) ** 2 + (child.position[1] - end_node.position[1]) ** 2) ** 0.5 child.f = child.g + child.h for open_node in open_list: if child == open_node and child.g > open_node.g: break else: heapq.heappush(open_list, child) return None maze = [ [0, 0, 0, 0, 1, 0], [0, 1, 1, 0, 1, 0], [0, 0, 0, 0, 1, 0], [0, 1, 1, 1, 1, 0], [0, 0, 0, 0, 0, 0] ] start = (0, 0) end = (4, 5) path = a_star(maze, start, end) print(path) ``` 此代码实现了 A 星算法的核心逻辑，包括节点定义、开放列表管理以及启发式函数计算[^1][^2]。 #### 关键点解析 - `Node` 类用于表示网格中的每个位置及其父节点、代价等属性。 - 启发式函数 \( h \) 使用欧几里得距离来估算当前位置到目标的距离[^3]。 - 开放列表通过优先队列 (`heapq`) 维护，确保每次扩展的是总成本最低的节点[^4]。