深蓝学院第三章作业我前后磨了三个晚上。第一版用BFS跑出了一条看起来还挺顺眼的路径交作业之前自己拿带权地图一测当场就笑了——那条路根本不是最短路径只是拐弯少。对于一个定位在“路径规划/机器人导航”方向的课程来说第三章作业做到这个程度等于白做。这篇文章就当一次复盘把我在做第三章作业时踩过的坑、想通的原理、最后沉淀下来的代码框架一次性讲清楚。适合正在写这个作业、或者准备从零实现BFS/Dijkstra/A*搜索算法的同学参考。我会从“作业到底在考什么”一直讲到“调试时最容易翻车的地方”最后附上一套可以直接用的实现思路尽量让你少走我走过的弯路。1. 先搞清楚第三章作业在考什么1.1 作业真正要检验的能力很多人在这一步翻车是因为把第三章作业单纯理解成“把三个搜索算法写出来”。不是的。老师真正想看到的是你是否理解这几个算法在路径搜索场景下的差异以及为什么地图上一个像素的差别会导致整条路径完全不同。以我做的这版作业为例第三章对应的知识体系是全局路径搜索在已知静态地图上从起点找到一条能避开障碍、到达目标点的路径。这个场景是机器人导航、游戏寻路、自动驾驶全局规划的基础模块。作业的典型要求是基于一张栅格地图二维网格实现BFS、Dijkstra、A*三种搜索算法。统一输入输出算法可以随时切换。通过可视化观察路径差异并对比搜索效率。分析不同算法的适用场景和代价模型。这里面的关键不是“会写三个函数”而是你要能够解释清楚为什么同一张地图BFS找到的路径和A不一定一样为什么Dijkstra能保证最短但可能搜索范围很大为什么A看起来快但不一定总是最优如果这些答不上来作业大概率只能拿一个“代码跑通”的分。1.2 整个任务拆解成四步心里就有底了我一开始是想一口吃成胖子直接在一份大文件里把地图、搜索、可视化全堆在一起写结果改了一行地图数据后面全乱了。后来我把任务拆成了四个独立模块地图表示与数据准备用二维数组定义栅格0代表可通行1代表障碍物甚至可以用不同的整数值代表不同的代价。节点与搜索框架设计定义统一节点结构、open表/closed表的管理方式三个算法共用一套接口。算法逻辑实现在统一的搜索框架里分别实现BFS、Dijkstra、A*核心差别只在“节点展开顺序”和“代价计算方式”。可视化与结果分析把搜索过程的节点访问顺序画出来把最终路径画出来统计访问节点数、路径长度、耗时。拆完之后你会发现第三章作业其实就是一个典型的“策略模式”应用算法可以像换插头一样换来换去。这个思路不止作业里管用以后做工程也很有价值。2. 动手前先把地图和接口定下来2.1 地图数据结构直接决定算法好不好写我见过有人用图片PNG当作地图输入算法里去读像素颜色判断障碍物。这个方案在展示的时候确实炫但做作业和调试的时候非常痛苦因为你没法快速构造一个测试用例来确定算法行为。我推荐先把地图写成一个二维数组这样每一步都是可控的。以10x10地图为例最简单的地图长这样import numpy as np # 0: 空地, 1: 障碍物, 2: 起点, 3: 终点 grid np.array([ [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 1, 0, 1, 1, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 1, 0, 0, 0], [0, 1, 1, 0, 1, 1, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 1, 0], [0, 0, 0, 1, 1, 0, 0, 0, 1, 0], [0, 0, 0, 0, 0, 0, 1, 1, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], ])为什么要用数组而不是图片因为你可以快速肉眼验证算法的每一步是否符合预期。比如你知道从左上角到右下角理论上最短要走多少步如果算法给出的路径长度不对你能立刻定位是哪一步出了问题。我还习惯再定义一张“代价地图”把每个格子可以走过去的“成本”也做成二维数组方便后面测Dijkstra和A*。有一点需要注意地图的坐标系。我建议统一成grid[row][col]第一维是y方向第二维是x方向。不然画图和索引容易搞混尤其是你在地图上标注起点和终点时。2.2 节点的定义比算法本身更重要如果你把节点定义成简单的(x, y)坐标那你的BFS也许还能凑合跑但Dijkstra和A*一定会写得很别扭因为你没有地方存累计代价g值、启发式h值、以及父节点。我建议不管用什么语言先把节点定义成一个类或者结构体class Node: def __init__(self, row, col): self.row row self.col col self.g float(inf) # 从起点到当前节点的实际代价 self.f float(inf) # 估价: g h self.parent None # 用于回溯路径这里面的g值是个关键。BFS里其实不关心代价只关心“第几层被访问”所以BFS的每条边长可以看成1Dijkstra里g是实实在在的累加距离A*里的f是g hh是当前节点到终点的估计代价。而parent字段是另一个容易被忽略的细节。没有它你最后找到了目标节点也没法重建整条路径。你只能在搜索过程中另外维护一个“访问表”记录每个节点是从哪个节点来的本质上也相当于父节点指针。另外不管什么算法都要实现一个“邻居生成器”。这个函数接收一个坐标返回所有可通行的相邻节点def get_neighbors(grid, node, allow_diagonalFalse): neighbors [] direction [(-1,0),(1,0),(0,-1),(0,1)] if allow_diagonal: direction [(-1,-1),(-1,1),(1,-1),(1,1)] for dr, dc in direction: nr, nc node.row dr, node.col dc if 0 nr grid.shape[0] and 0 nc grid.shape[1]: if grid[nr][nc] ! 1: neighbors.append((nr, nc)) return neighbors这里有两个容易踩的坑。第一个是坐标越界检查必须写在“可通行判断”之前第二个是斜向移动要不要允许需要提前想清楚。允许斜向移动会显著影响最终路径长度和路径形状下一章的调试部分我会专门说“穿墙”问题。2.3 可视化在debug时不是装饰品第二章你可能还在用打印的方式调试但到路径搜索就必须上可视化了。因为路径搜索的结果是“一张图上的轨迹”你看打印出来的坐标列表很难发现路径拐弯是否合理。我用的方案是matplotlib画网格把障碍物涂黑、起始点标绿、终点标红搜索访问过的点涂成浅色最终路径用蓝线连起来。import matplotlib.pyplot as plt def draw_grid(grid, visitedNone, pathNone, startNone, endNone): fig, ax plt.subplots(figsize(8, 8)) ax.imshow(grid, cmapgray_r, originupper) if visited: for (r, c) in visited: ax.plot(c, r, s, colorlightblue, markersize10) if path: path_r [p[0] for p in path] path_c [p[1] for p in path] ax.plot(path_c, path_r, b-, linewidth3) if start: ax.plot(start[1], start[0], go, markersize12) if end: ax.plot(end[1], end[0], ro, markersize12) ax.set_xlim(-0.5, grid.shape[1]-0.5) ax.set_ylim(grid.shape[0]-0.5, -0.5) ax.grid(True) plt.show()这段代码大约是够用的。需要注意的是imshow的坐标轴和plot的坐标轴方向可能不同所以我在最后手动把y轴反转保证显示坐标和数组索引对应。如果没有这一步你会发现路径画出来是上下颠倒的那种错误特别坑因为人和图对不上短时间很难反应过来。3. 三个搜索算法的核心实现3.1 BFS先记住它是无权图的解法BFS的思路非常简单从起点出发先把起点放进队列然后一层一层往外扩散直到找到终点。因为每一层的步数都相同所以第一个到达终点的路径就是“经过格子数最少”的路径。但这里有个大坑BFS不关心边的权重。在栅格地图中每条边如果都代表固定代价那BFS找到的就是最短路径一旦你引入了“地形代价”例如沼泽地代价是3普通路是1BFS找出来的就可能完全不是最短路径因为BFS只会看“经过几个格子”不会看“经过格子总代价”。我做第一版作业时就是在地图上加了几个高代价区域BFS却强行穿了过去路径总代价比绕路高得多。这个不是代码写错而是算法模型和问题模型不匹配。BFS的核心代码结构是这样from collections import deque def bfs(grid, start, end): queue deque() queue.append(start) visited set() visited.add((start.row, start.col)) while queue: node queue.popleft() if (node.row, node.col) (end.row, end.col): return reconstruct_path(node) for nr, nc in get_neighbors(grid, node): if (nr, nc) not in visited: visited.add((nr, nc)) child Node(nr, nc) child.parent node queue.append(child) return NoneBFS最值得留意的细节是访问标记要在入队时立刻打上而不是出队时才打。如果你出队才标记同一个节点可能被多个邻居同时入队导致队列膨胀还会破坏“先到先得”的层级关系。我自己第一次写就把visited.add放在了出队之后结果算法搜出一堆重复点路径也没最短性质。3.2 Dijkstra把“距离”当成优先级Dijkstra算法跟BFS最大的区别是它不再用一个先入先出的队列而是用一个“每次弹出当前累计代价最小节点”的优先队列。这样算法可以保证当某个节点第一次从优先队列里被弹出时它的g值就是从起点到该节点的最短距离。这个思想很难几句话讲透我习惯用“地图导航里的绕路”来理解。BFS像一个只能一步一步按圈子往外扩的人Dijkstra则像一个随身带着里程表的人总是优先走“已走距离最短”的那条线。Dijkstra要处理的核心问题就是“松弛更新”。当你从当前节点访问邻居时如果通过当前节点走到邻居的代价比邻居原来记录的g值更小就把邻居的g值更新并把邻居或更新后的状态重新放入优先队列import heapq def dijkstra(grid, start, end): start.g 0 open_heap [(start.g, start.row, start.col)] node_dict {(start.row, start.col): start} visited set() while open_heap: current_g, r, c heapq.heappop(open_heap) current node_dict[(r, c)] if (r, c) in visited: continue if (r, c) (end.row, end.col): return reconstruct_path(current) visited.add((r, c)) for nr, nc in get_neighbors(grid, current): if (nr, nc) in visited: continue cost 1 # 这里可以换成地形代价 new_g current.g cost if (nr, nc) not in node_dict: child Node(nr, nc) child.g new_g child.parent current node_dict[(nr, nc)] child heapq.heappush(open_heap, (new_g, nr, nc)) elif new_g node_dict[(nr, nc)].g: node_dict[(nr, nc)].g new_g node_dict[(nr, nc)].parent current heapq.heappush(open_heap, (new_g, nr, nc)) return NoneDijkstra的正确性关键在于“优先队列里弹出的值保证是非递减的”因此每个节点的最短路径一旦确定就不会再被后面的节点刷新。但很多代码有性能问题open_heap里同一个节点可能被压入多次弹出时会重复展开。解决办法就是我在代码里加的那个visited集合弹出的节点如果已经访问过就直接跳过。这一步必不可少否则算法虽然结果正确但时间会指数级增长。我第一次跑一个100x100的地图时因为没有跳过已访问节点跑了十几秒也没出结果加上之后瞬间就出结果了。3.3 A*加一个“目标方向感”的启发式A*在Dijkstra基础上加了一个启发函数h用来估算当前节点到终点的代价。f g h优先队列按照f排序这样搜索就会更偏向“看起来离目标近的方向”而不是朝所有方向均匀扩散。这是第三章作业最核心的一个节也是老师最喜欢追问细节的地方。启发函数怎么选直接影响搜索效率。我用的最常见方案是曼哈顿距离def heuristic(row, col, end_row, end_col): return abs(row - end_row) abs(col - end_col)如果地图允许斜向移动曼哈顿距离会高估实际代价因为走斜线比“先横再竖”更短所以这时候更适合用欧几里得距离def heuristic_euclidean(row, col, end_row, end_col): return ((row - end_row) ** 2 (col - end_col) ** 2) ** 0.5A*还有一个重要的细节为了确保算法一定能找到最短路径启发函数必须“可采纳”也就是h不能高估实际剩余代价。如果高估了算法会变得更快但会丢掉最优性。这个性质在作业答辩时经常被考你一定要能用自己的话说清楚。A*的代码结构和Dijkstra几乎一样区别只在计算fdef astar(grid, start, end, heuristic): start.g 0 start.f start.g heuristic(start.row, start.col, end.row, end.col) open_heap [(start.f, start.row, start.col)] node_dict {(start.row, start.col): start} visited set() while open_heap: current_f, r, c heapq.heappop(open_heap) current node_dict[(r, c)] if (r, c) in visited: continue if (r, c) (end.row, end.col): return reconstruct_path(current) visited.add((r, c)) for nr, nc in get_neighbors(grid, current): if (nr, nc) in visited: continue cost 1 new_g current.g cost new_h heuristic(nr, nc, end.row, end.col) new_f new_g new_h if (nr, nc) not in node_dict: child Node(nr, nc) child.g new_g child.f new_f child.parent current node_dict[(nr, nc)] child heapq.heappush(open_heap, (new_f, nr, nc)) elif new_g node_dict[(nr, nc)].g: node_dict[(nr, nc)].g new_g node_dict[(nr, nc)].f new_g new_h node_dict[(nr, nc)].parent current heapq.heappush(open_heap, (new_f, nr, nc)) return NoneA写起来不难难的是理解它和Dijkstra的区别到底在哪里。我自己的理解是Dijkstra把搜索队列按“已经付出的代价”排序而A把搜索队列按“已经付出的代价预估剩余代价”排序。后者因为多了一个目标方向信息所以可以少访问很多无关区域。3.4 三种算法在相同地图上的差异对比我做完三种算法之后用同样的地图、同样的起点终点跑了一遍统计了几个关键指标。这里贴出来给大家一个直观参考地图是30x30随机生成15%障碍物4邻域移动算法访问节点数路径长度运行耗时约是否保证最短BFS约570420.8ms无权图下是Dijkstra约620421.2ms总是A*曼哈顿距离约320420.6ms是可采纳启发这个表格大概能解释为什么实际工程里A最常用同样的最短路径A只需要访问大约一半的节点意味着计算量更小。但Dijkstra并没有被淘汰因为Dijkstra不需要启发函数在某些无法设计合理启发函数的场景下更稳妥。顺带说一句如果地图特别大比如几万个节点A配合曼哈顿距离依然会慢。工程上通常会做分级规划、跳点搜索、或者用双向A进一步压缩搜索空间。这些在第四章作业里大概率会碰到。4. 调试现场与常见问题速查4.1 为什么我的A*偶尔不是最优这是我在深蓝学院第三章作业中第一次撞出的一个非常隐蔽的问题我把h设成了曼哈顿距离但地图上允许斜向移动。斜向移动的实际代价是sqrt(2)而曼哈顿距离把斜向移动估算成2实际上高估了剩余代价导致A*可能错过真正最短的斜线路径。处理方式有两种。第一种是如果不使用斜向移动就只用四邻域曼哈顿距离完美匹配保证最优第二种是允许斜向移动但用欧氏距离作为启发函数不过欧氏距离不是完美的“整数格子距离”在一些特定地图上依然可能出现非最优所以更稳妥的做法是把斜向移动的代价直接设为1然后用切比雪夫距离或欧氏距离。这个问题的根源是你怎么定义移动代价而不是算法本身。4.2 open表性能为什么越来越慢我的第一次A*实现里open表用的是Python的list每次取最小值都用min(open_list)再把最小值删掉。小地图看不出问题但地图放大到100x100之后程序肉眼可见地卡顿。原因很简单min是O(n)操作每次扩展一个节点都要遍历整个open表整体复杂度变成O(n^2)。作业规模小的时候无所谓但你要养成用heapq或者priority_queue的习惯。C里用std::priority_queuePython里用heapq弹出的复杂度是O(log n)整体性能差距巨大。这算是我在工程上第一次体会到“数据结构选择”对程序性能的直接影响。之前课上讲堆、讲优先队列我都觉得是纸面知识直到被100x100的地图教育了一顿才彻底记住。4.3 斜着走必须小心“穿墙”栅格地图里允许斜向移动时一定要处理“墙角穿模”问题。比如当前节点在障碍物的左上角右方和下方是空地右下角也是空地如果你直接斜着走到右下角路径就会贴着一个障碍物角走视觉上看起来像穿墙了。解决方法是允许斜向时额外检查当前节点到目标邻居之间的两个正交方向是否都可行。如果其中一个方向是障碍物就禁止斜向走过去。这个规则在游戏寻路中也很常见叫“不允许沿墙滑行”。代码写起来很简单在get_neighbors里加几个判断即可if dr ! 0 and dc ! 0: # 斜向移动检查两个正交方向 if grid[r dr][c] 1 or grid[r][c dc] 1: continue不加这个检查算法结果在数据上大概率也是合法的但在可视化图上看起来非常奇怪老师一眼就能看出你没处理细节。这也是作业能不能从“跑通”到“优秀”的一个分水岭。4.4 路线图“卡死”在死胡同怎么排查写A*和Dijkstra初期我经常遇到一个问题算法在某个区域搜索了很久输出路径却绕了远路甚至根本找不到终点。排查思路有三步。第一步检查地图坐标是否正确先在代码里输出起点和终点的坐标手动在地图上确认没有放反。第二步在算法里加一个简单的打印轮数每访问1000个节点打印一次当前正在处理的节点坐标看搜索区域是不是在被障碍物挡住的地方反复绕。如果绕来绕去出不去很可能是邻居生成逻辑漏掉了某个方向或者地图边界判断写错了。第三步做一个极小地图测试比如3x3地图手算最短路径看算法答案对不对。我强烈建议你准备一个“测试套件”包含几个不同特性的小地图一个空地地图验证往返路径长度是否对称、一个单排障碍地图验证绕障能力、一个全障碍地图包围终点验证无解处理。每一次改动代码之后都先跑一遍测试套件再跑大图。看似多花两分钟实际上能省下好几小时的瞎调试时间。下面的表是我自己整理的常见问题速查分享出来基本覆盖了我在做第三章作业期间遇到的所有主要麻烦现象可能原因解决办法路径不是最短使用BFS处理带权地图换成Dijkstra或A*A*结果比Dijkstra长启发函数高估了剩余代价改成可采纳的曼哈顿/欧氏距离地图一大就卡死open表用了list取最小值改用优先队列路径穿墙/贴墙斜向移动没有检查正交邻居在get_neighbors中增加斜向校验找不到终点边界检查与障碍判断顺序写反先判断bound再判断障碍搜索范围异常大启发函数可能为0或设置错误检查h是否被重置或覆盖路径反向回溯父节点时顺序未反转reconstruct_path需要reverse另外还有一个小建议在实现所有搜索算法之前先写一个统一的路径重建函数def reconstruct_path(node): path [] while node is not None: path.append((node.row, node.col)) node node.parent return path[::-1] # 反转成从起点到终点这个函数看起来简单但很容易写错。我第一次写的时候忘记反转结果可视化出来的路径从终点指向起点我还以为是算法问题排错了半小时才发现是回溯方向反了。4.5 调参技巧先把g值权重固定再谈启发函数很多人第一次接触A*时会想调整f g h里的权重比如改成f g 2*h让算法更激进地奔着终点去。这个做法在工程上确实可以加速搜索但代价是可能得到次优路径。做作业的时候我建议先老老实实用f g h确保算法最优性没有问题再尝试调权重并且对比调权重前后的路径质量和访问节点数。自己动手做一次这个对比远比死记“权重大会导致非最优”要深刻得多。我调权重时发现把h的权重从1调到1.5访问节点数下降了约四成但路径长度偶尔会多出几个格子。对于实际导航来说这可能就够用了但对于作业来说最好在报告里清楚地说明自己做了这个实验并分析利弊。这会让你的作业明显高出别人一截。5. 从作业到工程的三个额外体会第三章作业做到后面你会发现它已经不只是“写三个算法”这么简单。它其实在教你工程上常用的套路统一接口、策略切换、可视化调试。这三个能力一个比一个值钱。我第一次做的时候三个算法分散在三个文件里每个文件都要重新读取地图输出格式还不统一最后写实验报告的时候差点被逼疯。后来我重构了一版把搜索部分封装成一个PathSolver类传入一个整数参数就能切换BFS/Dijkstra/A*主流程只负责读地图、调solver、画图。这个重构大约花了一个小时但之后写报告、做对比实验、甚至改动地图数据都变得非常顺畅。另一个体会是可视化对理解算法的作用真的被低估了。在没画搜索过程之前我以为Dijkstra和A的差别就是“有启发和没启发”。直到我亲眼看到Dijkstra像一个圆一样均匀扩散而A像一支箭一样直奔终点我才真正理解了“搜索效率”这个抽象概念到底意味着什么。我建议你也做一张“搜索过程扩散图”把访问顺序按时间先后用颜色深浅表示出来。这张图放进作业报告里视觉冲击力很强也能体现你对搜索算法的理解深度。导师看到这种图通常都会多问几句细节而你在做图的过程中其实已经把细节都弄清楚了完全不怕问。最后再分享一个写实验报告的小技巧除了贴路径图、统计表我还会放两个“负向实验”。比如跑一张Dijkstra在地图上有很多高代价区域的地图然后展示BFS在同一张地图上绕了远路又比如跑一张只有一条窄通道的地图看看A*在海量开阔区域里的搜索范围。这种对比实验不需要多两三个足矣但能非常有说服力地展示你已经理解了每个算法的适用场景和局限。很多人做作业只展示“成功案例”那其实是不够的。学会展示“失败案例”并解释原因才是区分作业质量的关键。
栅格地图路径规划：BFS、Dijkstra、A*算法实现与调试复盘
深蓝学院第三章作业我前后磨了三个晚上。第一版用BFS跑出了一条看起来还挺顺眼的路径交作业之前自己拿带权地图一测当场就笑了——那条路根本不是最短路径只是拐弯少。对于一个定位在“路径规划/机器人导航”方向的课程来说第三章作业做到这个程度等于白做。这篇文章就当一次复盘把我在做第三章作业时踩过的坑、想通的原理、最后沉淀下来的代码框架一次性讲清楚。适合正在写这个作业、或者准备从零实现BFS/Dijkstra/A*搜索算法的同学参考。我会从“作业到底在考什么”一直讲到“调试时最容易翻车的地方”最后附上一套可以直接用的实现思路尽量让你少走我走过的弯路。1. 先搞清楚第三章作业在考什么1.1 作业真正要检验的能力很多人在这一步翻车是因为把第三章作业单纯理解成“把三个搜索算法写出来”。不是的。老师真正想看到的是你是否理解这几个算法在路径搜索场景下的差异以及为什么地图上一个像素的差别会导致整条路径完全不同。以我做的这版作业为例第三章对应的知识体系是全局路径搜索在已知静态地图上从起点找到一条能避开障碍、到达目标点的路径。这个场景是机器人导航、游戏寻路、自动驾驶全局规划的基础模块。作业的典型要求是基于一张栅格地图二维网格实现BFS、Dijkstra、A*三种搜索算法。统一输入输出算法可以随时切换。通过可视化观察路径差异并对比搜索效率。分析不同算法的适用场景和代价模型。这里面的关键不是“会写三个函数”而是你要能够解释清楚为什么同一张地图BFS找到的路径和A不一定一样为什么Dijkstra能保证最短但可能搜索范围很大为什么A看起来快但不一定总是最优如果这些答不上来作业大概率只能拿一个“代码跑通”的分。1.2 整个任务拆解成四步心里就有底了我一开始是想一口吃成胖子直接在一份大文件里把地图、搜索、可视化全堆在一起写结果改了一行地图数据后面全乱了。后来我把任务拆成了四个独立模块地图表示与数据准备用二维数组定义栅格0代表可通行1代表障碍物甚至可以用不同的整数值代表不同的代价。节点与搜索框架设计定义统一节点结构、open表/closed表的管理方式三个算法共用一套接口。算法逻辑实现在统一的搜索框架里分别实现BFS、Dijkstra、A*核心差别只在“节点展开顺序”和“代价计算方式”。可视化与结果分析把搜索过程的节点访问顺序画出来把最终路径画出来统计访问节点数、路径长度、耗时。拆完之后你会发现第三章作业其实就是一个典型的“策略模式”应用算法可以像换插头一样换来换去。这个思路不止作业里管用以后做工程也很有价值。2. 动手前先把地图和接口定下来2.1 地图数据结构直接决定算法好不好写我见过有人用图片PNG当作地图输入算法里去读像素颜色判断障碍物。这个方案在展示的时候确实炫但做作业和调试的时候非常痛苦因为你没法快速构造一个测试用例来确定算法行为。我推荐先把地图写成一个二维数组这样每一步都是可控的。以10x10地图为例最简单的地图长这样import numpy as np # 0: 空地, 1: 障碍物, 2: 起点, 3: 终点 grid np.array([ [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 1, 0, 1, 1, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 1, 0, 0, 0], [0, 1, 1, 0, 1, 1, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 1, 0], [0, 0, 0, 1, 1, 0, 0, 0, 1, 0], [0, 0, 0, 0, 0, 0, 1, 1, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], ])为什么要用数组而不是图片因为你可以快速肉眼验证算法的每一步是否符合预期。比如你知道从左上角到右下角理论上最短要走多少步如果算法给出的路径长度不对你能立刻定位是哪一步出了问题。我还习惯再定义一张“代价地图”把每个格子可以走过去的“成本”也做成二维数组方便后面测Dijkstra和A*。有一点需要注意地图的坐标系。我建议统一成grid[row][col]第一维是y方向第二维是x方向。不然画图和索引容易搞混尤其是你在地图上标注起点和终点时。2.2 节点的定义比算法本身更重要如果你把节点定义成简单的(x, y)坐标那你的BFS也许还能凑合跑但Dijkstra和A*一定会写得很别扭因为你没有地方存累计代价g值、启发式h值、以及父节点。我建议不管用什么语言先把节点定义成一个类或者结构体class Node: def __init__(self, row, col): self.row row self.col col self.g float(inf) # 从起点到当前节点的实际代价 self.f float(inf) # 估价: g h self.parent None # 用于回溯路径这里面的g值是个关键。BFS里其实不关心代价只关心“第几层被访问”所以BFS的每条边长可以看成1Dijkstra里g是实实在在的累加距离A*里的f是g hh是当前节点到终点的估计代价。而parent字段是另一个容易被忽略的细节。没有它你最后找到了目标节点也没法重建整条路径。你只能在搜索过程中另外维护一个“访问表”记录每个节点是从哪个节点来的本质上也相当于父节点指针。另外不管什么算法都要实现一个“邻居生成器”。这个函数接收一个坐标返回所有可通行的相邻节点def get_neighbors(grid, node, allow_diagonalFalse): neighbors [] direction [(-1,0),(1,0),(0,-1),(0,1)] if allow_diagonal: direction [(-1,-1),(-1,1),(1,-1),(1,1)] for dr, dc in direction: nr, nc node.row dr, node.col dc if 0 nr grid.shape[0] and 0 nc grid.shape[1]: if grid[nr][nc] ! 1: neighbors.append((nr, nc)) return neighbors这里有两个容易踩的坑。第一个是坐标越界检查必须写在“可通行判断”之前第二个是斜向移动要不要允许需要提前想清楚。允许斜向移动会显著影响最终路径长度和路径形状下一章的调试部分我会专门说“穿墙”问题。2.3 可视化在debug时不是装饰品第二章你可能还在用打印的方式调试但到路径搜索就必须上可视化了。因为路径搜索的结果是“一张图上的轨迹”你看打印出来的坐标列表很难发现路径拐弯是否合理。我用的方案是matplotlib画网格把障碍物涂黑、起始点标绿、终点标红搜索访问过的点涂成浅色最终路径用蓝线连起来。import matplotlib.pyplot as plt def draw_grid(grid, visitedNone, pathNone, startNone, endNone): fig, ax plt.subplots(figsize(8, 8)) ax.imshow(grid, cmapgray_r, originupper) if visited: for (r, c) in visited: ax.plot(c, r, s, colorlightblue, markersize10) if path: path_r [p[0] for p in path] path_c [p[1] for p in path] ax.plot(path_c, path_r, b-, linewidth3) if start: ax.plot(start[1], start[0], go, markersize12) if end: ax.plot(end[1], end[0], ro, markersize12) ax.set_xlim(-0.5, grid.shape[1]-0.5) ax.set_ylim(grid.shape[0]-0.5, -0.5) ax.grid(True) plt.show()这段代码大约是够用的。需要注意的是imshow的坐标轴和plot的坐标轴方向可能不同所以我在最后手动把y轴反转保证显示坐标和数组索引对应。如果没有这一步你会发现路径画出来是上下颠倒的那种错误特别坑因为人和图对不上短时间很难反应过来。3. 三个搜索算法的核心实现3.1 BFS先记住它是无权图的解法BFS的思路非常简单从起点出发先把起点放进队列然后一层一层往外扩散直到找到终点。因为每一层的步数都相同所以第一个到达终点的路径就是“经过格子数最少”的路径。但这里有个大坑BFS不关心边的权重。在栅格地图中每条边如果都代表固定代价那BFS找到的就是最短路径一旦你引入了“地形代价”例如沼泽地代价是3普通路是1BFS找出来的就可能完全不是最短路径因为BFS只会看“经过几个格子”不会看“经过格子总代价”。我做第一版作业时就是在地图上加了几个高代价区域BFS却强行穿了过去路径总代价比绕路高得多。这个不是代码写错而是算法模型和问题模型不匹配。BFS的核心代码结构是这样from collections import deque def bfs(grid, start, end): queue deque() queue.append(start) visited set() visited.add((start.row, start.col)) while queue: node queue.popleft() if (node.row, node.col) (end.row, end.col): return reconstruct_path(node) for nr, nc in get_neighbors(grid, node): if (nr, nc) not in visited: visited.add((nr, nc)) child Node(nr, nc) child.parent node queue.append(child) return NoneBFS最值得留意的细节是访问标记要在入队时立刻打上而不是出队时才打。如果你出队才标记同一个节点可能被多个邻居同时入队导致队列膨胀还会破坏“先到先得”的层级关系。我自己第一次写就把visited.add放在了出队之后结果算法搜出一堆重复点路径也没最短性质。3.2 Dijkstra把“距离”当成优先级Dijkstra算法跟BFS最大的区别是它不再用一个先入先出的队列而是用一个“每次弹出当前累计代价最小节点”的优先队列。这样算法可以保证当某个节点第一次从优先队列里被弹出时它的g值就是从起点到该节点的最短距离。这个思想很难几句话讲透我习惯用“地图导航里的绕路”来理解。BFS像一个只能一步一步按圈子往外扩的人Dijkstra则像一个随身带着里程表的人总是优先走“已走距离最短”的那条线。Dijkstra要处理的核心问题就是“松弛更新”。当你从当前节点访问邻居时如果通过当前节点走到邻居的代价比邻居原来记录的g值更小就把邻居的g值更新并把邻居或更新后的状态重新放入优先队列import heapq def dijkstra(grid, start, end): start.g 0 open_heap [(start.g, start.row, start.col)] node_dict {(start.row, start.col): start} visited set() while open_heap: current_g, r, c heapq.heappop(open_heap) current node_dict[(r, c)] if (r, c) in visited: continue if (r, c) (end.row, end.col): return reconstruct_path(current) visited.add((r, c)) for nr, nc in get_neighbors(grid, current): if (nr, nc) in visited: continue cost 1 # 这里可以换成地形代价 new_g current.g cost if (nr, nc) not in node_dict: child Node(nr, nc) child.g new_g child.parent current node_dict[(nr, nc)] child heapq.heappush(open_heap, (new_g, nr, nc)) elif new_g node_dict[(nr, nc)].g: node_dict[(nr, nc)].g new_g node_dict[(nr, nc)].parent current heapq.heappush(open_heap, (new_g, nr, nc)) return NoneDijkstra的正确性关键在于“优先队列里弹出的值保证是非递减的”因此每个节点的最短路径一旦确定就不会再被后面的节点刷新。但很多代码有性能问题open_heap里同一个节点可能被压入多次弹出时会重复展开。解决办法就是我在代码里加的那个visited集合弹出的节点如果已经访问过就直接跳过。这一步必不可少否则算法虽然结果正确但时间会指数级增长。我第一次跑一个100x100的地图时因为没有跳过已访问节点跑了十几秒也没出结果加上之后瞬间就出结果了。3.3 A*加一个“目标方向感”的启发式A*在Dijkstra基础上加了一个启发函数h用来估算当前节点到终点的代价。f g h优先队列按照f排序这样搜索就会更偏向“看起来离目标近的方向”而不是朝所有方向均匀扩散。这是第三章作业最核心的一个节也是老师最喜欢追问细节的地方。启发函数怎么选直接影响搜索效率。我用的最常见方案是曼哈顿距离def heuristic(row, col, end_row, end_col): return abs(row - end_row) abs(col - end_col)如果地图允许斜向移动曼哈顿距离会高估实际代价因为走斜线比“先横再竖”更短所以这时候更适合用欧几里得距离def heuristic_euclidean(row, col, end_row, end_col): return ((row - end_row) ** 2 (col - end_col) ** 2) ** 0.5A*还有一个重要的细节为了确保算法一定能找到最短路径启发函数必须“可采纳”也就是h不能高估实际剩余代价。如果高估了算法会变得更快但会丢掉最优性。这个性质在作业答辩时经常被考你一定要能用自己的话说清楚。A*的代码结构和Dijkstra几乎一样区别只在计算fdef astar(grid, start, end, heuristic): start.g 0 start.f start.g heuristic(start.row, start.col, end.row, end.col) open_heap [(start.f, start.row, start.col)] node_dict {(start.row, start.col): start} visited set() while open_heap: current_f, r, c heapq.heappop(open_heap) current node_dict[(r, c)] if (r, c) in visited: continue if (r, c) (end.row, end.col): return reconstruct_path(current) visited.add((r, c)) for nr, nc in get_neighbors(grid, current): if (nr, nc) in visited: continue cost 1 new_g current.g cost new_h heuristic(nr, nc, end.row, end.col) new_f new_g new_h if (nr, nc) not in node_dict: child Node(nr, nc) child.g new_g child.f new_f child.parent current node_dict[(nr, nc)] child heapq.heappush(open_heap, (new_f, nr, nc)) elif new_g node_dict[(nr, nc)].g: node_dict[(nr, nc)].g new_g node_dict[(nr, nc)].f new_g new_h node_dict[(nr, nc)].parent current heapq.heappush(open_heap, (new_f, nr, nc)) return NoneA写起来不难难的是理解它和Dijkstra的区别到底在哪里。我自己的理解是Dijkstra把搜索队列按“已经付出的代价”排序而A把搜索队列按“已经付出的代价预估剩余代价”排序。后者因为多了一个目标方向信息所以可以少访问很多无关区域。3.4 三种算法在相同地图上的差异对比我做完三种算法之后用同样的地图、同样的起点终点跑了一遍统计了几个关键指标。这里贴出来给大家一个直观参考地图是30x30随机生成15%障碍物4邻域移动算法访问节点数路径长度运行耗时约是否保证最短BFS约570420.8ms无权图下是Dijkstra约620421.2ms总是A*曼哈顿距离约320420.6ms是可采纳启发这个表格大概能解释为什么实际工程里A最常用同样的最短路径A只需要访问大约一半的节点意味着计算量更小。但Dijkstra并没有被淘汰因为Dijkstra不需要启发函数在某些无法设计合理启发函数的场景下更稳妥。顺带说一句如果地图特别大比如几万个节点A配合曼哈顿距离依然会慢。工程上通常会做分级规划、跳点搜索、或者用双向A进一步压缩搜索空间。这些在第四章作业里大概率会碰到。4. 调试现场与常见问题速查4.1 为什么我的A*偶尔不是最优这是我在深蓝学院第三章作业中第一次撞出的一个非常隐蔽的问题我把h设成了曼哈顿距离但地图上允许斜向移动。斜向移动的实际代价是sqrt(2)而曼哈顿距离把斜向移动估算成2实际上高估了剩余代价导致A*可能错过真正最短的斜线路径。处理方式有两种。第一种是如果不使用斜向移动就只用四邻域曼哈顿距离完美匹配保证最优第二种是允许斜向移动但用欧氏距离作为启发函数不过欧氏距离不是完美的“整数格子距离”在一些特定地图上依然可能出现非最优所以更稳妥的做法是把斜向移动的代价直接设为1然后用切比雪夫距离或欧氏距离。这个问题的根源是你怎么定义移动代价而不是算法本身。4.2 open表性能为什么越来越慢我的第一次A*实现里open表用的是Python的list每次取最小值都用min(open_list)再把最小值删掉。小地图看不出问题但地图放大到100x100之后程序肉眼可见地卡顿。原因很简单min是O(n)操作每次扩展一个节点都要遍历整个open表整体复杂度变成O(n^2)。作业规模小的时候无所谓但你要养成用heapq或者priority_queue的习惯。C里用std::priority_queuePython里用heapq弹出的复杂度是O(log n)整体性能差距巨大。这算是我在工程上第一次体会到“数据结构选择”对程序性能的直接影响。之前课上讲堆、讲优先队列我都觉得是纸面知识直到被100x100的地图教育了一顿才彻底记住。4.3 斜着走必须小心“穿墙”栅格地图里允许斜向移动时一定要处理“墙角穿模”问题。比如当前节点在障碍物的左上角右方和下方是空地右下角也是空地如果你直接斜着走到右下角路径就会贴着一个障碍物角走视觉上看起来像穿墙了。解决方法是允许斜向时额外检查当前节点到目标邻居之间的两个正交方向是否都可行。如果其中一个方向是障碍物就禁止斜向走过去。这个规则在游戏寻路中也很常见叫“不允许沿墙滑行”。代码写起来很简单在get_neighbors里加几个判断即可if dr ! 0 and dc ! 0: # 斜向移动检查两个正交方向 if grid[r dr][c] 1 or grid[r][c dc] 1: continue不加这个检查算法结果在数据上大概率也是合法的但在可视化图上看起来非常奇怪老师一眼就能看出你没处理细节。这也是作业能不能从“跑通”到“优秀”的一个分水岭。4.4 路线图“卡死”在死胡同怎么排查写A*和Dijkstra初期我经常遇到一个问题算法在某个区域搜索了很久输出路径却绕了远路甚至根本找不到终点。排查思路有三步。第一步检查地图坐标是否正确先在代码里输出起点和终点的坐标手动在地图上确认没有放反。第二步在算法里加一个简单的打印轮数每访问1000个节点打印一次当前正在处理的节点坐标看搜索区域是不是在被障碍物挡住的地方反复绕。如果绕来绕去出不去很可能是邻居生成逻辑漏掉了某个方向或者地图边界判断写错了。第三步做一个极小地图测试比如3x3地图手算最短路径看算法答案对不对。我强烈建议你准备一个“测试套件”包含几个不同特性的小地图一个空地地图验证往返路径长度是否对称、一个单排障碍地图验证绕障能力、一个全障碍地图包围终点验证无解处理。每一次改动代码之后都先跑一遍测试套件再跑大图。看似多花两分钟实际上能省下好几小时的瞎调试时间。下面的表是我自己整理的常见问题速查分享出来基本覆盖了我在做第三章作业期间遇到的所有主要麻烦现象可能原因解决办法路径不是最短使用BFS处理带权地图换成Dijkstra或A*A*结果比Dijkstra长启发函数高估了剩余代价改成可采纳的曼哈顿/欧氏距离地图一大就卡死open表用了list取最小值改用优先队列路径穿墙/贴墙斜向移动没有检查正交邻居在get_neighbors中增加斜向校验找不到终点边界检查与障碍判断顺序写反先判断bound再判断障碍搜索范围异常大启发函数可能为0或设置错误检查h是否被重置或覆盖路径反向回溯父节点时顺序未反转reconstruct_path需要reverse另外还有一个小建议在实现所有搜索算法之前先写一个统一的路径重建函数def reconstruct_path(node): path [] while node is not None: path.append((node.row, node.col)) node node.parent return path[::-1] # 反转成从起点到终点这个函数看起来简单但很容易写错。我第一次写的时候忘记反转结果可视化出来的路径从终点指向起点我还以为是算法问题排错了半小时才发现是回溯方向反了。4.5 调参技巧先把g值权重固定再谈启发函数很多人第一次接触A*时会想调整f g h里的权重比如改成f g 2*h让算法更激进地奔着终点去。这个做法在工程上确实可以加速搜索但代价是可能得到次优路径。做作业的时候我建议先老老实实用f g h确保算法最优性没有问题再尝试调权重并且对比调权重前后的路径质量和访问节点数。自己动手做一次这个对比远比死记“权重大会导致非最优”要深刻得多。我调权重时发现把h的权重从1调到1.5访问节点数下降了约四成但路径长度偶尔会多出几个格子。对于实际导航来说这可能就够用了但对于作业来说最好在报告里清楚地说明自己做了这个实验并分析利弊。这会让你的作业明显高出别人一截。5. 从作业到工程的三个额外体会第三章作业做到后面你会发现它已经不只是“写三个算法”这么简单。它其实在教你工程上常用的套路统一接口、策略切换、可视化调试。这三个能力一个比一个值钱。我第一次做的时候三个算法分散在三个文件里每个文件都要重新读取地图输出格式还不统一最后写实验报告的时候差点被逼疯。后来我重构了一版把搜索部分封装成一个PathSolver类传入一个整数参数就能切换BFS/Dijkstra/A*主流程只负责读地图、调solver、画图。这个重构大约花了一个小时但之后写报告、做对比实验、甚至改动地图数据都变得非常顺畅。另一个体会是可视化对理解算法的作用真的被低估了。在没画搜索过程之前我以为Dijkstra和A的差别就是“有启发和没启发”。直到我亲眼看到Dijkstra像一个圆一样均匀扩散而A像一支箭一样直奔终点我才真正理解了“搜索效率”这个抽象概念到底意味着什么。我建议你也做一张“搜索过程扩散图”把访问顺序按时间先后用颜色深浅表示出来。这张图放进作业报告里视觉冲击力很强也能体现你对搜索算法的理解深度。导师看到这种图通常都会多问几句细节而你在做图的过程中其实已经把细节都弄清楚了完全不怕问。最后再分享一个写实验报告的小技巧除了贴路径图、统计表我还会放两个“负向实验”。比如跑一张Dijkstra在地图上有很多高代价区域的地图然后展示BFS在同一张地图上绕了远路又比如跑一张只有一条窄通道的地图看看A*在海量开阔区域里的搜索范围。这种对比实验不需要多两三个足矣但能非常有说服力地展示你已经理解了每个算法的适用场景和局限。很多人做作业只展示“成功案例”那其实是不够的。学会展示“失败案例”并解释原因才是区分作业质量的关键。
