A* 是一种路径规划算法。它解决的问题是我有一张地图 我知道起点 start 我知道终点 goal 地图里有障碍物 我要找一条从起点到终点的可走路线比如地图是grid [ [0, 0, 0, 0, 0], [1, 1, 0, 1, 0], [0, 0, 0, 1, 0], [0, 1, 0, 0, 0] ]这里0 可以走 1 障碍物不能走你可以把它想成一个棋盘第0行: 0 0 0 0 0 第1行: 1 1 0 1 0 第2行: 0 0 0 1 0 第3行: 0 1 0 0 0起点start (0, 0)终点goal (4, 3)注意坐标是(x, y) x 第几列 y 第几行所以(0, 0)是左上角。(4, 3)是第 4 列、第 3 行也就是右下附近。2. A* 的核心思想A* 不会乱走。它每次都会判断哪个点最值得我先探索判断方法靠这个公式f g h这里三个字母很重要。g 从起点走到当前点已经走了多少步 h 从当前点到终点估计还要走多少步 f 总估计代价比如当前有一个点current (2, 1)如果从起点走到它已经用了 3 步g 3它离终点估计还差 4 步h 4那么f g h 7另一个点g 5 h 6 f 11那 A* 会优先看f 7的点。因为它看起来更有希望更快到终点。3. h 怎么算这里的h叫 heuristic中文一般叫“启发式函数”。最简单的是曼哈顿距离abs(x1 - x2) abs(y1 - y2)它的意思是横着差多少 竖着差多少比如current (2, 1) goal (4, 3)那x 差距 |2 - 4| 2 y 差距 |1 - 3| 2 h 2 2 4对应代码def heuristic(a, b): x1, y1 a x2, y2 b return abs(x1 - x2) abs(y1 - y2)逐句解释def heuristic(a, b):定义一个函数输入两个点。比如a (2, 1) b (4, 3)然后x1, y1 a x2, y2 b把坐标拆开。return abs(x1 - x2) abs(y1 - y2)返回横向距离加纵向距离。4. 找邻居 get_neighborsA* 每次处理一个点时要看它周围哪些点能走。比如当前点node (2, 1)它周围理论上有四个方向右边: (3, 1) 左边: (1, 1) 下边: (2, 2) 上边: (2, 0)代码是def get_neighbors(node, grid): x, y node directions [ (1, 0), (-1, 0), (0, 1), (0, -1) ] neighbors [] for dx, dy in directions: nx x dx ny y dy if 0 ny len(grid) and 0 nx len(grid[0]): if grid[ny][nx] 0: neighbors.append((nx, ny)) return neighbors这段很关键。先看x, y node如果node (2, 1)那么x 2 y 1再看directions [ (1, 0), (-1, 0), (0, 1), (0, -1) ]这是四个移动方向。(1, 0) x 1往右 (-1, 0) x - 1往左 (0, 1) y 1往下 (0, -1) y - 1往上然后neighbors []创建一个空 list用来装“可以走的邻居”。接着for dx, dy in directions:意思是一个方向一个方向试。第一次dx 1 dy 0第二次dx -1 dy 0第三次dx 0 dy 1第四次dx 0 dy -1然后nx x dx ny y dy算出新点坐标。比如当前点(2, 1)方向(1, 0)nx 2 1 3 ny 1 0 1所以新点是(3, 1)然后检查有没有出界if 0 ny len(grid) and 0 nx len(grid[0]):这句话意思是ny 必须在合法行范围内 nx 必须在合法列范围内比如这个地图有 4 行len(grid) 4所以 y 只能是0, 1, 2, 3每行有 5 列len(grid[0]) 5所以 x 只能是0, 1, 2, 3, 4如果新点没出界再看是不是障碍物if grid[ny][nx] 0:这里一定注意grid[ny][nx]不是grid[nx][ny]因为二维 list 是grid[第几行][第几列]而y 行 x 列所以是grid[y][x]如果这个格子是0说明可以走neighbors.append((nx, ny))把这个点加入邻居列表。最后return neighbors把所有可走邻居返回。5. A* 主函数完整主函数是def astar(grid, start, goal): open_list [] heapq.heappush(open_list, (0, start)) came_from {} g_score {} g_score[start] 0 closed_set set() while open_list: current_f, current heapq.heappop(open_list) if current goal: return reconstruct_path(came_from, current) closed_set.add(current) for neighbor in get_neighbors(current, grid): if neighbor in closed_set: continue tentative_g g_score[current] 1 if neighbor not in g_score or tentative_g g_score[neighbor]: came_from[neighbor] current g_score[neighbor] tentative_g h heuristic(neighbor, goal) f tentative_g h heapq.heappush(open_list, (f, neighbor)) return None我们拆开讲。6. open_list 是什么open_list []open_list是等待被探索的点也就是候选点。然后heapq.heappush(open_list, (0, start))意思是把起点放进去。注意放进去的是(0, start)不是单纯的start因为 A* 要按照f值排序。比如(7, (2, 1))意思是点 (2,1) 的 f 值是 7heapq的作用就是每次自动帮你拿出 f 最小的点7. came_from 是什么came_from {}这是一个字典。作用是记录每个点是从哪里来的比如came_from[(2, 1)] (2, 0)意思是(2,1) 这个点是从 (2,0) 走来的最后找到终点之后就靠这个字典倒推路径。8. g_score 是什么g_score {} g_score[start] 0g_score也是字典。它记录从起点到某个点已经用了多少步起点到起点当然是 0g_score[start] 0比如之后可能有g_score[(2, 1)] 3意思是从起点走到 (2,1) 已经用了 3 步9. closed_set 是什么closed_set set()这是集合。作用是记录已经处理过的点比如一个点已经被处理完了就放进去closed_set.add(current)之后如果又遇到它if neighbor in closed_set: continue就跳过。这样可以避免重复绕圈。10. while open_list 是什么while open_list:意思是只要 open_list 里还有候选点就继续找如果 open_list 空了还没找到终点说明没有路。所以最后return None意思是找不到路径。11. 取出 f 最小的点current_f, current heapq.heappop(open_list)这句意思是从 open_list 里面取出 f 最小的点比如取出来current_f 5 current (2, 1)那当前要处理的点就是(2,1)。这就是 A* 的核心每次优先处理 f 最小的点12. 判断是不是终点if current goal: return reconstruct_path(came_from, current)意思是如果当前点就是终点说明路径找到了然后调用reconstruct_path(came_from, current)把完整路径还原出来。13. 把 current 标记为处理过closed_set.add(current)意思是这个点我已经检查过它的邻居了 以后别重复处理14. 检查 current 的邻居for neighbor in get_neighbors(current, grid):这句意思是把当前点上下左右能走的点拿出来一个一个检查比如current (2, 1)可能返回[(2, 2), (2, 0)]然后循环检查每个邻居。15. 如果邻居处理过就跳过if neighbor in closed_set: continuecontinue的意思是跳过这一次循环直接看下一个 neighbor也就是说如果这个邻居已经处理过了就别重复处理16. 计算 tentative_gtentative_g g_score[current] 1这句非常重要。tentative_g的意思是如果我从 current 走到 neighbor那么 neighbor 的新 g 值是多少因为每走一步代价是 1。所以neighbor 的 g current 的 g 1比如g_score[current] 3那么tentative_g 4意思是如果从当前点走到邻居邻居离起点就是 4 步。17. 判断这条路线是不是更好if neighbor not in g_score or tentative_g g_score[neighbor]:这句意思是如果这个邻居以前没见过 或者 这次走到它的路线比以前更短 那就更新比如以前g_score[neighbor] 8现在tentative_g 5说明现在这条路更短。所以更新。18. 更新 came_fromcame_from[neighbor] current意思是neighbor 是从 current 走过来的比如came_from[(2, 2)] (2, 1)意思是(2,2) 的上一站是 (2,1)19. 更新 g_scoreg_score[neighbor] tentative_g意思是记录从起点走到 neighbor 需要多少步20. 计算 h 和 fh heuristic(neighbor, goal) f tentative_g h这里tentative_g g h 估计到终点还差多少 f g h比如g 4 h 3 f 721. 把 neighbor 加入 open_listheapq.heappush(open_list, (f, neighbor))意思是把这个邻居加入候选点列表 它的优先级是 f之后 A* 会继续从open_list里拿出f最小的点。22. reconstruct_path 是什么代码def reconstruct_path(came_from, current): path [current] while current in came_from: current came_from[current] path.append(current) path.reverse() return path这个函数负责从终点倒着找回起点比如最终到了current (4, 3)然后came_from里记录came_from[(4, 3)] (3, 3) came_from[(3, 3)] (2, 3) came_from[(2, 3)] (2, 2) came_from[(2, 2)] (2, 1) came_from[(2, 1)] (2, 0) came_from[(2, 0)] (1, 0) came_from[(1, 0)] (0, 0)那它就会倒着找(4,3) (3,3) (2,3) (2,2) (2,1) (2,0) (1,0) (0,0)但这个顺序是终点 → 起点所以需要path.reverse()变成起点 → 终点最后返回[(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (2, 3), (3, 3), (4, 3)]23. 完整代码你可以把 Day 03 的完整代码写成这样import heapq def heuristic(a, b): x1, y1 a x2, y2 b return abs(x1 - x2) abs(y1 - y2) def get_neighbors(node, grid): x, y node directions [ (1, 0), (-1, 0), (0, 1), (0, -1) ] neighbors [] for dx, dy in directions: nx x dx ny y dy if 0 ny len(grid) and 0 nx len(grid[0]): if grid[ny][nx] 0: neighbors.append((nx, ny)) return neighbors def reconstruct_path(came_from, current): path [current] while current in came_from: current came_from[current] path.append(current) path.reverse() return path def astar(grid, start, goal): open_list [] heapq.heappush(open_list, (0, start)) came_from {} g_score {} g_score[start] 0 closed_set set() while open_list: current_f, current heapq.heappop(open_list) if current goal: return reconstruct_path(came_from, current) closed_set.add(current) for neighbor in get_neighbors(current, grid): if neighbor in closed_set: continue tentative_g g_score[current] 1 if neighbor not in g_score or tentative_g g_score[neighbor]: came_from[neighbor] current g_score[neighbor] tentative_g h heuristic(neighbor, goal) f tentative_g h heapq.heappush(open_list, (f, neighbor)) return None grid [ [0, 0, 0, 0, 0], [1, 1, 0, 1, 0], [0, 0, 0, 1, 0], [0, 1, 0, 0, 0] ] start (0, 0) goal (4, 3) path astar(grid, start, goal) print(path)24. 最后用人话串起来A* 干的事情就是先把起点放进 open_list 然后每次拿出 f 最小的点 看它是不是终点 如果不是就找它周围能走的邻居 给邻居计算 g、h、f 如果发现更短路线就更新 came_from 和 g_score 然后把邻居放回 open_list 一直重复 直到找到终点最重要的 5 个变量你先背下来open_list 还没探索、但可以考虑的点 closed_set 已经探索过的点 g_score 从起点走到某点已经用了多少步 heuristic 估计某点到终点还差多少步 came_from 记录路径每个点的上一站是谁