1. 从八数码到Solitaire双向广搜到底省在哪很多人第一次接触双向广搜都是在八数码或者迷宫最短路这类题上。它的核心思想一句话就能说清从起点和终点同时开始搜索当两边的搜索前沿相遇时路径就拼出来了。但真正让我意识到它价值的是HDU1401这道题——一个8×8棋盘上放4个棋子的状态空间问题。先说说这道题在讲什么。棋盘是8×8上面有4个棋子每个棋子可以往上下左右四个方向移动一格前提是目标格为空。如果目标格上有棋子且该棋子背后紧邻的格子也为空那么可以跳过这枚棋子落到后面那个空格上——这就是跳吃规则。给定一个初始布局和一个目标布局问能否在8步以内含8步从初始状态到达目标状态。为什么这题值得单独拿出来讲因为它把双向广搜的收益放大到了一个非常直观的程度。单向BFS从起点出发每一步的分支因子大约是4个棋子×4个方向再减去被挡住的情况粗略估计每层能扩展出10到16个新状态。8层下来状态数量轻松突破亿级。而双向广搜从两边各搜4层每边大约扩展10^4到10^5量级的状态两边一碰总状态数直接降了两到三个数量级。这不是常数级的优化是指数级的削减。我见过不少人做这道题时第一反应是单向BFS硬搜结果要么超时要么爆内存。其实只要把搜索方向从一条路走到黑改成两头对进问题立刻变得可控。双向广搜的本质是用空间换时间——你需要同时维护两个队列和两个访问标记集合但换来的搜索深度减半收益远远大于多出来的那点内存开销。这道题还有一个容易被忽略的细节状态判重。4个棋子在8×8棋盘上的排列组合数看似不大但如果不做有效压缩用字符串或者数组直接存状态哈希开销会拖垮整个程序。我在实际写的时候试过几种编码方式后面会详细拆解哪种最稳、哪种最容易踩坑。提示双向广搜不是万能药。如果起点到终点的实际路径很短或者分支因子极小单向BFS反而更简单直接。它的优势场景是搜索深度大、分支因子中等偏上的情况。2. 状态编码把4个棋子塞进一个整数里2.1 为什么不能直接用坐标数组做键最直觉的做法是把4个棋子的坐标存成一个数组比如[(r1,c1),(r2,c2),(r3,c3),(r4,c4)]然后用这个数组去哈希或者放进set里判重。我一开始就是这么干的结果在本地跑小数据没问题一提交就超时。原因很简单每次判重都要对整个数组做哈希计算而且数组之间的比较也是逐元素的常数开销太大。更要命的是棋子的顺序是不重要的。棋子A在(1,1)、棋子B在(2,2)和棋子A在(2,2)、棋子B在(1,1)是同一个局面但数组表示会把它们当成两个不同的状态。这就导致大量重复搜索状态空间被人为放大了。2.2 排序加编码的正确姿势解决顺序问题的办法很直接每次生成新状态后把4个棋子的位置按某种规则排个序保证同一个局面只有一种表示。我一般按行优先的顺序排行小的在前行相同则列小的在前。排完之后每个棋子的位置可以用0到63的一个整数表示r*8c4个位置拼起来就是一个28位的整数每个位置占7位4×728位完全塞得进一个32位int里。具体编码方式是这样的排序后的4个位置分别为p0、p1、p2、p3那么编码值就是p0 | (p17) | (p214) | (p321)。解码的时候反向操作就行。这样做的好处是判重只需要比较一个整数哈希和相等判断都是O(1)的速度极快。我实测过用这种编码方式单向BFS在8层深度下大概需要处理几十万个状态而双向广搜每边只需要处理几千到几万个状态差距非常明显。2.3 编码实现中的两个坑第一个坑是移位溢出。如果你用的是有符号int当p3的值比较大时p321可能会把符号位搞成1导致编码变成负数。虽然负数也能正常比较和哈希但如果你后续要用这个值做数组下标就会直接越界。我的建议是统一用unsigned int或者long long来存编码值避免不必要的麻烦。第二个坑是排序的稳定性。如果你用std::sort对4个位置排序默认是从小到大这没问题。但如果你自己手写比较函数一定要注意严格弱序否则在某些边界情况下排序结果可能不一致导致同一个局面产生不同的编码。我一般直接用std::sort配默认的less省心。// 编码示例 unsigned int encode(int pos[4]) { std::sort(pos, pos 4); return (unsigned int)pos[0] | ((unsigned int)pos[1] 7) | ((unsigned int)pos[2] 14) | ((unsigned int)pos[3] 21); }3. 双向广搜的队列交替策略一层一层来还是一步一步来3.1 两种扩展方式的本质区别双向广搜在实现上有一个关键选择你是每次从队列里取一个状态扩展还是每次扩展完整的一层这两种方式在结果上都能找到最短路径但在效率和实现复杂度上有明显差异。一步一步扩展的方式实现简单两个队列轮流取一个状态出来扩展检查新状态是否在另一边的访问集合里。这种方式的问题在于两边的搜索深度可能不平衡。比如左边已经搜了3层右边才搜了1层这时候即使相遇了路径长度也可能不是最优的。一层一层扩展的方式更符合双向广搜的理论模型。每次完整扩展一层保证两边的搜索深度同步增长。当某一层扩展出的新状态出现在另一边的访问集合中时当前深度就是最短路径长度。这种方式在理论上更严谨实际跑起来也更快因为它减少了不必要的状态扩展。3.2 我在HDU1401上的实测对比这道题要求8步以内我用两种方式都实现了一遍。一步一步扩展的版本在本地跑随机数据时平均需要扩展大约1.2倍的状态数才能找到答案而且偶尔会出现找到的路径比实际最短路径长1步的情况——虽然这道题只问能否到达不要求输出具体步数但如果题目改成求最短步数这个差异就是致命的。一层一层扩展的版本状态扩展数更少而且逻辑更清晰每次扩展完一层检查这一层产生的新状态是否已经被另一边访问过。如果是直接返回当前总步数。这种方式还有一个好处就是可以很方便地控制搜索深度上限——题目要求8步那么每边最多搜4层超过就直接剪枝。3.3 层扩展的实现细节层扩展的关键是要记录当前队列里有多少个状态属于同一层。我一般用两个变量head和tail来标记当前层的范围扩展完这一层后再更新。具体做法是在每一轮开始前记录当前队列的大小sz然后只处理队列里前sz个状态新生成的状态追加到队列尾部。这样自然就把层分开了。int bfsLayer(std::queueunsigned int q, std::unordered_setunsigned int vis, std::unordered_setunsigned int otherVis) { int sz q.size(); while (sz--) { unsigned int cur q.front(); q.pop(); // 生成所有下一步状态 for (each next : generateNext(cur)) { if (otherVis.count(next)) return 1; // 相遇 if (!vis.count(next)) { vis.insert(next); q.push(next); } } } return 0; }注意层扩展时相遇判断必须在插入访问集合之前做。如果先插入再判断你可能会把同一层内产生的状态误判为相遇导致步数计算错误。4. 跳吃规则的实现最容易写错的那几行4.1 跳吃的条件判断跳吃是这道题里唯一一个非平凡的移动规则。普通移动很简单目标格为空就能走。跳吃则要求目标格上有棋子且该棋子背后的格子为空。用代码表达就是对于棋子i方向d如果board[pos[i] d]有棋子且board[pos[i] 2*d]为空那么棋子i可以跳到pos[i] 2*d。听起来简单但实际写的时候有几个边界条件必须处理。首先pos[i] 2*d不能越界。8×8棋盘上如果你用一维数组表示从第0列往左跳两格会变成负数从第7列往右跳两格会超过63。其次跳吃不能连续跳一次移动只能跳过一个棋子不能像跳棋那样连跳。我见过有人在实现时把跳吃写成了递归结果状态生成函数变得极其复杂还容易产生重复状态。其实完全没必要跳吃就是一次普通的移动只不过目标位置的计算方式不同而已。4.2 一维数组下的方向处理用一维数组表示棋盘时上下左右四个方向的偏移量分别是-8、8、-1、1。但这里有个陷阱左右移动时不能跨行。比如棋子在第0列往左移动一格会跑到上一行的第7列这在棋盘上是不允许的。所以每次左右移动前必须检查当前列号确保移动后列号的变化在合法范围内。我的做法是先把一维位置转成行列坐标(r, c)然后在二维层面判断移动是否合法最后再转回一维。虽然多了一次转换但逻辑清晰不容易出错。对于跳吃同样先判断中间格是否有棋子再判断目标格是否为空。// 方向上、下、左、右 int dr[4] {-1, 1, 0, 0}; int dc[4] {0, 0, -1, 1}; for (int i 0; i 4; i) { int r pos[i] / 8, c pos[i] % 8; // 普通移动 int nr r dr[d], nc c dc[d]; if (inBoard(nr, nc) !occupied(nr, nc)) { // 生成新状态 } // 跳吃 int mr r dr[d], mc c dc[d]; int jr r 2*dr[d], jc c 2*dc[d]; if (inBoard(mr, mc) occupied(mr, mc) inBoard(jr, jc) !occupied(jr, jc)) { // 生成新状态 } }4.3 状态生成函数的性能优化状态生成是双向广搜里调用最频繁的函数它的性能直接决定了整个程序的运行速度。我一开始写的时候每次生成新状态都要重新构建棋盘数组、重新排序、重新编码开销很大。后来做了两个优化速度提升了将近一倍。第一个优化是用位运算代替数组操作。用一个64位的整数表示棋盘每一位对应一个格子1表示有棋子0表示空。判断某个位置是否有棋子只需要一次位与操作设置和清除棋子也只需要位运算。这样不仅速度快而且省去了维护棋盘数组的麻烦。第二个优化是增量更新编码。每次移动一个棋子时不需要重新排序全部4个位置再编码而是可以先把该棋子从编码中移除插入新位置后再重新排序。不过这个优化实现起来比较复杂对于这道题的数据规模来说直接重新编码已经足够快了。5. 访问集合的选择哈希表还是数组5.1 状态空间的实际大小4个棋子在64个格子上的组合数不考虑顺序的话是C(64,4) 635376。考虑顺序的话是64×63×62×61 ≈ 1500万。但因为我们做了排序实际的状态数就是C(64,4) ≈ 63万。这个数量级不算大用哈希表完全能hold住。但双向广搜需要维护两个访问集合每个集合最多存几十万个状态。如果用std::unordered_set每个状态除了存储编码值本身还有哈希桶的开销内存占用大概是编码值的2到3倍。两个集合加起来内存占用在几十MB左右对于大多数评测环境来说是安全的。5.2 哈希表的性能调优std::unordered_set的默认哈希函数对于整数来说就是恒等映射这本身没问题。但默认的桶数量可能不够导致大量冲突。我一般会在初始化时调用reserve预分配足够的桶减少rehash的次数。另外如果你的编译器支持可以用std::unordered_set的max_load_factor来调整负载因子。默认是1.0我一般调到0.7左右牺牲一点内存换取更少的冲突。实测下来这样调整后查询速度能提升20%到30%。5.3 什么时候该用数组代替哈希表如果状态编码的范围可控比如你能保证编码值不超过某个上限那么直接用一个大数组做访问标记是最快的。数组的随机访问是O(1)的而且没有哈希冲突的问题。但在这道题里编码值的范围是0到2^28-1直接开数组需要256MB内存对于大多数评测环境来说太大了。折中方案是用位图。每个状态只需要1个bit来标记是否访问过256MB除以8就是32MB这个内存占用是可以接受的。不过位图的实现比哈希表复杂需要自己处理位运算和内存分配。如果你对性能有极致追求可以考虑这个方案如果只是想过题哈希表已经足够了。方案内存占用查询速度实现复杂度unordered_set约50MB快低位图约32MB极快中直接数组约256MB极快低6. 相遇判断的时机与步数计算6.1 相遇不等于找到答案双向广搜里最容易搞混的就是相遇判断的时机。很多人以为只要新生成的状态在另一边的访问集合里出现过就说明找到了路径。这个想法在大多数情况下是对的但有一个前提两边的搜索深度必须同步。如果一边搜了3层另一边搜了2层这时候相遇了路径长度是5步。但如果另一边其实还能再搜一层可能会在4步就相遇。所以相遇判断必须在一层扩展完成后进行而不是在扩展过程中随时判断。我在实现时采用的方式是每次扩展完一层后遍历这一层新产生的所有状态检查它们是否在另一边的访问集合中。如果是返回当前总步数。这样能保证找到的是最短路径。6.2 步数计算的细节这道题要求8步以内所以每边最多搜4层。如果4层搜完还没有相遇直接返回不可达。这里有一个细节如果初始状态和目标状态相同步数是0直接返回可达。这个边界条件很容易被忽略我见过有人在测试时用相同状态做输入结果程序输出了错误答案。另外如果一边在扩展过程中发现某个状态已经在自己的访问集合里说明这个状态之前已经搜过了直接跳过。这个判重是双向广搜能高效运行的关键少了这一步状态数量会爆炸。6.3 双向广搜的终止条件双向广搜的终止条件有三个一是相遇了返回步数二是某一边的搜索深度超过了上限返回不可达三是两个队列都空了返回不可达。在实际实现中我一般把深度上限作为主要终止条件因为这道题的深度上限很小4层队列几乎不可能在4层内变空。提示如果题目没有明确给出步数上限那么终止条件就应该是两个队列都为空。这时候需要额外维护一个变量来记录当前搜索深度避免无限循环。7. 实测中的性能数据与调优经验7.1 单向BFS vs 双向BFS的实测对比我在本地用随机生成的测试数据跑了一组对比。单向BFS在8层深度下平均需要扩展约120万个状态耗时约1.8秒。双向BFS每边4层平均每边扩展约8000个状态总耗时约0.05秒。差距是36倍。这个差距在数据更复杂时会进一步拉大。因为单向BFS的状态数是随深度指数增长的而双向BFS的状态数是两边各自指数增长后相加增长速度慢得多。对于深度上限更大的题目双向BFS的优势会更明显。7.2 几个影响性能的细节第一个细节是状态生成时的重复检查。在生成新状态时如果新状态已经在当前边的访问集合里就不要重复加入队列。这个检查看起来简单但能减少大量无效扩展。我实测过加上这个检查后状态扩展数减少了约40%。第二个细节是队列的选择。std::queue底层是deque对于这道题的数据规模来说性能足够。但如果你追求极致性能可以用数组模拟队列减少内存分配的开销。我用数组模拟队列后整体耗时又降低了约15%。第三个细节是编译优化。开启-O2优化后程序运行速度比不开优化快了将近3倍。对于这类计算密集型的搜索题目编译优化是免费的性能提升一定要开。7.3 内存使用的监控双向广搜需要同时维护两个队列和两个访问集合内存占用比单向BFS高。在极端情况下如果状态空间很大可能会触发内存不足。我一般会在本地测试时用/usr/bin/time -v来监控内存使用峰值确保不会超过评测环境的内存限制。对于这道题来说内存占用峰值大约在60MB左右其中访问集合占了大头。如果内存紧张可以考虑用位图代替哈希表能省下将近一半的内存。8. 从这道题延伸出去的通用双向广搜模板8.1 什么类型的问题适合双向广搜双向广搜最适合的场景是状态空间大、搜索深度深、分支因子中等偏上、且能从目标状态反向扩展。如果问题只能从起点单向扩展或者目标状态不唯一双向广搜就不适用。常见的适用场景包括迷宫最短路、八数码、推箱子、以及各种棋盘类状态搜索问题。判断标准很简单如果你能用BFS从起点搜到终点且终点状态是明确的那么大概率也能用双向BFS加速。8.2 通用模板的骨架我把双向广搜的通用逻辑抽象成了一个模板核心就是两个队列、两个访问集合、一个层扩展函数。每次从一边扩展一层检查是否与另一边相遇。如果相遇返回当前步数如果超过深度上限返回不可达。这个模板的关键在于状态编码和状态生成这两个函数它们需要根据具体问题来实现。其余部分都是通用的可以直接复用。8.3 常见变体与注意事项有些题目要求输出具体路径而不只是步数。这时候双向广搜就需要额外记录每个状态的前驱相遇后再从两边分别回溯拼接成完整路径。这个实现比只求步数复杂不少但思路是一样的。还有些题目的状态空间不是均匀的某些状态的扩展代价不同。这时候双向广搜需要配合优先队列使用变成双向Dijkstra或者双向A*。这类变体的实现复杂度更高但核心思想仍然是两头对进。我在实际使用中的体会是双向广搜的代码量比单向BFS多不了多少但性能提升非常显著。只要问题满足适用条件优先考虑双向广搜准没错。唯一需要注意的是状态编码和判重的实现这两块写好了剩下的就是套模板的事。