信息竞赛搜索算法模板与优化：从DFS/BFS到IDA*的实战指南

1. 搜索算法的整体认知与竞赛定位先聊一个很多竞赛选手都踩过的坑拿到一道搜索题第一反应是“不就是DFS和BFS吗”然后直接开写写着写着发现超时再回来加剪枝加完剪枝发现过不了样例最后对着代码发呆半小时骂自己当初为什么不把状态设计得再想想。搜索在信息竞赛里是一门“看着简单、用到极深处极难”的算法。它的内核是穷举状态的策略但又远不止穷举——剪枝、估价、双向、迭代加深、状态压缩、记忆化、启发式搜索每一个方向都能单独撑起一道省选甚至国赛级别的题目。进阶指南里的“搜索相关”模板恰恰就是把这些散落的技巧整理成一套可以直接套用的框架让我们在考场上不至于从零开始摸着石头过河。从竞赛定位来看搜索通常出现在两个位置一是暴力分二是正解。暴力分的搜索往往要求你快速写出能拿部分分的版本这时候模板化的DFS/BFS框架能帮你节省大量调试时间正解的搜索则要求你把搜索作为一种高级算法来使用比如状态空间的巧妙压缩、启发式函数的精确设计。很多选手忽视了后者导致只会写“裸搜”题目一变就僵住。这篇文章我打算按自己的实战经验从搜索的底层模板开始一层层往上拆基础DFS/BFS怎么写得又稳又快、状态压缩搜索的常见套路、剪枝的几大方向、启发式搜索IDA*、A*的比赛应用、双向搜索和迭代加深的具体写法最后附上我自己的刷题路径和避坑清单。每个部分都给出可直接复制的模板代码和针对性的解释保证不是贴一段代码就完事而是把“为什么这么写”讲透。2. 基础DFS与BFS模板的精细化写法2.1 DFS模板从递归框架到回溯细节DFS深度优先搜索是所有搜索算法的基础。竞赛里的DFS模板看起来都差不多但真正能稳拿分的写法有几个关键细节必须注意。先说通用模板我们以“n皇后问题”这类经典回溯题为例#include bits/stdc.h using namespace std; int n, ans; int col[20], diag1[40], diag2[40]; // 列、主对角线、副对角线 void dfs(int row) { if (row n) { ans; return; } for (int c 0; c n; c) { if (col[c] || diag1[row c] || diag2[row - c n]) continue; col[c] diag1[row c] diag2[row - c n] 1; dfs(row 1); col[c] diag1[row c] diag2[row - c n] 0; // 回溯 } } int main() { cin n; dfs(0); cout ans \n; return 0; }这个模板最核心的地方在于回溯时状态的恢复。很多新手会在递归后忘记把标记恢复导致同一状态被重复使用答案直接错掉。记住一个口诀进入递归前“占坑”出递归后“还坑”——这是DFS能正确枚举所有路径的前提。另一个容易出错的是对角线的表示。我们用row c表示主对角线从左上到右下用row - c n表示副对角线从右上到左下加n是为了把负数下标偏移到非负。这个技巧其实是一个通用的坐标变换套路后面在做状态压缩搜索时还会遇到类似思维。在实际竞赛中DFS模板还应具备几个“保命”优化用位运算替代布尔数组。在n不超过20的题目里可以用整数或bitset来存储状态回溯时也只需要^操作比数组快一个量级。后面会单独讲状态压缩。提前定义好搜索顺序。比如“每一步尽量先尝试限制更多的分支”这在剪枝中叫做“优先搜索可行性较小的分支”往往能极大提升剪枝效果。递归参数尽量少。能通过全局变量/引用传参时不要用值传递。竞赛里递归深度可能上万参数拷贝会带来无谓开销。2.2 BFS模板队列与状态的入队规范BFS广度优先搜索通常用于求最短路、最少步数以及“状态可以抽象成图”的题目。模板的核心是“逐层扩展”保证第一次访问到目标状态时就是最优解。一个典型的BFS模板以棋盘走迷宫为例#include bits/stdc.h using namespace std; struct State { int x, y, step; }; const int dx[4] {1, -1, 0, 0}; const int dy[4] {0, 0, 1, -1}; int n, m; char grid[105][105]; bool vis[105][105]; int bfs(int sx, int sy, int tx, int ty) { queueState q; q.push({sx, sy, 0}); vis[sx][sy] true; while (!q.empty()) { State cur q.front(); q.pop(); if (cur.x tx cur.y ty) return cur.step; for (int k 0; k 4; k) { int nx cur.x dx[k], ny cur.y dy[k]; if (nx 0 || nx n || ny 0 || ny m) continue; if (grid[nx][ny] #) continue; if (vis[nx][ny]) continue; vis[nx][ny] true; q.push({nx, ny, cur.step 1}); } } return -1; } int main() { cin n m; int sx, sy, tx, ty; for (int i 0; i n; i) { cin grid[i]; for (int j 0; j m; j) { if (grid[i][j] S) sx i, sy j; if (grid[i][j] T) tx i, ty j; } } cout bfs(sx, sy, tx, ty) \n; return 0; }BFS模板的核心细节有三点第一入队即标记。很多新手习惯在出队时才标记访问这会导致同一层的节点被重复入队队列膨胀好几倍甚至MLE。正确做法是一旦一个状态被生成且合法就立刻在vis中标记。这是BFS模板最关键的“纪律”。第二状态中直接携带步数。虽然也可以用dist数组来记录但直接把步数作为结构体成员往往更直观尤其当状态本身包含多维信息比如行政坐标钥匙状态时结构体更加灵活。第三边界检查放在最前面。不要先判断是否能走再判断边界那样容易漏判数组越界。正确顺序是先判坐标是否在界内再判障碍、再判已访问。次序错了小数据没事大数据一来就RE。3. 状态压缩与记忆化搜索的进阶模板3.1 位运算状态压缩的核心模式当搜索的状态可以用一个整数来表示时状态压缩就派上了用场。最经典的场景是“旅行商问题TSP”、 “子集枚举”、 “图上的状态转移”。在竞赛题中经常出现n 20这类限制一旦看到这种范围就要立刻想到状态压缩DP或状态压缩搜索。举个最常用的模板——基于状态压缩的回溯比如“分配问题”给n个人分配m项任务每个人做每项任务有不同收益求最大总收益要求每个人最多一项任务int n; int a[20][20]; int dp[1 20]; // 记录当前使用的人的状态 void dfs(int task, int mask, int sum) { // 剪枝当前收益 未来最大可能收益 已知最优 // 记忆化dp[mask] 记录到达这个状态的最大收益 }实际上状态压缩搜索往往直接转成记忆化搜索Memoization或DP更优但竞赛中我们经常“先搜索记忆化”因为记忆化就能实现类似DP的效果又比纯DP更直观——尤其是状态维度多、转移顺序不显然时。一个典型的记忆化搜索模板以数位DP的简单版为例比如统计[0, x]中不含4的数字个数int dp[20][2]; string s; int dfs(int pos, int tight) { if (pos s.size()) return 1; if (dp[pos][tight] ! -1) return dp[pos][tight]; int limit tight ? s[pos] - 0 : 9; int res 0; for (int d 0; d limit; d) { if (d 4) continue; res dfs(pos 1, tight (d limit)); } return dp[pos][tight] res; } int solve(int x) { if (x 0) return 0; s to_string(x); memset(dp, -1, sizeof(dp)); return dfs(0, true); }这个模板是数位DP中非常常用的“记忆化搜索”写法。它的精髓在于用tight表示“当前位是否受上界约束”。很多人第一次看到这个参数会觉得绕但你只要理解tight1时当前位只能取0~limit否则可以取0~9。通过记忆化所有pos和tight的状态只被计算一次复杂度从指数级降到O(位数×状态数)。记忆化搜索和状态压缩相结合时常见场景是“棋盘覆盖”、“八数码”、“推箱子”这类游戏类问题。每个棋盘状态可以编码成整数如把棋盘按行展开成二进制再用unordered_mapint, int或map记录到达该状态的最少步数。关键点是状态的编码与解码必须可靠建议用宏或内联函数统一封装避免手写出错。注意记忆化搜索中dp的维度一定要覆盖所有影响后续决策的参数。漏掉一个参数比如漏掉tight会导致状态错误合并答案错得离谱。建议在写记忆化搜索前先把“状态由哪几个参数唯一确定”写在草稿纸上。3.2 状态压缩BFS如何用整数表示复杂局面有些BFS题目状态不仅仅是坐标还包含一些开关状态、钥匙状态、蛇的身体等。这时我们可以将整个局面编码为一个整数配合vis数组/哈希表去重。经典模板以“带钥匙的迷宫”为例地图上有若干钥匙某些门需要特定钥匙才能通过。求从起点到终点的最短路径。struct State { int x, y, keyMask, step; }; bool vis[ N ][ N ][ 1 K ]; // K为钥匙种数 void bfs() { queueState q; q.push({sx, sy, 0, 0}); vis[sx][sy][0] true; while (!q.empty()) { State cur q.front(); q.pop(); // 到达终点返回 for (int dir 0; dir 4; dir) { int nx cur.x dx[dir], ny cur.y dy[dir]; if (越界 || 墙) continue; int nk cur.keyMask; if (地图[nx][ny] ak) nk | (1 k); // 捡钥匙 if (地图[nx][ny] Ak !(nk (1 k))) continue; // 没钥匙过不去 if (vis[nx][ny][nk]) continue; vis[nx][ny][nk] true; q.push({nx, ny, nk, cur.step 1}); } } }这里的关键是keyMask用二进制位来表示携带的钥匙集合。比如有4种钥匙mask0b1010就表示有第1种和第3种钥匙从低位数。当拾取钥匙时做nk | (1 idx)判断是否有钥匙时做nk (1 idx)。这套位运算非常自然配合vis数组的第三维就可以正确处理“同一位置但携带钥匙不同”的状态。在竞赛中状态压缩BFS的坑主要是空间。vis数组的第三维大小等于1 K当K较大比如10以上时内存可能爆掉。这时要么用unordered_map来记录已访问状态要么进一步压缩状态如把坐标也编码进整数。我的建议是如果N*N*(1K)超过 1e7就果断用哈希表虽然慢一点但能保命。4. 剪枝优化的四大方向与实操模板4.1 可行性剪枝与最优性剪枝搜索的暴力版谁都会写但能让搜索在限定时间内跑完的全靠剪枝。剪枝可以分成两大类可行性剪枝这个分支不可能到达答案和最优性剪枝这个分支就算走下去也不会比当前最优解更好。我见过不少选手在写DFS时只想着“能不能提前return”但很少系统地分析剪枝的维度。实际上一个高效的搜索算法应该同时考虑多个剪枝条件而不是只靠一个“金剪子”。典型的可行性剪枝例子搜索组合数时如果当前选了几个剩下的不够凑满目标就剪掉。模板void dfs(int start, int cnt, int sum) { if (cnt (n - start 1) need) return; // 剩下的全选都不够 if (sum target) return; if (cnt need sum target) { ... } for (int i start; i n; i) { if (sum a[i] target) continue; // 最优性剪枝 dfs(i 1, cnt 1, sum a[i]); } }这里的cnt (n - start 1) need就是典型的可行性剪枝——判断“就算把后面所有元素都选上数量是否够”。像这种剪枝往往能极大减少搜索树的分支而且代码就一行性价比极高。最优性剪枝的常见形式是“当前步数 已知最优解时 return”。在“最少步骤”类题目中我们通常初始化ans INF每次dfs传入当前的步数如果step ans就直接剪掉。这种剪枝简单粗暴但配合迭代加深使用时比单纯判断step更有效。4.2 顺序剪枝与上下界剪枝搜索顺序对剪枝效果影响巨大。同样一组数据一个良好的搜索顺序可能让时间从超时降到几十毫秒。竞赛中常用“从大往小搜”或“优先搜索约束最多的分支”。这听起来抽象我举一个“木棒拼接”的经典例题题目是给定若干根散木棒的长度要把它们拼成若干根等长的完整木棒求可能的最小原始木棒长度。这是一个典型的搜索剪枝题。很多新手直接按输入顺序搜索会超时而正确的做法是把所有木棒按长度从大到小排序搜索从大到小选记录上一次尝试失败的木棒长度相同长度不在同一个位置重复尝试当拼好一根新木棒时如果第一根木棒就失败直接回溯到上层。其中“相同长度不重复尝试”就是顺序剪枝而“第一根失败直接回溯”属于上下界的隐含剪枝。这些技巧在竞赛模板中非常常见。bool dfs(int idx, int cnt, int curLen) { if (cnt k) return true; for (int i idx; i n; i) { if (used[i] || curLen a[i] target) continue; if (a[i] a[i-1] !used[i-1]) continue; // 相同长度跳过 used[i] true; if (curLen a[i] target) { if (dfs(0, cnt 1, 0)) return true; } else { if (dfs(i 1, cnt, curLen a[i])) return true; } used[i] false; if (curLen 0 || curLen a[i] target) return false; // 关键剪枝 } return false; }这个模板几乎就是“木棒拼接”的标准解法。其中if (curLen 0 || curLen a[i] target) return false;是极其重要的几个剪枝之一。它的原理是如果在一根全新木棒的开头就失败那么这根木棒无论怎么换别的组合都无法成功因为后面的木棒没有能替代当前开头位置的同理如果当前木棒刚好被填满却无法完成剩余任务那么这根小棒也不能被其他方案替代。这两个剪枝可以让指数级搜索瞬间瘦身。4.3 剪枝的成效评估思路剪枝不是越多越好因为每次剪枝判断本身也有开销。如果某个剪枝条件很少触发却每次进入循环都要计算反而拖慢程序。我一般会在混合剪枝时给每个剪枝打一个“触发频率”的标签高频且计算便宜直接放在循环内部开头。低频但计算复杂放在函数入口处先判断再进入循环。极端情况剪枝只在特定数据上需要平时可能用不上但写上无妨。实际做题时我会先在暴力版本上加上最简单的可行性/最优性剪枝看能否通过部分测试点如果超时再逐步加入更复杂的剪枝并用随机数据测试剪枝后的扩展节点数。这种方法比盲目堆剪枝高效得多。5. 启发式搜索IDA* 与 A* 的实战模板5.1 A*的估价函数与优先队列实现A* 算法是带有优先级的BFS它的核心公式是f(n) g(n) h(n)其中g(n)是到达当前状态的实际代价h(n)是对从当前状态到目标状态的代价估计。只要h(n)不大于真实代价即“可采纳”A* 就能保证第一次出队的目标状态是最优解。A* 在竞赛中的典型场景是求带权图最短路径、八数码问题等。以八数码为例状态是3x3棋盘g是已经走的步数h可以采用曼哈顿距离之和。模板如下#include bits/stdc.h using namespace std; struct State { string board; // 棋盘编码成字符串 int g, h; bool operator(const State other) const { return g h other.g other.h; // 小顶堆 } }; int manhattan(const string board) { int sum 0; for (int i 0; i 9; i) { if (board[i] 0) continue; int target board[i] - 1; // 期望位置 int x1 i / 3, y1 i % 3; int x2 target / 3, y2 target % 3; sum abs(x1 - x2) abs(y1 - y2); } return sum; } int solve(string start) { priority_queueState pq; unordered_mapstring, int dist; pq.push({start, 0, manhattan(start)}); dist[start] 0; string goal 123456780; while (!pq.empty()) { State cur pq.top(); pq.pop(); if (cur.board goal) return cur.g; if (dist[cur.board] cur.g) continue; // 旧状态跳过 int pos cur.board.find(0); int x pos / 3, y pos % 3; for (int dir 0; dir 4; dir) { int nx x dx[dir], ny y dy[dir]; if (nx 0 || nx 2 || ny 0 || ny 2) continue; string nxt cur.board; swap(nxt[pos], nxt[nx * 3 ny]); int ng cur.g 1; if (dist.count(nxt) dist[nxt] ng) continue; dist[nxt] ng; pq.push({nxt, ng, manhattan(nxt)}); } } return -1; }这个模板里有几个竞赛细节值得注意board用string编码查找0的位置用find交换直接用swap编写极其方便。虽然比整数编码略慢但胜在清晰适合赛时快速实现。priority_queue的排序规则是反直觉的operator返回g h other.g other.h才能让f最小的先出队。很多人第一次写容易反掉建议直接记住这个写法。unordered_map记录dist是为了处理“同一个状态被不同路径到达”的情况。当发现新的g不比记录的dist小就跳过避免无效扩展。A* 的难点不在模板而在h的设计。竞赛中常用h有曼哈顿距离、欧氏距离、模式数据库等。一般来说h越接近真实代价搜索节点越少但同时计算h的开销也越大。对于类似八数码的问题曼哈顿距离是一个很好的折中。5.2 IDA*迭代加深与启发式结合的递归写法IDA*Iterative Deepening A*是“迭代加深DFS”与“A启发式”的结合。它不用优先队列而是把阈值作为DFS的深度限制不断加大阈值直到找到解。其优势在于不需要维护dist哈希表空间占用小递归结构简单代码比A短。缺点是可能重复搜索很多次但对许多题目来说仍然高效。以“数独”或“骑士周游”类问题为例IDA*的模板是这样的int maxDepth; bool dfs(int depth, int pos, int totalCost) { if (depth estimate(pos) maxDepth) return false; // 超出阈值 if (isGoal(pos)) return true; for (每个后继状态 nxt) { if (dfs(depth 1, nxt, ...)) return true; } return false; } void solve() { maxDepth 0; while (true) { if (dfs(0, start, 0)) break; maxDepth; } }关键点在于depth estimate(pos) maxDepth这个判断。这里estimate是从当前状态到目标状态的最少步数估计它必须要小于等于真实步数。每一步迭代maxDepth1其实就是把搜索树的半径加大一圈并通过启发式估计来避免探索“死活到不了目标”的分支。我在做迭代加深题目时有一个经验是maxDepth的递增步长不一定非要是1有时候可以加2甚至加3。因为如果答案在很远的地方每次只加1会导致大量重复搜索但步长过大又可能首超一定距离错过更优解。一般先从1开始如果估计答案距离较长可以改成“当前深度估计值”作为新的阈值这样收敛更快。IDA* 适合那些“状态很多、路径很长、但估计函数较好”的题目。比如“骑士到达目标”的题用IDA就比BFS更简洁。因为骑士的棋盘状态太大BFS会MLE而IDA用DFS天然省空间。6. 双向搜索与迭代加深的模板与适用场景6.1 双向BFS正向和逆向同时扩展双向BFS用来解决“起点和终点都明确状态空间巨大”的最短路问题。它的思想是从起点和终点同时各扩展一层当两边状态相遇时把步数相加得到最短路径。复杂度从b^d降到2 * b^(d/2)提升不是一点点。模板以单词变换为例每次改变一个字母问最少步数int bfs(string start, string target) { if (start target) return 0; unordered_mapstring, int dist1, dist2; queuestring q1, q2; q1.push(start); q2.push(target); dist1[start] 0; dist2[target] 0; while (!q1.empty() !q2.empty()) { // 每次扩展较小的队列 if (q1.size() q2.size()) { swap(q1, q2); swap(dist1, dist2); } int sz q1.size(); for (int i 0; i sz; i) { string cur q1.front(); q1.pop(); int d dist1[cur]; for (每个可能的变换 next) { if (dist1.count(next)) continue; if (dist2.count(next)) return d 1 dist2[next]; dist1[next] d 1; q1.push(next); } } } return -1; }双向BFS的模板有几个关键技巧每次优先扩展队列元素较少的一侧这可以保证总扩展量尽量小。实现上直接swap两个队列和对应的距离表代码很简洁。当生成的后继状态已经在对方距离表中出现时说明双方搭上了桥此时d 1 dist2[next]就是最短路径。距离表用unordered_map因为状态总数通常比较大数组不方便。双向BFS并不适用于所有题型。它要求“逆向搜索”也能进行即我们要能从目标状态反推前驱。例如迷宫类问题通常可以从终点反向走但如果题目给的是“操作序列”反向操作和正向操作往往不等价这时就要小心设计逆向生成函数。6.2 迭代加深DFS的经典写法迭代加深DFSIDDFS是另一种应对“深度未知”的搜索策略。它通过限制搜索深度从小到大递增来解决“DFS会一条路走到黑BFS空间太大”的问题。它在状态空间为树形时非常高效因为每层节点数通常是指数增长的重复搜索上层带来的额外代价往往可以接受。模板以“埃及分数”为例把真分数拆成若干个单位分数之和bool dfs(int depth, int maxDepth, long long a, long long b, long long lastDeno) { if (depth maxDepth) { if (a 0) { // 记录答案 return true; } return false; } // 从 lastDeno1 开始枚举分母 for (long long i max(lastDeno 1, (b a - 1) / a); i (maxDepth - depth) * b / a; i) { long long na a * i - b; long long nb b * i; if (na 0) continue; if (dfs(depth 1, maxDepth, na, nb, i)) return true; } return false; }这里(b a - 1) / a是保证当前分数a/b不小于1/i的最小分母而(maxDepth - depth) * b / a是保证剩余项都能用单位分数表示。这套上下界也是迭代加深搜索中“启发式剪枝”的体现。迭代加深与IDA的关系非常紧密当迭代加深DFS中加入“剩余深度下界”剪枝时就升级成了IDA。我的建议是如果题目不需要复杂估价函数就直接用IDDFS如果需要优化在IDDFS里加一个estimate()函数变成IDA*代码改动很小但效果明显。7. 竞赛实战中的搜索题解构套路7.1 从题目条件快速判断搜索类型在拿到一道题时不要急着写代码先花两分钟判断它适合哪种搜索类型。我总结了一套“选拔标准”数据范围极小n 8一般直接用DFS全排列枚举配合剪枝。如数独、八皇后、排列组合。n 20状态压缩搜索或状态压缩DP。需要最短步数且状态空间较大优先考虑双向BFS、A或IDA。尤其是题目给定了明确的目标状态如华容道、魔方启发式搜索几乎是必选项。求是否存在一种方案而不需求最优DFS往往足够注意剪枝。每条状态转移代价都相等BFS代价不等则用A*或IDDFS。这个判断不是百分百准确但它能帮你快速确定大方向。很多高级题实际上是多种搜索类型的组合例如“迭代加深剪枝状态压缩”这时候就需要综合运用多个模板。7.2 一个典型综合案例十六宫格数字谜题我拿一个常见的“十六宫格数字谜题”15-puzzle来演示综合解构的思路。这道题把1~15的数字放在4x4方格中留一个空位每次将空位移到相邻位置要求恢复为有序排列。如果直接用BFS状态总数为16! / 2大约是1.05e13显然存不下。此时我们需要用IDA*。估价函数可以用“每个数字的曼哈顿距离之和”因为每一步最多将一个数字的曼哈顿距离减少1所以这个估价是可采纳的。同时还需要一个奇偶性判断对于一个目标排列若逆序对数的奇偶性与空位行号满足特定关系则无解可以在进入搜索前直接排除避免无限迭代。这就是一个典型的“搜索选择估价函数可行性判断”的组合。我在模拟赛时写过这个题当时卡在内存上后来改成IDA*从几秒优化到几百毫秒深刻体会到选对搜索框架的重要性。7.3 竞赛中的搜索调试技巧搜索算法的调试比普通算法更痛苦因为一旦答案不对很难定位是“剪枝剪多了”还是“状态编码错了”。我自己的调试套路是这样先跑小数据关闭所有剪枝对比暴力和优化版本的结果是否一致。如果一致再逐步打开剪枝观察答案是否变化。一旦变化说明新打开的剪枝有逻辑漏洞。记录搜索树深度和扩展节点数的调试信息比如在dfs入口累计调用次数用来对比剪枝效果。对状态压缩类题目写一个解码函数打印出每个状态对应的实际局面方便肉眼观察。这些小技巧虽然不直接改变算法但能大幅节省调bug的时间。竞赛场上调通一道题往往比想出算法更耗时间。8. 从模板到高分的进阶训练路线模板只是起点真正的高分需要把模板内化成自己的“肌肉记忆”并在各种题目里灵活变形。我个人比较推荐的三阶段训练法是第一阶段裸模板过题。找十几道不同类型的搜索题包括DFS、BFS、状态压缩、双向BFS、IDA*每类至少两题。这个阶段不追求效率只求把模板写熟。写的时候手不要看代码自己要能默写出来。第二阶段剪枝强化。选一些经典的搜索难题题目名一般带“搜索”、“剪枝”关键词比如木棒拼接、靶形数独、生日蛋糕。做完之后对比题解中的剪枝看看自己的搜索树大了多少倍。不断尝试优化直到时间和题解接近。第三阶段综合变形。做涉及搜索的省选/国赛题目这些题往往不裸考搜索而是把搜索作为某个环节的工具比如“在DP中转移时用搜索枚举子集”、“用搜索预处理状态”。这时候训练的是把搜索与其他算法结合的能力。我自己的体验是很多选手卡在第一阶段到第二阶段之间因为他们觉得“模板我都会了剪枝太玄学”。但剪枝不是玄学它的本质是尽量不重复计算并用数学上下界排除无用分支。遇到一道题多问自己几个问题当前状态有没有无解的可能当前解有没有已经是次优的可能后面可选的元素还够不够这些问题想清楚了剪枝自然就出来了。还有一个高频问题刷搜索题是否需要大量时间我的回答是搜索是性价比极高的算法类型。你花两周专项训练之后遇到绝大多数穷举类题目都会有清晰的思路。而且搜索对代码能力的要求很综合练搜索的同时递归、位运算、STL容器、复杂度分析都会得到提升。9. 常见搜索错误速查表与避坑清单我把过去几年刷题时遇到的搜索报错/答案错整理成了一张速查表每一条都是血泪经验。错误症状可能原因解决方法递归无限循环 / 栈溢出回溯时忘记恢复状态或状态转移成环检查回溯代码对访问过的状态做标记BFS答案偏大或偏小入队时未标记vis可能记录了多条路径入队立刻标记vis答案总是差1步数是从0开始还是从1开始没对齐统一起点步数为0转移时1状态压缩后下标越界二进制位运算不当或数组大小未开到1n用1 n申请空间位运算用括号括起来启发式搜索超时估价函数太弱或不是可采纳的提高估价值但保持小于真实代价IDA*无解时死循环没有判断无解条件或阈值增长无限先做可解性判断限定最大深度双向BFS返回错误步数步数合并时多算或少算一层画小例子检查连接处的步数剪枝后答案错误剪枝条件过强误删合法分支暂时关闭剪枝对比暴力结果这里重点说一下“启发式搜索超时”的问题。我最早写A*时h随便写了一个“相同数字个数”要是没有正确性和强约束力导致搜索几乎退化成BFS五分钟后跑不出来。后来意识到h必须是“到目标的距离下界”而且要尽量大。曼哈顿距离在网格问题中如此好用核心原因就是它既是下界又比“相同数字个数”大得多。这个原则适用于所有博弈和路径类搜索。最后还有一个容易被忽略的细节搜索题的数据读入和输出往往也有很多坑。比如多组测试数据时全局变量和距离表没有清空字符串包含空格导致cin读入失败状态编码时没有统一起始位置等等。建议把读入和状态初始化封装成函数每组数据调用一次减少人为遗漏。信息竞赛里的搜索模块内容远比想象中丰富。从基础DFS到IDA*每往上走一层对状态空间的理解就加深一层。模板的意义是让你在赛场上不慌但真正决定水平的是你对状态空间的洞察力知道哪些状态可以合并、哪些分支可以剪掉、哪个方向值得先去搜。把这些点想明白再配合本文给出的模板勤加练习搜索难题也会变得有章可循。