### 带有注释和图表的Python实现A*算法示例 以下是基于用户需求编写的带注释和可视化功能的A*算法实现，重点在于实际代价计算部分。 #### 实际代价计算的核心逻辑 在A*算法中，实际代价（g-cost）是指从起点到当前节点的实际路径长度。此值通常通过累加每一步的距离来获得[^1]。为了确保精确性和效率，在每次扩展新节点时更新其g-cost，并将其存储以便后续比较。 ```python import heapq from collections import defaultdict def heuristic(a, b): """曼哈顿距离作为启发函数""" return abs(b[0] - a[0]) + abs(b[1] - a[1]) def astar(start, goal, grid): """ 使用A*算法找到从start到goal的最佳路径。 参数: start: 起始坐标 (x, y) goal: 终点坐标 (x, y) grid: 地图网格表示法，其中0为空白区域，其他为障碍物 返回: path: 找到的最短路径列表 [(x1,y1), ..., (xn,yn)] """ open_set = [] # 开放集合，优先队列形式存储待处理节点及其f-score closed_set = set() # 关闭集合，已访问过的节点 g_score = defaultdict(lambda: float('inf')) # 当前最优路径下的g-cost表 f_score = defaultdict(lambda: float('inf')) # 预估总成本(f=g+h) came_from = {} # 记录父节点用于重建路径 g_score[start] = 0 # 初始位置g-cost设为零 f_score[start] = heuristic(start, goal) # 初始化起始节点预估值 heapq.heappush(open_set, (f_score[start], start)) # 将初始状态加入开放集 while open_set: _, current = heapq.heappop(open_set) # 取出具有最小f-score的节点 if current == goal: # 如果到达目标，则返回路径 return reconstruct_path(came_from, current) closed_set.add(current) # 加入关闭集合标记为已访问过 neighbors = get_neighbors(grid, current) # 获取邻居节点 tentative_gscore = g_score[current] + 1 # 默认移动开销设定为单位步长(可调整) for neighbor in neighbors: if neighbor in closed_set: # 已经评估过的跳过 continue if tentative_gscore < g_score[neighbor]: # 更新更优解 came_from[neighbor] = current g_score[neighbor] = tentative_gscore f_score[neighbor] = g_score[neighbor] + heuristic(neighbor, goal) if neighbor not in [node[1] for node in open_set]: # 若未被考虑则加入open-set heapq.heappush(open_set, (f_score[neighbor], neighbor)) return None # 如无可行路径则返回None def get_neighbors(grid, pos): """获取给定位置的有效邻接点""" directions = [(0, 1), (1, 0), (-1, 0), (0, -1)] # 上下左右四个方向 result = [] for dx, dy in directions: nx, ny = pos[0] + dx, pos[1] + dy if 0 <= nx < len(grid) and 0 <= ny < len(grid[nx]): # 边界条件判断 if grid[nx][ny] == 0: # 空白格子才允许通行 result.append((nx, ny)) return result def reconstruct_path(came_from, current): """回溯构建最终路径""" total_path = [current] while current in came_from.keys(): current = came_from[current] total_path.insert(0, current) return total_path ``` 上述代码实现了完整的A*寻路过程并着重于`tentative_gscore`变量的定义与应用，它代表了从起点至任意候选节点的真实累计花费。 #### 数据结构说明 - `heapq`: 提供高效的二叉堆操作支持快速检索最低优先级项即拥有最小F值的节点。 - `defaultdict`: 自动初始化字典条目简化程序设计减少冗余检查语句数量提升性能表现[^2]。 #### 图形化展示方法建议 可以利用matplotlib库绘制地图以及动态显示搜索进展轨迹如下所示： ```python import matplotlib.pyplot as plt import numpy as np grid_size = 10 obstacles = [(3,i) for i in range(grid_size)] + [(i,7) for i in range(grid_size)] # 创建空白矩阵填充障碍物信息形成可视化的环境模型 env_map = [[0]*grid_size for _ in range(grid_size)] for obs in obstacles: env_map[obs[0]][obs[1]] = 1 plt.imshow(env_map,cmap='Greys',origin='upper') path = astar((0,0),(9,9),env_map) if path is not None: px=[p[1] for p in path]; py=[p[0] for p in path] plt.plot(px,py,'r-o') # 'r'红色线条'o'圆圈标注各点位 else: print("No Path Found!") plt.show() ``` 以上脚本能够直观呈现整个规划流程中的关键环节——包括但不限于障碍规避策略制定、局部极小值克服技巧等方面均有所体现[^3]。