1. 从一道经典题说起为什么广搜还需要优化Knight Moves 这道题但凡刷过一段时间的算法题大概率都见过。题干本身非常朴素在一个 8×8 的国际象棋棋盘上给定起点和终点问马从起点跳到终点最少需要几步。马走“日”字也就是每步在横纵两个方向上分别偏移 1 和 2 格。求最少步数第一反应就是广度优先搜索一层一层往外扩展第一次碰到终点时的层数就是答案。这个思路没错而且对于 8×8 这种小棋盘朴素 BFS 跑起来毫无压力。但问题在于这道题被放在“广搜的优化技巧”这一章里它的定位就不是让你写一个能过的 BFS而是让你理解当搜索空间变大、状态变多、单层扩展代价变高时普通 BFS 会卡在哪里以及有哪些手段能把它救回来。这才是这道题真正的价值所在。我见过太多人做这道题写完一个标准队列 BFS提交过了然后就翻篇了。等到后面遇到棋盘变成 100×100、状态带上额外维度、或者需要多次查询的时候同样的代码直接超时回头再补优化等于重新学一遍。所以这篇内容我打算把这道题当成一个引子把广搜优化里最核心的几类技巧掰开揉碎讲清楚双向广搜、状态压缩与去重、启发式剪枝、以及边界与常数的处理。这些技巧不是孤立的它们背后有一套共同的逻辑——减少无效扩展、降低单次扩展成本、让搜索更快撞到目标。适合谁来读如果你已经会写最基础的 BFS知道队列怎么用、visited 数组怎么标记但一遇到大数据就发怵那这篇正好补上从“能过”到“稳过”的那段路。如果你是完全的新手也没关系我会把每一步的动机讲清楚你跟着推一遍就能理解为什么这么设计。先说清楚这道题的基本盘。棋盘 8×8马有 8 个可能的移动方向用坐标偏移表示就是 (±1, ±2) 和 (±2, ±1) 这八组。起点终点都在棋盘内。最坏情况下从棋盘一个角到另一个角马需要 6 步。这个数字很关键它意味着搜索树的深度很浅但每一层的分支因子是 8朴素 BFS 的节点规模大概在 8 的若干次方量级虽然实际因为棋盘限制和去重会小很多但方向上是清楚的。# 马的八个移动方向 directions [ (1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1) ]这八组偏移是这道题的地基后面所有优化都建立在对这八组方向的合理利用上。别小看这个定义方向数组写错一个符号整个搜索就废了而且这种错误特别隐蔽因为程序不报错只是答案不对。我建议每次写方向数组的时候都按“先固定一个轴的偏移再枚举另一个轴的正负”这种规律来写减少手误。2. 朴素 BFS 的瓶颈到底在哪2.1 一层一层扩展的本质开销朴素 BFS 的流程很直白起点入队标记已访问每次取出队首枚举八个方向如果新位置在棋盘内且没访问过就入队并标记同时记录步数一旦取出的位置等于终点返回步数。用代码写出来大概是这样from collections import deque def bfs(start, end): if start end: return 0 visited [[False] * 8 for _ in range(8)] queue deque() queue.append((start[0], start[1], 0)) visited[start[0]][start[1]] True while queue: x, y, step queue.popleft() for dx, dy in directions: nx, ny x dx, y dy if 0 nx 8 and 0 ny 8 and not visited[nx][ny]: if (nx, ny) end: return step 1 visited[nx][ny] True queue.append((nx, ny, step 1)) return -1这段代码在 8×8 上跑没有任何问题。但它的开销结构值得拆开看。每个节点出队时要做八次方向枚举每次枚举包含边界判断、访问判断、可能的入队操作。也就是说总操作数约等于访问节点数乘以 8。在 8×8 上最多 64 个格子乘 8 也就 512 次操作微不足道。问题出在“访问节点数”这个量上。BFS 的特点是它会把目标层之前的所有节点全部扩展完才可能碰到目标。也就是说如果答案是 6 步那么第 0 到第 5 层的所有可达节点都会被访问。这个“所有”在棋盘小的时候无所谓棋盘一大就爆炸。假设棋盘是 N×N分支因子是 8那么第 k 层的理论节点数是 8 的 k 次方虽然实际受棋盘边界和去重限制会少很多但增长趋势是指数级的。2.2 什么时候朴素 BFS 会撑不住有几个信号一出现就说明朴素 BFS 该优化了。第一棋盘尺寸从 8 变成几十甚至上百节点总数从 64 变成几千几万单次查询还能忍但如果有多组查询就顶不住。第二状态不只是坐标还带了额外维度比如“已经收集了哪些钥匙”“还剩多少步数预算”“当前朝向是什么”状态空间直接翻倍甚至翻几十倍。第三单层扩展的代价变高比如每个节点要枚举的方向不是 8 个而是几十个或者每次扩展要做复杂计算。Knight Moves 这道题本身没到那个程度但它是理解这些瓶颈的最佳样本因为它的结构足够简单你可以把注意力全放在优化思路上而不用分心去处理复杂的业务逻辑。我个人的习惯是每学一个优化技巧都回到这道题上验证一遍看看在这个最小样本上它长什么样然后再迁移到复杂场景。提示判断要不要优化先估算状态空间大小和分支因子。状态数乘以分支因子如果超过百万量级就该考虑双向搜索或启发式了。2.3 优化的三个方向广搜优化说到底就三条路。第一条是减少搜索的层数双向广搜是典型代表从起点和终点同时扩展两边在中间相遇搜索深度直接砍半。第二条是减少每层的无效节点靠的是更好的去重、状态压缩、以及启发式剪枝把明显不可能通向最优解的节点提前扔掉。第三条是降低单次扩展的常数比如用更快的队列实现、用位运算代替数组、减少不必要的判断。这三条路可以叠加使用效果往往是一加一大于二。下面我按这个顺序把每一类技巧在 Knight Moves 上的具体形态讲透。3. 双向广搜把搜索深度砍一半3.1 双向广搜的核心思想单向 BFS 是从起点往外一圈一圈扩直到碰到终点。双向广搜的思路是既然从起点到终点和从终点到起点是对称的马走日这个移动是可逆的从 A 能跳到 B从 B 也能跳回 A那我为什么不从两头同时扩谁先碰到对方的已访问区域就说明找到了一条路径。这个思路的威力在于搜索的节点数随深度是指数增长的。如果单向需要扩展到第 d 层节点规模大约是 b 的 d 次方b 是分支因子。双向的话两边各扩展到第 d/2 层就能相遇节点规模大约是 2 乘以 b 的 d/2 次方。当 d 比较大的时候这个差距是数量级的。举个具体的数b 取 8d 取 6单向是 8 的 6 次方约 26 万双向是 2 乘以 8 的 3 次方约 1024差了 250 倍。当然实际因为有去重和边界限制差距没这么夸张但方向是对的。3.2 在 Knight Moves 上实现双向广搜实现双向广搜有几个关键点。第一要维护两个队列和两个访问标记数组分别记录从起点出发和从终点出发的访问情况同时记录到达每个格子的步数。第二每次选择扩展哪一边的时候通常选当前层节点数较少的那一边这样能让两边更均衡地推进相遇更快。第三当从一边扩展出一个新节点发现它已经被另一边访问过就说明找到了路径总步数是两边步数之和。from collections import deque def bidirectional_bfs(start, end): if start end: return 0 # 两个方向的访问步数数组-1 表示未访问 visited_a [[-1] * 8 for _ in range(8)] visited_b [[-1] * 8 for _ in range(8)] queue_a deque([start]) queue_b deque([end]) visited_a[start[0]][start[1]] 0 visited_b[end[0]][end[1]] 0 while queue_a and queue_b: # 优先扩展节点较少的一边 if len(queue_a) len(queue_b): if expand(queue_a, visited_a, visited_b): return get_answer(visited_a, visited_b) else: if expand(queue_b, visited_b, visited_a): return get_answer(visited_a, visited_b) return -1这里的expand函数负责从队列里取出一整层节点进行扩展get_answer负责在相遇时计算总步数。注意一个细节相遇的判断是在扩展过程中做的一旦新节点在对方数组里已有步数记录就立刻可以返回不需要等整层扩完。但为了代码清晰也可以整层扩完再检查代价是稍微多算一点。3.3 相遇判断与步数合并的坑双向广搜最容易出错的地方就是步数合并。假设从起点方向扩展到节点 X 用了 sa 步从终点方向扩展到同一个节点 X 用了 sb 步那么总步数是 sa 加 sb。但这里有个陷阱如果是在扩展过程中发现 X 已经被对方访问那么当前这一步的步数要算清楚。比如从 A 方向扩展当前节点步数是 s新节点步数是 s1如果新节点在 B 方向的步数是 t那么总步数是 s1t。还有一个更隐蔽的坑相遇不一定发生在同一个节点上也可能发生在一条边上。也就是说A 方向扩展到了节点 UB 方向扩展到了节点 V而 U 和 V 之间有一条边相连那么路径是 A 到 U 到 V 到 B总步数是步数(U) 1 步数(V)。如果只检查节点重合会漏掉这种情况导致答案偏大。稳妥的做法是在扩展每个新节点时既检查它本身是否被对方访问过也检查它的邻居是否被对方访问过。注意双向广搜的终止条件比单向复杂建议先用小棋盘暴力对拍确认步数合并逻辑无误后再上大数据。3.4 双向广搜的适用边界双向广搜不是万能的。它要求从起点到终点的路径是可逆的也就是移动关系对称。马走日满足这个条件所以能用。但如果移动是单向的比如某些有向图上的搜索就不能简单套用。另外双向广搜需要额外的空间存两套访问数组空间开销翻倍在状态空间本来就很大的时候要权衡。在 Knight Moves 这个场景下双向广搜的收益是明显的尤其是当棋盘从 8×8 扩大到更大尺寸时深度增加双向的优势更突出。我实测过在 8×8 上双向和单向差距不大因为深度太浅但在 50×50 上双向的节点访问量大概只有单向的十分之一到五分之一。4. 状态去重与压缩别在同一个坑里摔两次4.1 去重的本质是避免重复扩展BFS 能保证最短路径前提是每个状态只被扩展一次。如果同一个状态被多次入队不仅浪费时间和空间还可能因为步数记录混乱导致错误答案。所以 visited 数组的作用不只是“标记来过”更是“保证每个状态只处理一次”。在 Knight Moves 里状态就是棋盘上的坐标 (x, y)用二维布尔数组就能搞定。但很多人写的时候会犯一个错在入队时标记 visited还是在出队时标记正确做法是入队时标记。如果出队时才标记同一个节点可能在入队前被多个前驱节点发现导致重复入队队列膨胀。这个细节在棋盘小的时候看不出来棋盘一大就是灾难。# 正确入队时立即标记 visited[nx][ny] True queue.append((nx, ny, step 1)) # 错误出队时才标记会导致重复入队 queue.append((nx, ny, step 1)) # ... 出队时再 visited[x][y] True4.2 状态压缩的常见手段当状态带额外维度时二维数组就不够用了。比如状态是 (x, y, keys)keys 表示已收集的钥匙集合那么可以用三维数组 visited[x][y][keys]。如果 keys 的种类很多三维数组会很大这时候可以用哈希表或者把状态编码成一个整数。编码的思路是把每个维度的取值范围确定下来然后做进制转换。比如 x 范围 0 到 7y 范围 0 到 7keys 范围 0 到 15那么状态可以编码成 x 乘以 8 乘以 16 加 y 乘以 16 加 keys得到一个唯一的整数。用这个整数作为数组下标或者哈希键就能压缩存储。# 状态编码示例 def encode(x, y, keys): return (x * 8 y) * 16 keys # 解码 def decode(code): keys code % 16 code // 16 y code % 8 x code // 8 return x, y, keys在 Knight Moves 里状态简单用不上编码但这个技巧在后面复杂题目里是标配。我建议在这道题上先把二维 visited 写熟理解“入队即标记”的原则再往复杂状态迁移。4.3 位运算加速状态标记如果状态空间不大可以用一个整数的二进制位来表示访问情况。比如 8×8 棋盘有 64 个格子可以用一个 64 位的整数第 i 位为 1 表示第 i 个格子访问过。判断和设置都用位运算速度比二维数组快。visited 0 # 64 位整数 # 判断第 idx 个格子是否访问 if not (visited idx) 1: visited | (1 idx)这种写法在竞赛里很常见因为位运算的常数极小。但可读性会下降日常开发里如果性能不是瓶颈还是用数组更清晰。我的建议是先保证逻辑正确再考虑用位运算压常数。提示位运算适合状态数不超过 64 或 128 的场景。超过这个范围整数放不下就得换回数组或哈希。5. 启发式剪枝与搜索顺序优化5.1 启发式剪枝的基本逻辑剪枝的核心是如果某个节点明显不可能通向比当前已知最优解更好的结果就提前扔掉它。在 BFS 里因为是一层层扩展第一次碰到目标就是最优解所以剪枝的空间比 DFS 小。但也不是完全没有比如可以用一个下界函数估算“从当前节点到目标至少还要多少步”如果当前步数加上这个下界已经超过了某个已知上界就可以剪掉。在 Knight Moves 里一个简单的下界是“切比雪夫距离除以 2 再向上取整”因为马每步最多让横纵坐标各变化 2所以从 (x1, y1) 到 (x2, y2) 至少需要 max(|x1-x2|, |y1-y2|) 除以 2 向上取整步。这个下界可以用来做 A* 搜索的估价函数。5.2 A* 搜索在 Knight Moves 上的应用A* 搜索本质是带优先级的 BFS每次扩展估价函数 f g h 最小的节点其中 g 是已走步数h 是到目标的估计步数。如果 h 满足“不高估”的性质即可采纳性A* 能保证找到最优解而且通常比 BFS 扩展更少节点。import heapq def heuristic(x, y, end): dx abs(x - end[0]) dy abs(y - end[1]) return (max(dx, dy) 1) // 2 def a_star(start, end): if start end: return 0 visited [[False] * 8 for _ in range(8)] heap [(heuristic(start[0], start[1], end), 0, start[0], start[1])] visited[start[0]][start[1]] True while heap: f, g, x, y heapq.heappop(heap) if (x, y) end: return g for dx, dy in directions: nx, ny x dx, y dy if 0 nx 8 and 0 ny 8 and not visited[nx][ny]: visited[nx][ny] True ng g 1 heapq.heappush(heap, (ng heuristic(nx, ny, end), ng, nx, ny)) return -1A* 在 Knight Moves 上的效果取决于启发函数的质量。上面这个下界比较松剪枝效果一般但比纯 BFS 还是好一些。如果能把下界算得更紧效果会更好。不过要注意启发函数必须保证不高估否则可能错过最优解。5.3 搜索顺序对性能的影响在 BFS 里同一层节点的扩展顺序不影响正确性但影响“多快碰到目标”。如果目标在某个方向优先扩展朝那个方向的节点可能更早碰到。在 Knight Moves 里可以根据目标相对于当前节点的方位调整八个方向的枚举顺序把更可能接近目标的方向排在前面。这个优化在单向 BFS 里效果有限因为 BFS 是一层层来的同层顺序影响不大。但在 A* 或者双向 BFS 里顺序的影响就明显了。我的经验是如果目标在右上方就优先枚举 (1,2) 和 (2,1) 这类朝右上的方向。这个技巧不需要额外空间只是调整方向数组的顺序成本极低。注意搜索顺序优化不改变算法的最坏复杂度只是让平均情况更快。不要指望它解决根本性的性能问题。6. 边界处理与常数优化魔鬼在细节里6.1 边界判断的写法边界判断看起来简单但写法不同性能差很多。常见写法是0 nx 8 and 0 ny 8这个写法清晰但每次要做四次比较。另一种写法是预先在棋盘外围加一圈“哨兵”把棋盘扩成 10×10外围标记为已访问这样扩展时不用判断边界直接检查 visited 就行。# 哨兵写法棋盘扩成 10x10外围一圈标记为已访问 visited [[True] * 10 for _ in range(10)] for i in range(1, 9): for j in range(1, 9): visited[i][j] False # 坐标整体偏移 1哨兵写法减少了边界判断但增加了初始化的开销而且坐标要整体偏移容易出错。在 8×8 这种小棋盘上两种写法差距不大。但在大棋盘上哨兵写法能省下可观的判断开销。我个人的习惯是如果棋盘尺寸固定且不大用直接判断如果尺寸大或者要多次搜索用哨兵。6.2 队列的选择Python 里collections.deque是 BFS 的标准选择它的 popleft 是 O(1) 的。如果用 list 加 pop(0)每次弹出都是 O(n)队列一大就慢得离谱。这个坑我见过太多人踩尤其是从其他语言转过来的习惯用数组模拟队列。# 正确用 deque from collections import deque queue deque() queue.append(x) queue.popleft() # 错误用 list 的 pop(0)O(n) 操作 queue [] queue.append(x) queue.pop(0) # 慢如果自己用数组模拟队列可以用两个指针 head 和 tail避免真的移动元素。这种写法在 C 里很常见Python 里用 deque 就够了。6.3 减少函数调用和属性访问Python 里函数调用和属性访问的开销不小。在 BFS 的内层循环里如果每次都调用len(queue)或者访问visited[nx][ny]累积起来很可观。可以把常用的东西提前绑定到局部变量比如把visited绑成局部变量把方向数组绑成局部变量减少全局查找。def bfs(start, end): visited [[False] * 8 for _ in range(8)] queue deque([start]) visited[start[0]][start[1]] True dirs directions # 局部绑定 step 0 while queue: for _ in range(len(queue)): x, y queue.popleft() if (x, y) end: return step for dx, dy in dirs: nx, ny x dx, y dy if 0 nx 8 and 0 ny 8 and not visited[nx][ny]: visited[nx][ny] True queue.append((nx, ny)) step 1 return -1这种按层处理的写法把步数从节点里剥离出来节点只存坐标减少了元组的元素个数也减少了内存和拆包开销。在小数据上无所谓在大数据上是实打实的提升。6.4 常见问题速查表问题现象可能原因排查方向答案偏大相遇判断漏了边的情况检查双向 BFS 是否只判断节点重合答案偏小步数合并多加或少加打印两边步数手动验证一条路径超时队列用了 list 的 pop(0)换成 deque超时出队时才标记 visited改成入队时标记死循环方向数组写错导致原地跳检查八个方向是否有 (0,0)内存超限visited 数组开太大考虑状态压缩或哈希结果不稳定启发函数高估检查 h 是否满足可采纳性这张表是我自己踩坑总结的遇到问题先对照一遍能省不少调试时间。7. 从 Knight Moves 到通用广搜优化的迁移7.1 什么场景该用哪种优化把这道题的经验迁移到其他场景需要判断当前瓶颈在哪。如果状态空间大但深度浅优先考虑去重和常数优化如果深度大优先考虑双向广搜如果单层分支多优先考虑启发式剪枝。这三者不是互斥的可以组合。我一般按这个顺序排查先看 visited 有没有正确去重再看队列实现有没有问题然后看能不能双向最后看能不能加启发式。这个顺序是从成本低到成本高先做便宜的优化往往就能解决问题。7.2 双向广搜的通用模板双向广搜的模板可以抽象成两个队列、两个访问表、一个扩展函数、一个相遇检查。扩展函数负责从一边取一层节点生成新节点检查是否被对方访问返回是否相遇。这个模板稍作修改就能用到其他可逆搜索问题上。def bidirectional_search(start, end, expand_func, check_func): visited_a {start: 0} visited_b {end: 0} queue_a deque([start]) queue_b deque([end]) while queue_a and queue_b: if len(queue_a) len(queue_b): if expand_func(queue_a, visited_a, visited_b): return check_func(visited_a, visited_b) else: if expand_func(queue_b, visited_b, visited_a): return check_func(visited_a, visited_b) return -1这个模板的关键是把“如何生成邻居”和“如何判断相遇”抽象成函数这样换问题的时候只需要改这两个函数框架不用动。7.3 启发式函数的设计原则启发式函数 h 必须满足两个条件一是可采纳性即 h 不高估真实代价二是一致性即 h(u) 不超过从 u 到 v 的真实代价加上 h(v)。满足一致性的话A* 不需要重复扩展节点实现更简单。设计 h 的时候通常用“放松约束”的思路比如忽略障碍、允许更自由的移动得到的下界就是可采纳的。在 Knight Moves 里忽略棋盘边界和马的走法限制只考虑坐标差得到的就是那个切比雪夫距离下界。这个下界比较松但胜在计算快。如果愿意花更多计算时间可以预计算所有格子对之间的真实距离用查表代替估算但那就不是启发式了而是精确值。提示启发式函数的质量直接决定 A* 的效率。宁可花时间设计一个好的 h也不要在差的 h 上堆优化。8. 我在这道题上踩过的坑和实测心得第一次做这道题的时候我写了个标准 BFS过了没多想。后来在另一道棋盘更大的题上超时回头才发现问题。那次超时的原因是出队时才标记 visited导致大量重复入队队列一度膨胀到几十万。改成入队时标记直接降到几千。这个教训让我养成了“入队即标记”的肌肉记忆。双向广搜的坑我踩得更深。第一次实现的时候只检查了新节点是否被对方访问漏了边的情况结果在某些起点终点组合上答案偏大。后来加上了邻居检查才对上。这个 bug 特别隐蔽因为大部分情况下节点重合就够了只有少数情况会漏。我的建议是双向广搜写完后用暴力 BFS 在小棋盘上全量对拍确认所有起点终点组合都一致。常数优化方面我实测过 deque 和 list 的差距。在 8×8 上两者都是毫秒级看不出区别。但在 100×100 上list 的 pop(0) 让程序慢了将近十倍。这个差距在竞赛里是致命的。所以不管数据大小养成用 deque 的习惯没坏处。还有一个心得是关于方向数组的。我习惯把它写成元组的元组而不是列表的列表因为元组是不可变的访问更快而且不会被意外修改。这个习惯是从一次调试事故来的当时有个地方不小心修改了方向数组导致后续所有搜索都错查了半天才发现。最后说一个关于启发式剪枝的体会。A* 在 Knight Moves 上其实优势不明显因为棋盘太小BFS 本来就快。但在大棋盘上A* 的节点扩展量能比 BFS 少一个数量级。关键是启发函数要设计好太松了没效果太紧了可能破坏可采纳性。我一般先用一个简单的下界跑一遍看节点数如果还是太多再想办法收紧。这道题的价值不在于它本身有多难而在于它是一个干净的实验台。你可以在上面试各种优化观察每种优化带来的变化而不用被复杂的业务逻辑干扰。把这道题吃透后面遇到再复杂的广搜问题你都有了一套可以复用的工具箱。