### Python 中 A* 算法的实现 A* 是一种启发式搜索算法，广泛应用于路径规划领域。以下是基于给定引用和专业知识构建的一个完整的 Python 版本 A* 算法实现。 #### 节点类定义 为了表示地图中的节点以及其属性（如坐标、代价等），可以创建一个 `Node` 类： ```python class Node: def __init__(self, parent=None, position=None): self.parent = parent # 父节点 self.position = position # 当前位置 (x, y) self.g = 0 # 从起点到当前节点的实际代价 self.h = 0 # 启发函数估计值，即从当前节点到终点的最佳可能代价 self.f = 0 # 总代价 f(n) = g(n) + h(n) def __eq__(self, other): # 判断两个节点是否相等 return self.position == other.position ``` #### 主要逻辑实现 下面是一个基本的 A* 寻路算法框架，适用于二维网格环境下的最短路径计算： ```python import heapq def astar(maze, start, end): """ :param maze: 迷宫矩阵(2D list)，障碍物标记为1，可通行区域标记为0 :param start: 起始点 tuple(x,y) :param end: 终点 tuple(x,y) :return: 返回路径列表 [(x1,y1),(x2,y2)...], 如果无解则返回 None """ # 初始化起始节点和结束节点 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_set = set() # 关闭集合，已访问过的节点不再重复处理 heapq.heappush(open_list, (start_node.f, start_node)) # 将初始节点加入开放列表 while len(open_list) > 0: current_f, current_node = heapq.heappop(open_list) # 取出f值最小的节点 if current_node == end_node: # 找到了目标节点 path = [] temp_current = current_node while temp_current is not None: path.append(temp_current.position) temp_current = temp_current.parent return path[::-1] closed_set.add(current_node) # 加入关闭集 children = [] # 子节点列表 for new_position in [ (-1, 0), (1, 0), (0, -1), (0, 1)]: node_position = ( current_node.position[0] + new_position[0], current_node.position[1] + new_position[1]) # 检查边界条件 if (node_position[0] < 0 or node_position[0] >= len(maze) or node_position[1] < 0 or node_position[1] >= len(maze[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_set: # 已经在关闭集中跳过 continue child.g = current_node.g + 1 # 计算g值 child.h = ((child.position[0] - end_node.position[0]) ** 2 + (child.position[1] - end_node.position[1]) ** 2) ** 0.5 # 曼哈顿距离作为h值 child.f = child.g + child.h # 检查open表中是否存在更优路径 flag = False for _, open_node in open_list: if child == open_node and child.g > open_node.g: flag = True break if flag: continue heapq.heappush(open_list, (child.f, child)) return None # 若未找到路径，则返回None ``` 上述代码实现了标准的 A* 算法流程[^1]，其中使用了优先队列来管理开放列表，并通过曼哈顿距离作为启发函数的一部分[^2]。 #### 测试案例 以下是如何调用该函数并打印结果的例子： ```python maze = [[0, 0, 0, 0], [0, 1, 1, 0], [0, 0, 0, 0]] start = (0, 0) end = (2, 3) path = astar(maze, start, end) if path: print(f'Path found: {path}') else: print('No path exists.') ```