算法竞赛搜索进阶：从DFS/BFS到剪枝与状态压缩-开发者社区

1. 写在前面：搜索不是“暴力”，是你还没学会的进阶思维

很多人一听到信息学竞赛里的“搜索”，第一反应就是“不就是暴搜嘛，DFS 扫一遍、BFS 扫一遍，数据一大就超时”。说实话，我之前也是这么想的，直到在某一次模拟赛中被一道看似简单的状态搜索题卡了整整两个小时，才意识到：搜索这门基本功，远不是“递归 + 循环”这么简单。它是一整套关于“状态定义、分支策略、剪枝时机、空间换时间”的方法论。

这篇进阶指南，我打算聚焦在竞赛中最常用的几类搜索模板和技巧上：DFS/BFS 的进阶写法、各类剪枝策略、状态压缩与记忆化搜索、双向 BFS、迭代加深以及 A* 的实战取舍。适合已经写过不少搜索题、但总觉得“别人能过我不能过”的选手，也适合刚进省队、准备系统性梳理搜索体系的同学。内容不会太入门，但我会把每个模板背后的思考过程拆开来讲，顺便附上我自己调试时的体会和踩过的坑。

搜索题在竞赛里有个特点：看起来思路谁都能想到，但拿满分的代码和拿部分分的代码往往只在“剪枝”和“状态表示”上有差别。这种差别，恰恰是进阶和入门的分水岭。下面我们直接进入正题。

2. 搜索基础模板的重新梳理：为什么 DFS 和 BFS 各有不可替代的场景

2.1 DFS 的“深度优先”到底优先的是什么

深度优先搜索，核心是用递归（或者显式栈）一直往深处走，走不动了再回头。很多人写 DFS 只是背了一个模板：

void dfs(int dep) { if (dep == n) { // 到达边界，处理答案 return; } for (int i = 0; i < n; i++) { if (vis[i]) continue; vis[i] = true; dfs(dep + 1); vis[i] = false; } }

但真正需要想清楚的不是这个框架本身，而是“搜索树的形状”和“每层分支的含义”。DFS 适合的场景有这么几类：

需要枚举所有可能的排列或组合，并且过程中可以逐步剪枝。
需要记录路径本身，比如迷宫问题、图上的简单路径问题。
递归深度可控、单次搜索空间不大但分支很多。

我举个例子，全排列问题你用 DFS 很自然，因为每一层就是在决定“当前位放哪个数”。但换成子集枚举、拆数方案、括号生成这类问题，DFS 的“层”定义就要谨慎。有人说这是“套路题”，我不这么看，深搜的难点从来不是递归本身，而是你怎么把原问题映射成一棵思路清晰的搜索树。

2.2 BFS 的“队列层序”为什么能保证最短路

BFS（广度优先搜索）用队列逐层扩展，第一次到达某个状态时，步数一定是最小的。这个性质在无权图的最短路、状态转移的最少步数问题里是无可替代的。

queue<int> q; dist[start] = 0; q.push(start); while (!q.empty()) { int u = q.front(); q.pop(); for (auto v : adj[u]) { if (dist[v] != -1) continue; dist[v] = dist[u] + 1; q.push(v); } }

这里有个很多人没注意到的细节：BFS 的“层”概念如果只是简单记录 dist 数组，在有些题目里还不够，你还需要记录路径或者方案。比如输出最短路的完整走法，就需要额外维护一个“前驱节点”数组。

另外还有一个实际经验：能用 BFS 求最短路就尽量不要用 DFS + 回溯去试。DFS 确实也能求最短路，但它的遍历顺序决定了它会先莽撞地跑到很远的地方，再折回来，而 BFS 是老老实实一层一层扩，很多时候在稀疏图、状态空间大的场景里，BFS 的访问顺序更有利于及早命中目标状态。

但 BFS 的问题也很明显：空间消耗是指数级的。一层状态可能就有几万个节点，队列撑不住。这时候就要考虑双向 BFS 或者 A* 了，后面的章节我会详细讲。总之，DFS 和 BFS 不是“谁替代谁”，而是“谁更匹配搜索树的形状”。树深而窄，用 DFS；树浅而宽，用 BFS；希望找最少步数且无权，BFS 首选；需要枚举全部方案，DFS 首选。

2.3 递归函数设计的三个关键点：参数、返回值与全局状态

进阶选手写 DFS，已经不是“能跑出答案就行”的水平了，而是要思考递归函数的三要素：参数设计，返回值设计，以及全局状态的管理。

先说参数：原则是“哪一层需要哪些信息，就传哪些信息”，但也不能无脑多传。比如迷宫问题，你需要传坐标 (x, y) 和当前步数 step；子集枚举需要传当前下标 pos 和当前已选集合；某些搜索过程中需要判断“之前的最大值是多少”，那就得额外传一个 curMax。

返回值上，有两种主流写法：一种是“void + 全局变量收集答案”的写法，适合枚举所有方案；另一种是“返回值 int/bool 直接向上传递最优解或可行性”的写法，适合“是否存在可行方案”或“最优值是多少”的问题。我个人强烈推荐在写“可行性搜索”时使用“返回 bool”的写法，因为一旦找到了目标就可以立刻 return true 剪掉整个递归子树，代码可读性也好。

全局状态的坑主要有两个：一是回溯时忘记恢复状态，二是局部变量和全局变量重名。恢复状态这个问题，几乎所有初学者都遇到过，比如递归完没把 vis[i] 改回 false，导致后面搜索路径缺失。我的习惯是：只要修改了全局状态，就一定要在 return 之前恢复，哪怕有几条分支已经确定不需要了，也先恢复再说，避免后续递归出错。更安全一点的做法，是把“需要回退的状态”用局部变量保存下来，在递归返回后还原，避免“漏恢复”和“错恢复”。

3. 剪枝不是玄学，是“信息量”的博弈

3.1 剪枝的本质：利用已知信息排除无用分支

很多同学写搜索只知道三个字：“要剪枝”，但不理解剪枝的本质。我觉得可以这样理解：搜索树上的每一个节点都代表一个“部分决策序列”，而剪枝就是在扩展到某个节点时，根据当前已知的信息，判断以这个节点为根的整棵子树不可能产生最优解或可行解，然后直接跳过。

剪枝的依据，来自题目的特殊性质。典型的有三类：

可行性剪枝：当前状态已经违反了约束条件，再往下搜也没有意义。
最优性剪枝：当前已知的局部代价已经大于等于当前搜到的全局最优解，不需要继续。
对称性剪枝：搜索结果在某种变换下等价的，只搜索其中一个代表。

我不建议把剪枝当成一个个孤立的技巧去背，而是要养成“每写一个搜索分支，就问自己一句：什么情况下来到这里必死或者必差”的习惯。真实的竞赛题里，往往不是一个剪枝威力巨大，而是多个小剪枝叠加之后，把指数级搜索空间压到了可接受范围。

3.2 经典剪枝策略实例：从“迷宫问题”到“木棒拼接”

先拿大家最熟悉的迷宫回溯来说。深搜走迷宫时，最简单的剪枝是“判断下一个位置是否越界、是否撞墙、是否走过”，这其实是可行性剪枝。但多数情况下这还不够，如果你是在找迷宫的一条可行路径而不是全部路径，可以用“终点连通性预判”：提前从终点反向 BFS 或者用 FloodFill 标记所有可达点，如果当前点不在可达集合里，直接剪掉。这属于“预处理剪枝”，思想是“先花小代价获得全局宏观信息，再用它指导搜索”。

再说一道很经典的搜索剪枝题：给定若干根长度不一的木棒，要把它们拼接成若干根等长的长棒，求长棒的最小可能长度。这种题目思路是搜索“每根长棒由哪些短棒组成”，但直接搜必炸。常见的剪枝组合是：

先排个序，从大到小尝试拼接，这样能让“长的先占用”，大幅减少搜索分支。这个是“优化搜索顺序”剪枝。
如果当前长棒已经接了一根短棒 x，继续接后续短棒失败，那么后续与 x 等长的短棒也一定会失败，直接跳过。
如果某个短棒作为“当前长棒的第一根”就失败了，那说明这根短棒无法放入任何长棒，立即判定整个方案失败。

“排序 + 等价长度跳过 + 第一根失败即整体失败”这三个剪枝组合在一起，能让原本不可能跑完的搜索跑进几百毫秒。这就是“信息量博弈”的典型例子。

3.3 剪枝过度的风险：当心“剪对了时间，剪错了答案”

剪枝也不是越多越好，剪枝的前提是“证明该分支不可能导致合法答案”。如果凭感觉剪掉一个可能含正确答案的分支，那你的程序就会 WA（答案错误），而且通常是针对特殊数据才错，极难排查。

我自己的一个亲身经历是：在某次练习中，我写了一道搜索题，加了一个自以为很妙的排序启发式，测试样例全过，放到判题平台上却在一组刁钻数据上 WA。我调了半天才发现，我的启发式排序让搜索优先尝试某些状态，但我却错误地写成了“如果这个顺序下失败就直接剪掉其他顺序”。这等于把“启发式优先级”当成了“排除规则”，完全是我的逻辑失误。

所以这里给大家一个检查清单：

剪枝剪掉的子树中，是否有可能包含最优解？
剪枝条件是否依赖了变化的全局变量？
剪枝条件是否在多次递归中被意外篡改？

只要这三条都确认无误，再放心的剪。

4. 状态压缩与记忆化搜索：让搜索变成“查表”

4.1 状态转移的关键：不是“我在哪”，而是“我去过哪”

有一类搜索题目，递归过程本身并不复杂，复杂的是“状态”太多了。比如经典的“旅行商问题（TSP）”的简化版：一个点可以重复经过，但每个点有一个“收集标记”要拿，问经过所有标记点的最短路径。这里简单的 DFS 会疯狂重复搜索“从 u 出发，但之前经过的集合不同”的相同子问题。

这种重复，本质上是“同一子问题多次出现”，而“子问题”的定义无非是：当前我在哪里，以及我之前的经历构成了什么样的状态。如果我们能用一个哈希值或一个整数把这个“经历集合”编码起来，就能用记忆化搜索把重复计算砍掉。

很多时候我们要做的状态压缩就是把集合映射成一个整数的位掩码（bitmask）。比如有 n 个元素，用整数 mask 的二进制第 i 位表示第 i 个元素是否已经被取走。这样一来，上面这句话就直接对应一个 int 变量，简单直接。

4.2 位运算实现状态压缩的常用技巧

掩码操作其实就是三板斧：

// 判断第 i 位是否为 1 (mask >> i) & 1 // 将第 i 位设为 1 mask |= (1 << i) // 将第 i 位设为 0 mask &= ~(1 << i)

竞赛里我还常用几个组合写法，比如枚举 mask 的子集：

for (int sub = mask; sub; sub = (sub - 1) & mask) { // sub 是 mask 的一个非空子集 }

这个写法能在线性枚举所有子集，很多状态压缩 DP 和记忆化搜索都要用。说句实话，状态压缩真正解决的不只是空间问题，更是“状态的唯一性”问题。因为很多搜索的重复在于：不同的递归路径走到了相同的“当前点 + 经历集合”，如果不压缩，这些路径会被当成不同状态反复算，而位掩码让这种重复显而易见。

4.3 记忆化搜索：把递归结果存下来，下次直接取

记忆化搜索几乎是“搜索进阶的第一课”。核心写法很简单：

int dp[1 << n][n]; memset(dp, -1, sizeof(dp)); int dfs(int mask, int u) { if (mask == (1 << n) - 1) return 0; if (dp[mask][u] != -1) return dp[mask][u]; int res = INF; for (int v = 0; v < n; v++) { if (mask & (1 << v)) continue; res = min(res, dfs(mask | (1 << v), v) + dist[u][v]); } return dp[mask][u] = res; }

这里的核心思想：dfs(mask, u) 的返回值只依赖 mask 和 u，与到达该状态的路径无关。所以同样的 (mask, u) 无论被谁调用，结果都一样。这就是“无后效性”，也是记忆化搜索区别于普通搜索的关键。

需要注意的是，记忆化搜索不是万金油。如果状态数量达到 2^n * n，n 到 20 左右基本就是极限了，再大内存会爆。所以你需要先算一下状态空间：n=20 时 2^20 * 20 约两千万个 int，就是 80MB 左右，在多数竞赛环境中还能接受；n=25 就完全不行了。此时要换思路，比如 meet-in-the-middle 或者启发式搜索。

5. 双向 BFS 与迭代加深：向“状态爆炸”亮剑

5.1 双向 BFS：从两端同时扩展，把指数降一半

BFS 最大的痛点是状态数按层数指数增长。假设每层平均分支因子是 b，搜到底部层数 d，那么单向 BFS 大约要扩展 b^d 个状态。但是双向 BFS 从起点和终点同时扩展，只要两边各扩展 d/2 层就能碰头，总状态数大约是 2 * b^(d/2)，当 d 较大时收益非常可观。

实现的时候有几个要点：

用两个队列分别模拟正向和反向的扩展。
用两个 Map（或数组）记录每个状态属于哪一侧以及对应的步数。
每次扩展时选择“当前队列元素较少的一侧”扩展，节省时间。
一旦一个状态被两侧都访问过，答案就是两侧步数之和。

写双向 BFS 最常见的误区是“只扩展一步再交换队列”，这其实不太对。更稳妥的做法是每一轮都选择“当前状态数更少的一侧”去扩展完整的一层，然后检查是否发生“相遇”。层与层的边界要处理好，否则同一层会重复计算步数。

5.2 迭代加深（IDDFS）：用重复搜索换取空间节省

有一种场景：深度可能很深，但答案是“最小深度”。此时直接用 DFS 很容易一头扎进很深的地方找不到答案；用 BFS 内存又不够。迭代加深就派上用场了：先限定深度为 1 搜一遍，没找到就限定深度为 2 再搜一遍，依次递增。

有人一听“重复搜索”就觉得浪费，但分析一下会发现：搜索树节点数主要是由最深层决定的，浅层的重复搜索在深层节点的对比下往往可以忽略不计。

bool dfs(int dep, int maxDep) { if (dep == maxDep) { // 判断是否满足条件 return isOk(); } for (auto nxt : expand()) { if (dfs(dep + 1, maxDep)) return true; } return false; } for (int d = 1; ; d++) { if (dfs(0, d)) break; }

迭代加深和 A* 比较像的地方在于“都有一个不断放大的界线”，但 IDDFS 不需要设计启发式函数，更容易落地。它在“埃及分数”这类数学搜索题目中表现很好，因为深度就是分成多少个分数，深度增加时还要维护“当前最大分母不得超过某个值”的剪枝，和迭代加深天然配合。

5.3 启发式搜索 A*：当“贪心预估”遇上“精确搜索”

A* 本质是 BFS 的扩展，它用启发式函数 h(state) 估计从当前状态到目标状态的最小代价，并用 f = g + h 作为优先级进行扩展。g 是已花代价，h 是预估剩余代价。

A* 要保证正确性，h 必须满足“可采纳性”：h(state) 对真实剩余代价的估计只能偏低，不能偏高。比如 15 数码问题中，用“每个数字到目标位置的曼哈顿距离之和”作为 h 是可采纳的，因为无论怎样移动，一个数字至少要移动曼哈顿距离那么多步。

但 A* 的实现比 BFS 复杂得多，对内存要求也高（需要维护 Open 表和 Closed 表），在竞赛里不会特别常用。我的建议是：

如果状态空间可以接受，优先用双向 BFS，简单可靠。
如果必须用 A*，一定要验证 h 的可采纳性，并且预估状态是否超过内存。
如果 h 简单且效果不错，IDDFS + 剪枝往往也能达到类似效果，代码更好写。

6. 搜索模板的综合应用与查错心得

6.1 如何快速判断一道题“该用哪种搜索”

我收到过不少同学私信问：“这道题到底用 DFS 还是 BFS？”这个问题其实有比较固定的判断思路：

题目要求枚举所有可行方案、输出路径、或者搜索树的深度有限，优先 DFS + 剪枝。
题目要求最少步数/最短距离，且状态转移代价为 1，优先 BFS。
题目状态数与路径无关，且有大量重叠子问题，优先记忆化搜索。
题目状态空间大、目标清晰、且可以设计好的启发式，考虑双向 BFS 或 A*。
题目深度未知但答案深度很小，可用 IDDFS。

当然，有经验的选手还会看数据规模：n 在 20 左右，位压缩记忆化可能够用；n 在 100，大概率不能用指数级的搜索，应该想别的算法。

6.2 搜索代码的常见卡点与调试技巧

搜索题的调试和普通题不太一样，因为它可能跑几百万次递归，strange bug 很难肉眼发现。我总结了自己最常用的几个调试手段：

第一个是“小数据对拍”。随机生成小规模数据，用暴力和优化版分别跑，对比结果。这一步能抓出 90% 的剪枝错误和状态恢复遗漏。我平时会写一个 Python 或 C++ 的朴素版跑小数据，再和我精心剪枝的版本对拍，效率极高。

第二个是“打印搜索树路径”。在 dfs 入口打印当前参数（比如 dep、mask、cur），在 return 之前再打印一次，观察是否有不合理的递归路径。注意这种调试只适合小数据，不然输出量爆炸。

第三个是“状态重置检查”。如果你发现结果和预期相差很大，优先怀疑全局状态恢复的问题。把全局数组改成函数参数传入（或反之）再跑一遍，往往能发现问题。

第四个是“边界值测试”。比如 n=1、n=最大、完全无解、答案是 0 的情况，这些边界最容易暴露数组越界或死循环。

6.3 从一个案例看搜索框架的搭建思路

假设我们遇到一道题：给定一个 n×m 的棋盘，有一些格子不能走，求从起点到终点的最短路径，并且路径上恰好经过 k 个特殊格子。这里如果只是求最短路径，就是个简单 BFS；但“恰好经过 k 个特殊格子”使得状态必须多一维。

此时我的选择是：状态定义为 (x, y, c) 三元组，c 表示已经经过的特殊格子数量。然后跑 BFS 即可，因为每个状态访问一次就够了。搜索代码框架：

struct Node { int x, y, c; }; int dist[105][105][15]; int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; queue<Node> q; dist[sx][sy][0] = 0; q.push({sx, sy, 0}); while (!q.empty()) { auto [x, y, c] = q.front(); q.pop(); for (int d = 0; d < 4; d++) { int nx = x + dx[d], ny = y + dy[d]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if (blocked[nx][ny]) continue; int nc = c + (special[nx][ny] ? 1 : 0); if (nc > k) continue; if (dist[nx][ny][nc] != -1) continue; dist[nx][ny][nc] = dist[x][y][c] + 1; q.push({nx, ny, nc}); } }

这道题的坑点在于：同一个 (x, y) 可能以不同的 c 到达，不能简单地用二维数组判重，必须用三维数组。很多人在“(x,y) 已访问就不再扩展”的习惯性写法里栽跟头，正是因为没有意识到“状态多于坐标”。