1. 项目概述从“会写”到“会搜”的算法进阶之路“Acwing算法提高课—搜索”这个标题对于任何一个在算法竞赛或技术面试道路上深耕的朋友来说都像是一盏明灯。它指向的不仅仅是“搜索”这个具体的算法分类更是一种解决复杂问题的核心思维模式。我自己在刷了几百道题、也带过不少新人后深刻体会到很多人算法基础不错一维数组、链表操作得心应手但一到二维矩阵、图论或者状态空间稍微复杂点的问题就立刻懵了。问题往往不是出在不会写for循环而是不知道如何系统性地、高效地“探索”一个庞大的解空间。Acwing的提高课正是瞄准了这个痛点它不教你语法而是教你如何把“搜索”这把利器从一把生锈的铁剑打磨成削铁如泥的宝剑。简单来说这个课程模块解决的核心问题是当问题没有显而易见的公式或贪心策略时如何通过系统性的枚举与剪枝在有限时间内找到可行解或最优解。它适合已经掌握了C/Java基础语法、熟悉基本数据结构数组、链表、栈、队列并且刷过一些基础题如Acwing算法基础课内容的开发者。无论是备战蓝桥杯、ACM-ICPC还是冲击大厂的技术面试深度掌握搜索技术都是你从“普通选手”迈向“高手”的必经之路。这里的“搜索”远不止是DFS深度优先搜索和BFS宽度优先搜索两个缩写它是一套包含状态定义、转移策略、剪枝优化和启发式引导的完整的方法论。2. 搜索技术核心思想与方案选型为什么搜索如此重要因为在面对NP难问题、组合爆炸或者路径规划时我们常常没有“一步到位”的完美算法。搜索的本质是“试探”与“回溯”是一种暴力美学但绝不是无脑的暴力。提高课的核心就是教你如何让这种“暴力”变得聪明和高效。2.1 深度优先搜索DFS与回溯框架DFS的核心思想是“一条路走到黑”不撞南墙不回头。它用递归或显式栈实现非常适合解决需要枚举所有可能方案、且方案呈树形结构的问题比如排列、组合、子集、棋盘放置N皇后等。为什么首选DFS对于这类问题解空间天然是一棵树DFS的递归调用栈完美模拟了这棵树的生长过程。每一层递归对应树的一层每一个分支对应一个选择。它的代码框架非常清晰void dfs(当前状态) { if (到达终止条件) { 记录或处理结果; return; } for (所有可能的选择) { if (选择合法) { 做出选择更新状态; dfs(新状态); // 递归深入 撤销选择恢复状态; // 回溯的关键 } } }这个“做出选择-递归-撤销选择”的模板是回溯算法的精髓。我个人的一个深刻体会是初学时最容易忘记“撤销选择”这一步导致状态污染结果乱七八糟。一定要在脑子里把递归树画出来明白每一层递归结束后状态必须恢复到进入这层时的样子这样才能正确探索其他分支。2.2 宽度优先搜索BFS与最短路径模型BFS的核心思想是“广撒网”一层一层地探索。它用队列实现保证最先找到的解决方案一定是步数最少的在边权为1的图中。这解决了“最短步数”、“最少转换次数”这类问题。为什么用BFS求最短路径因为BFS按距离起点的层次进行遍历第一次访问到某个节点时走过的路径必然是最短的。这是由队列的先进先出FIFO特性保证的。它的框架也很固定queue状态 q; q.push(初始状态); 标记初始状态已访问; while (q.size()) { auto t q.front(); q.pop(); if (t 是目标状态) { 输出结果或返回步数; break; } for (从状态t能到达的所有下一个状态 next) { if (next 合法且未访问) { q.push(next); 标记next已访问; 记录next的前驱或步数dist[next] dist[t] 1; } } }这里的关键细节是“标记已访问”的时机。一定要在状态入队时立刻标记而不是出队时。如果等到出队再标记同一层中可能会将同一个状态重复入队多次导致队列膨胀甚至死循环。这是我早期踩过的一个大坑。2.3 DFS与BFS的抉择问题性质决定工具选择DFS还是BFS不是凭感觉而是由问题性质决定的选DFS问题要求输出所有具体方案如所有排列、判断是否存在可行解如迷宫是否能走到终点、且树深度不会太深避免栈溢出。它的优势是占用空间与深度成正比代码简洁。选BFS问题要求最优解如最短路径、最少操作次数。它的劣势是空间占用与宽度成正比在状态空间大时可能内存爆炸。有些问题两者皆可但侧重点不同。比如经典的“迷宫问题”如果只问能否走出DFS更简单如果问最短路径BFS是正解。提高课会带你深入理解这种差异并教你如何根据数据范围做出选择。3. 核心优化策略剪枝与启发式搜索如果只会基础的DFS/BFS框架遇到稍大的数据范围就会超时。提高课的精华在于“优化”。让搜索变得高效的核心就是减少不必要的探索。3.1 剪枝艺术丢掉不可能的树枝剪枝就是在搜索树中提前判断某些分支不可能产生合法解或最优解从而直接跳过。这是将指数级复杂度降下来的关键。1. 可行性剪枝当前状态已经不可能满足题目要求直接返回。例如在“数独”游戏中当前格子所在行、列、九宫格内1-9的数字都已经出现那么当前分支无需继续。2. 最优性剪枝当前状态已经比已知的最优解差直接返回。例如在“旅行商问题”的搜索中当前路径长度已经超过了目前找到的最短回路长度后面再怎么走也只会更长果断放弃。3. 搜索顺序优化改变尝试选择的顺序能更快地接近答案或触发剪枝。例如在“小猫爬山”问题中先尝试重量大的猫可以更快地填满一辆车减少后续分支数量。这需要一些贪心思维和问题洞察力。4. 排除等效冗余避免搜索本质相同的状态。例如求组合数时[1,2]和[2,1]是同一个组合。我们可以在递归时传入一个start参数保证每次选择的数字索引是递增的从而避免重复。实操心得剪枝代码往往就是加在DFS的for循环里或递归开头处的几个if判断。但正是这几个判断体现了对问题的深刻理解。写的时候要问自己“我凭什么能肯定这个分支没用” 理由必须充分否则可能错失正解。多构造极端数据测试自己的剪枝逻辑是否正确。3.2 双向BFS与A*启发式搜索当状态空间非常庞大时即使剪枝单向BFS也可能力不从心。这时就需要更高级的策略。双向BFS从起点和终点同时开始BFS。当两个搜索 frontier 相遇时路径找到。它能将搜索范围从O(b^d)降到O(b^(d/2))其中b是分支因子d是深度。适用于知道明确起点和终点、且状态可逆的问题如“字变换”。实现关键使用两个队列和两个距离数组。每次选择当前队列中元素较少的一端进行扩展平衡搜索压力。判断相遇的条件是从一端扩展出的新状态在另一端的距离数组中已经被访问过。A*算法带启发函数的优先队列BFS。它不再是盲目扩展而是每次优先扩展“综合代价”最小的状态。综合代价f(state) g(state) h(state)其中g(state)是从起点到当前状态的实际代价h(state)是从当前状态到终点的估计代价启发函数。为什么有效一个好的启发函数h()能引导搜索方向更快逼近终点。例如在网格地图寻路中h()常用曼哈顿距离或欧几里得距离。核心要求启发函数h()必须满足可采纳性估计值永远不大于真实代价才能保证找到最优解。如果还满足一致性三角不等式则效率更高。注意事项A*算法需要用到优先队列堆时间复杂度涉及堆操作。h()函数的设计是灵魂设计不好可能退化成普通BFS甚至更差。4. 状态表示与存储技巧化繁为简的钥匙搜索的效率很大程度上取决于状态的表示是否紧凑以及查重是否快速。4.1 状态压缩用整数表示集合当状态涉及一个较小规模集合的选中情况时如小于等于20可以使用状态压缩。用一个整数的二进制位来表示某个元素是否在集合中。int state 0;初始空集。state | 1 i;将第i个元素加入集合。state (1 i)判断第i个元素是否在集合中。state ^ 1 i;将第i个元素从集合中取出如果存在。这广泛应用于“旅行商问题”、“棋盘覆盖”、“任务安排”等场景。它能将状态从一个数组或向量压缩成一个整数使得vis数组可以用简单的数组而非哈希表访问速度极快。4.2 哈希与判重避免原地打转在BFS或DFS中同一个状态不能重复访问否则会导致无限循环或冗余计算。如何快速判断一个状态是否已访问数组标记最适合状态空间小且能直接映射到数组下标的情况如状态压缩后的整数、坐标范围明确的网格。哈希表unordered_set通用性强适合状态复杂如字符串、向量的情况。但需要注意为自定义状态结构体编写哈希函数和相等比较函数。双哈希或康托展开对于排列类状态如八数码可以将一个排列映射成一个唯一的整数。康托展开是一种经典方法适用于全排列。避坑指南使用哈希表时如果状态是自定义结构体务必重载运算符和std::hash模板特化否则无法正确工作。对于性能要求极高的场景手写哈希表或使用开放寻址法有时比STL的unordered_set更快。4.3 编码与解码复杂状态的序列化对于更复杂的状态如多个整数、字符串组合我们需要将其“编码”成一个唯一键值用于判重并在需要时“解码”还原。简单编码将多个维度合并成一个long long确保不溢出。例如一个10x10网格中两个角色的坐标(x1,y1,x2,y2)可以编码为(((x1*10 y1)*10 x2)*10 y2)。字符串编码将状态各部分用特定分隔符连接成字符串。直观但效率较低。使用tuple或结构体直接作为哈希表的键需要提供哈希函数。选择编码方式的原则是在保证唯一性的前提下越快越好越小越好。编码解码的过程会增加常数开销需要在复杂度和便利性间权衡。5. 经典问题实战拆解与代码实现理论说得再多不如动手实现。我们挑两个提高课中的经典问题看看如何综合运用以上技巧。5.1 实战一AcWing 843. n-皇后问题DFS 状态标记问题要求在一个 n×n 的棋盘上放置 n 个皇后使得它们互不攻击。这是DFS回溯的经典例题。朴素DFS枚举每一行的皇后放在哪一列。状态是(当前行号, 棋盘状态)。每次递归到第n行就得到一个解。优化关键如何快速判断当前位置(row, col)能否放置需要检查同一列、同一正对角线、同一反对角线是否已有皇后。同一列用布尔数组col[N]标记。正对角线左上到右下row - col的值是常数范围是[-(n-1), n-1]可以加n偏移到[0, 2n-1]用数组dg[2N]标记。反对角线右上到左下row col的值是常数范围是[0, 2n-2]用数组udg[2N]标记。#include iostream using namespace std; const int N 20; // 对角线数量是2n-1开20足够 int n; char g[N][N]; // 棋盘 bool col[N], dg[N], udg[N]; // 列、正对角线、反对角线的占用情况 void dfs(int u) { // u代表当前正在放置第u行0-indexed if (u n) { // 所有行都放好了 for (int i 0; i n; i) puts(g[i]); // 输出整个棋盘 puts(); return; } for (int i 0; i n; i) { // 尝试在第u行的第i列放置皇后 // 判断(u, i)位置是否合法 if (!col[i] !dg[u - i n] !udg[u i]) { g[u][i] Q; col[i] dg[u - i n] udg[u i] true; dfs(u 1); // 递归处理下一行 // 回溯恢复现场 col[i] dg[u - i n] udg[u i] false; g[u][i] .; } } } int main() { cin n; for (int i 0; i n; i) for (int j 0; j n; j) g[i][j] .; dfs(0); return 0; }个人踩坑点对角线数组dg和udg的大小一定要开够2N因为u-in和ui的最大值可能超过n。曾经因为这里少开了几个位置导致数组越界出现非常诡异的错误。5.2 实战二AcWing 845. 八数码BFS 状态哈希在一个3x3的网格中摆放着1-8的数字和一个空格x。每次操作可以将空格与上下左右相邻的数字交换。给定初始状态和目标状态通常为12345678x求最少移动步数。问题分析这是一个典型的最短路径问题状态是3x3网格的排列。直接BFS即可。核心难点状态如何表示和判重一个3x3网格可以用一个字符串表示如123x46758。用unordered_setstring来记录已访问状态。关键操作如何从当前状态生成下一状态找到x的位置计算其二维坐标然后枚举四个方向的移动交换字符生成新字符串。#include iostream #include unordered_map #include queue #include algorithm using namespace std; int bfs(string start) { string end 12345678x; queuestring q; unordered_mapstring, int dist; // 同时记录距离和判重 q.push(start); dist[start] 0; int dx[4] {-1, 0, 1, 0}, dy[4] {0, 1, 0, -1}; while (q.size()) { auto t q.front(); q.pop(); if (t end) return dist[t]; int distance dist[t]; int k t.find(x); int x k / 3, y k % 3; // 一维下标转二维坐标 for (int i 0; i 4; i) { int a x dx[i], b y dy[i]; if (a 0 a 3 b 0 b 3) { swap(t[k], t[a * 3 b]); // 交换字符 if (!dist.count(t)) { // 新状态未访问过 dist[t] distance 1; q.push(t); } swap(t[k], t[a * 3 b]); // 换回来恢复状态用于下一个方向尝试 } } } return -1; } int main() { string start; for (int i 0; i 9; i) { char c; cin c; start c; } cout bfs(start) endl; return 0; }注意事项与优化状态恢复在for循环内交换字符生成新状态后判断并入队必须立刻再交换回来让t恢复原状才能尝试下一个移动方向。这是回溯思想在BFS中的应用。使用unordered_map这里用unordered_mapstring, int一举两得既判重又记录距离。比单独用一个set再加一个dist数组更简洁。一维与二维坐标转换这是处理网格问题的基本功务必熟练index x * cols y反过来x index / cols,y index % cols。潜在优化可以使用A算法启发函数h()可以定义为每个数字当前位置到目标位置的曼哈顿距离之和。对于更大规模的“十五数码”问题A几乎是唯一可行的解法。6. 调试技巧与常见问题排查搜索算法的代码逻辑复杂递归深度大很容易写出bug。分享几个我常用的调试方法和常见问题。6.1 调试方法论缩小问题范围小数据测试永远先用最小的、你能手动算出结果的数据测试。比如n皇后问题先用n4测试。八数码问题用一两步就能完成的初始状态测试。输出中间状态在DFS递归函数的开头打印当前的状态参数如当前行、当前路径。在BFS中每扩展一个状态可以打印这个状态。这能帮你看清程序的执行流程快速定位在哪一步出了问题。使用调试器在IDE如VS Code, CLion中设置断点单步跟踪观察变量值的变化。特别是递归函数观察调用栈的深度和状态变化是否符合预期。边界检查检查数组下标是否越界、递归终止条件是否正确、队列/栈是否在空的时候进行了弹出操作。6.2 常见问题速查表问题现象可能原因排查方法程序运行超时TLE1. 缺少必要的剪枝。2. 状态表示冗余导致搜索空间爆炸。3. 死循环BFS中未及时判重。4. 递归深度过大DFS栈溢出。1. 分析问题复杂度检查是否可加入可行性/最优性剪枝。2. 尝试压缩状态或更换更高效的判重容器。3. 检查BFS中新状态入队时是否立即标记已访问。4. 考虑改用迭代加深搜索IDS或BFS。答案错误WA1. 回溯时未正确恢复现场。2. 剪枝条件过于严格剪掉了正解。3. BFS最短路径记录错误步数未1或前驱记录错。4. 多组数据输入未重置全局状态和标记数组。1. 仔细对照“做出选择”和“撤销选择”的代码确保完全对称。2. 暂时注释掉所有剪枝代码看是否能得到正确结果。3. 手动模拟一个小例子跟踪dist数组的变化。4. 在main函数中每轮循环开始前用memset或循环重置所有全局变量。内存超限MLE1. BFS队列中存储的状态过大或过多。2. DFS递归深度太深调用栈占用内存大。3. 存储所有解的容器如vectorvectorint未及时清理。1. 优化状态表示减少单个状态的内存占用。2. 考虑使用迭代加深或双向BFS减少同时存在的状态数。3. 如果只需输出一个解或最优解不必保存所有中间解。输出结果重复或遗漏1. DFS求所有组合/排列时未处理重复元素或顺序问题。2. 状态判重逻辑有误导致同一状态被多次搜索或漏搜。1. 排序后在递归循环中加入if (i start nums[i] nums[i-1]) continue;跳过重复组合总和II。2. 检查哈希函数或相等判断函数是否正确。打印所有访问过的状态进行比对。递归深度过深导致段错误1. 问题规模大递归树深度超过系统栈限制通常约1e4层。2. 递归终止条件写错导致无限递归。1. 尝试改用非递归显式栈实现DFS或使用BFS。2. 检查递归基if (到达终点)是否正确确保递归参数能向终止条件收敛。6.3 性能优化实战心得当你的搜索程序在小数据上正确但大数据超时时可以尝试以下优化按性价比从高到低排序剪枝优先重新审视问题寻找最有力的剪枝条件。一个强剪枝可能将复杂度降低好几个数量级。状态压缩如果能将状态压缩成一个整数访问数组的速度远快于哈希表。更换容器如果状态可以用较小范围的整数表示用vectorbool或普通数组代替unordered_set。如果必须用哈希表尝试调整负载因子或使用更快的哈希函数。调整搜索顺序优先尝试“看起来更可能成功”的分支这能让你更快地找到解或触发最优性剪枝。算法升级对于最短路问题如果单向BFS超时考虑双向BFS。如果状态空间巨大且有好的启发函数考虑A*。代码层面减少函数调用开销如将一些参数设为全局变量、使用位运算代替算术运算、使用scanf/printf代替cin/cout在输入输出量巨大时。最后也是最重要的一点耐心和练习。搜索题的调试往往很耗时需要你静下心来像侦探一样分析状态流转。每独立解决一道复杂的搜索题你对递归、状态和优化的理解就会深一层。把Acwing提高课的搜索专题刷完并真正弄懂每一道题背后的思想你会发现再面对那些看似庞杂的问题时你手里已经握有了清晰的路线图。