★ FEATURED ARTICLE 每年准备机试的同学翻到《王道论坛计算机考研机试指南》第五章基本都会觉得一股劲上来了。前面几章还在讲排序、字符串、数据结构本质上都是“已知套路 熟练调用”到了搜索这一章题目突然变得“活”起来不再有明显的公式套路更多是要求你自己设计状态、选择搜索方式、控制复杂度。这也是为什么很多人都说第五章是整本书的分水岭跨过去机试才算真正入门。这篇笔记我按照自己阅读第五章的节奏来写。内容会围绕“搜索”这个核心展开包括枚举、BFS、DFS、剪枝几个大块也会补充一些做题时的实际反馈和排查经验。如果你正在备战考研机试或者刚开始刷算法题、想把搜索基础打扎实这篇内容可以直接当作导读使用。1. 第五章在整本书里的定位以及为什么它值得单独写一篇笔记1.1 从“会写代码”到“会算法设计”的转折点前几章的排序、查找、字符串处理核心都在“掌握一种数据结构或一个现成 API然后正确调用”。学完那些内容你对一门语言的基本功会有底但这种能力本质上还是“照着说明书操作”。到了第五章搜索类题目要求的是把问题抽象成状态空间然后决定用什么方式去遍历这个空间。这个过程不再有标准答案同一个题你既能用枚举硬算也能用 BFS 求最短路还可以用 DFS 回溯加剪枝。选择不同代码长度、时间消耗、正确率都会差很多。我在读这一章的时候最大的感受是代码量本身并不大真正的难点在于“想到了什么”。比如一个看起来像数学题的倒水问题本质上竟然是一张图上的最短路一个拼接木棍的判定题绕来绕去最后要靠深度优先搜索加剪枝才能跑完。这种思维转换才是这一章真正想练的东西。1.2 机试里搜索题为什么常考搜索题在机试里出现频率高有两个原因。第一它几乎不需要超纲的知识背景。排序、图论、动态规划都有可能因为知识点没学而卡住但搜索的本质是“穷举所有可能”只要你懂递归、懂队列、懂状态标记任何题你都能至少写出一个暴力版本。第二搜索题特别适合考查“复杂度控制能力”。很多搜索题的朴素算法一定能得到正确答案但一定会超时这时候就要靠剪枝、优化枚举范围、选择 BFS 而非 DFS 来解决问题。这种能力没法靠背模板获得所以考官喜欢用它来区分考生。书中这一章的选题也很有代表性。它没有一上来就甩难题而是用几个经典例子把“广度优先搜索”“深度优先搜索”“枚举优化”这几个分支逐个打通。读完之后你再去做题库里的搜索题至少能判断出“该用哪种搜索、核心状态是什么、大概需要什么级别的优化”。1.3 这一章的知识结构拆解我自己读下来的结构大致可以分成三块枚举法。这是最朴素的搜索核心是“确定搜索空间、找到缩小空间的规律”。书中用了一些常见题来展示比如判断一个范围内的特殊数字、查找满足条件的组合。这部分内容偏简单但非常重要因为后面很多剪枝思路本质上是“在枚举的过程中提前去掉无效分支”。广度优先搜索BFS。核心是“队列 分层扩展”适合求最短步数、最少操作次数这类无权重最短路问题。本章用倒水、迷宫、最少步数等题目做载体强调状态标记的重要性。深度优先搜索DFS与回溯。核心是“递归深入 状态恢复”适合求方案数、判断是否存在可行解、回溯枚举所有排列组合。这部分相对难需要用剪枝来对抗指数级的状态增长。后面我会按照这个结构逐个展开我实际做题时遇到的问题和总结的模板。2. 枚举法先把“暴力”这件事做到极致2.1 枚举之前先算一笔复杂度账很多人提到枚举就想到 for 循环套 for 循环然后直接开跑。这个习惯在刷题时很危险因为机试的评测环境通常有 1 到 3 秒的时间限制你写的程序必须在限制内跑完所有测试数据。我一般会在写枚举代码前先估算一下复杂度如果状态总量小于 10 的 7 次方直接暴力大概率没问题如果接近 10 的 8 次方就要考虑常数和剪枝如果超过 10 的 9 次方基本不能再无脑枚举了。举一个书里最常见的例子给定一个范围要找出满足某条件的所有数字。如果直接遍历区间内每一个数区间长度是 n每次判断条件需要 O(1) 或者 O(log n)总复杂度就是 O(n) 或 O(n log n)。在 n 达到 10 的 6 次方时完全没问题但如果你内层还套了一个遍历复杂度变成 O(n²)那 n 一旦上万就很容易超时。所以枚举不是不能写而是写之前一定要知道当前的数据量级。2.2 缩小枚举量的三个实用方向书里没有刻意总结但我在做题后归纳出三个最常用的优化方向第一缩小范围。很多题目里某个变量的取值其实有明确的上下界甚至可以根据数学关系直接算出来。比如百钱买百鸡这种经典题与其让三个变量都在 0 到 100 之间循环不如先固定两个量第三个量用总数减去前两个得到这样直接少一层循环。第二利用对称性。有些问题里枚举的对象存在顺序无关性比如组合问题。如果 A、B、C 三个值的顺序不影响结果就可以强行要求 A ≤ B ≤ C这样能减少大量重复状态。我一开始经常忽略这一点结果同样的组合被枚举了好几遍白白浪费时间。第三提前终止。如果题目问的是“是否存在”一旦找到答案就可以直接结束循环如果是求最小值的枚举也可以在找到一个可行解后继续尝试更优解但不必等待所有情况都跑完。这里需要注意编码方式不要在循环内部频繁调用重函数能拆出来的计算放到循环外。2.3 枚举题的一个易错点边界条件枚举题代码简单容易让人的警惕性下降。实际上边界条件是枚举题最容易翻车的地方。一个区间如果题目说的是“大于等于 a 且小于 b”代码里就应该写成i a; i b; i少一个等号结果就全错。我之前做题时遇到过一种情况题目要求找某个范围内的“回文数”我循环写成了从 1 到 n但没注意到 n 本身也是两位数回文判断函数里取每一位的逻辑在特殊输入上出了 bug最后在评测时才暴露。为了避免这种情况建议在写完枚举代码后专门用最小边界、最大边界、恰好等于边界的数据各测一遍。2.4 枚举和后面所有搜索的关系读这一章时不要觉得枚举太简单就跳过。实际上BFS 本质上是一种“按层枚举”的搜索DFS 本质上是“沿着一条路径枚举到底”。剪枝所要做的事情就是在枚举过程中删掉不可能产生答案的分支。如果你枚举时就没有“状态空间”的意识后面学 BFS、DFS 时很容易把代码写得一团乱。我建议把枚举题当作练手刻意训练自己分析状态空间的能力这个题有多少个变量每个变量的取值范围是什么总状态数是多少哪些状态可以合并。这个习惯养成了后面所有搜索题都会好写很多。3. BFS把“最短步数”问题变成队列的层层推进3.1 什么时候该用 BFSBFS广度优先搜索最典型的应用场景是在一个“无权重图”上求最短路径。所谓“无权重”是指每次操作带来的代价相同比如走一步、倒一次水、按一次按钮。机试题里很多描述是“最少需要几次操作才能从初始状态到达目标状态”这类问题十有八九要用 BFS。一个很容易踩的坑是看到“最少”“最短”就直接上最短路算法或动态规划却忽略了状态空间本身可能就是一张隐式图。书里的倒水问题就是这样表面上是倒来倒去实际上每个“两个杯子的水量组合”就是一个节点“倒一次水”就是一条边起点是初始水量状态终点是目标水量状态。这时候用 BFS 天然合适因为每个操作代价都是 1第一次到达目标状态的层数就是最少操作次数。3.2 BFS 的固定模板骨架我习惯把 BFS 模板固定成四步定义状态结构体。结构体里放当前状态的所有关键信息比如坐标 x、y或者两个杯子的当前水量。定义标记数组。标记数组用来记录哪些状态已经访问过避免重复入队。初始化队列把起点状态入队并标记起点。循环处理队列弹出队首判断是否为目标如果是则返回距离如果不是则生成下一步的所有可能状态能入队的入队。代码骨架大致长这样struct State { int x, y; int step; }; int bfs(State start, State target) { queueState q; bool visited[MAXN][MAXN] {false}; q.push(start); visited[start.x][start.y] true; while (!q.empty()) { State cur q.front(); q.pop(); if (cur.x target.x cur.y target.y) { return cur.step; } // 枚举所有下一步状态 for (int i 0; i nextCount; i) { State next generateNext(cur, i); if (valid(next) !visited[next.x][next.y]) { visited[next.x][next.y] true; next.step cur.step 1; q.push(next); } } } return -1; // 无解 }这个模板看起来简陋但实际做题时最花时间的地方往往不是在模板本身而是“怎么生成下一步”和“怎么标记状态”。尤其是后者如果标记维度不够BFS 就会陷入死循环。3.3 状态设计是 BFS 的关键很多初学者写 BFS标记数组只考虑了一个维度。比如迷宫题里只用visited[x][y]标记坐标倒水题里却只记录第一个杯子当前水量。这种情况非常容易出错。倒水问题里第二个杯子的水量不同即使第一个杯子水量相同后续还能到达的状态也是完全不同的如果只按第一个杯子去重就会漏掉很多分支甚至得到错误的最少次数。正确的做法是用完整的状态向量做标记。坐标题就用visited[x][y]杯子题就用visited[a][b]表示两个杯子的水量组合。有些更复杂的状态还需要增加维度比如记录当前剩余油量、当前朝向等。标志位越多状态区分越细搜索就越不容易出错但也会更占内存。所以要在正确性和空间开销之间取一个平衡。3.4 从倒水题理解“隐式图”书里的倒水题给我留下很深的印象。题面大致是有两个容量固定的杯子初始有一定水量允许的操作是“把一个杯子的水倒入另一个杯子直到源杯为空或目标杯满”要求最少的倒水次数让某个杯子达到指定水量。当时我看到这个题的第一反应是列数学方程想了半天也没理清。后来才意识到这就是一个 BFS状态是(a, b)也就是两个杯子的当前水量从每个状态出发可能的下一步是有限的最多只有几种倒法目标状态是满足a target || b target的任意状态。用 BFS 一层层扩展第一次遇到目标状态时的步数就是答案。这个例子很好地说明了为什么 BFS 比数学推导更通用。数学方法可以解决特定条件的问题但一旦题目改了杯子数量、操作方式数学解法可能就失效了BFS 却还能继续工作只是状态维度变多一点。3.5 多组输入下最容易犯的错忘记清空标记数组机试题目很多都是“多组测试数据”也就是程序会循环读入多组输入。我第一次做 BFS 题时把标记数组定义成了全局变量结果只在程序开头初始化了一次后续每组新数据都会带着上一组的访问记录导致明明有解的搜索返回了 -1。排查了很久才发现是visited没清空。解决方式有两种一种是在每组数据输入后手动memset重置标记数组另一种是用“时间戳标记法”也就是额外开一个visTime数组每次使用前把当前组号写入对应位置判断时检查该位置存的值是不是当前组号。第二种方法在多次 BFS 时效率更高因为不用每次把整个数组清零。4. DFS 与回溯递归里的“状态恢复”是灵魂4.1 DFS 的核心思想一条路走到黑再回头DFS深度优先搜索和 BFS 的区别在于遍历状态树的顺序。BFS 是逐层扩散DFS 则是从起点开始尽可能深地往下走走不通再返回换一条路继续。机试题里DFS 常用于三类问题判断是否存在可行解、统计所有可行方案、枚举排列组合。一个常见的误解是 DFS 一定比 BFS 慢。其实不一定。如果问题要求“输出所有可行方案”BFS 往往要保存大量中间状态内存爆炸DFS 则每次只维护一条路径空间开销小得多。所以当题目要求的是方案数而不是最短步数时DFS 反而更合适。4.2 回溯时改了什么就一定要还回去写 DFS 最容易出错的地方是“状态恢复”。递归深入一层时你可能修改了一个全局标记、往列表里加了一个元素、把某个位置改为已占用当从深层返回时这些修改必须全部撤销否则会影响同一层的其他分支。有一个经典例子用若干根长度不一的棍子拼一个正方形。DFS 的写法是为每根棍子安排位置如果当前位置已经摆满了就换下一根。这个过程中如果不恢复“某根棍子已使用”的标记那么后面的分支就会错误地认为这根棍子已经被用掉了导致本来能拼成的方案被判为不可能。我在学习时总结了一个口诀进入递归前做了什么修改退出递归后一定做对应的逆操作。而且逆操作必须在函数返回之前执行顺序要严格对应。如果修改了两处恢复时也要按相反顺序恢复两处。这个细节写错排查起来非常痛苦因为错误往往只在某些输入组合下才会出现。4.3 剪枝把不可能的分支提前砍掉DFS 的原始版本本质上是在一棵指数级规模的树上做遍历。如果不加任何限制状态稍微多一点程序就会卡死。剪枝是 DFS 的灵魂也是这个章节里让我收获最大的一部分。剪枝分两大类。第一类是可行性剪枝发现某个分支已经不可能产生合法解直接不进入。例如拼棍子问题中如果当前剩余长度小于下一根棍子的长度就不用考虑这根棍子了。第二类是最优性剪枝即使某个分支可能产生合法解但它的代价已经超过当前已知最优解也可以提前终止。这类剪枝常见于求最大/最小值的 DFS 中。还有一个实际技巧排序之后再 DFS。很多组合问题里数据从小到大或从大到小排序后剪枝效率会有明显提升。书中拼棍子的题就是一个例子按棍子长度从大到小排序后优先尝试长棍这样能更快地填满一条边也能更早暴露不可能的分支减少搜索量。4.4 递归深度过大怎么办DFS 用递归写比较直观但有些题目搜索深度很大递归层数可能超过几万甚至几十万。大多数评测环境默认的递归栈空间有限递归层数太高会导致栈溢出。应对方式有三种。第一改用显式栈模拟 DFS。这种写法代码会复杂一些但完全规避了递归栈深度问题。第二有些题目可以在设计状态时压缩深度比如倒水问题里很多加水倒水操作并不产生新的有效状态可以用状态合并减少递归深度。第三确认题目限制。机试题一般不会给特别深的搜索空间如果递归深度确实让人担心优先考虑用 BFS 或优化状态设计。4.5 一个常见的 DFS 模板排列组合式枚举后来的很多题都用到“逐个位置尝试”的 DFS 写法。模板大致是void dfs(int pos) { if (pos n) { // 已经生成一个完整方案检查并记录 checkAndRecord(); return; } for (int i 1; i n; i) { if (!used[i]) { used[i] true; array[pos] i; dfs(pos 1); used[i] false; // 状态恢复 } } }这个模板可以用来生成全排列、组合、子集等。我读第五章时最常做的练习就是自己动手把全排列、组合、子集都各写一遍然后比较它们在状态空间上的差异。这样后面遇到实际问题就能快速判断“这个题本质上是在枚举全排列还是组合还是子集”。5. 做这一章习题时我反复踩过的几个坑5.1 问题与排查速查表读这一章期间我整理了五六个高频问题放在这里当作速查清单。现象可能原因解决方式输出结果比答案多状态恢复没做好重复计数检查递归前后标记和列表的撤销输出结果比答案少状态标记维度不够漏情况确认 visited 数组覆盖完整状态程序运行超时枚举范围太大或剪枝不足估算复杂度增加可行性剪枝多组数据时结果错乱全局标记数组未清空每组输入前重置所有状态递归函数栈溢出深度过大或死递归检查终止条件或改为显式栈BFS 返回 -1 但实际有解目标状态判断条件写错检查目标条件是否覆盖所有要求这里面最隐蔽的是状态恢复问题。因为普通规模的数据下错误分支可能不影响最终结果只有特定数据组合才会暴露。我的建议是在调试 DFS 时打印出每一次递归调用的当前状态和标记数组肉眼观察哪一步恢复出了问题。5.2 关于 STL 使用的几个建议写搜索题时STL 是必需品但使用方式有讲究。第一queue的front和pop要小心。很多人弹出一个元素后还想着通过引用修改队列内部数据这是不安全的。建议每次先复制一份State cur q.front()再q.pop()后续操作在cur上进行。第二如果 DFS 需要记录当前路径vector不要频繁在递归中拷贝。可以把路径存在全局数组里用push_back和pop_back维护递归返回时自动恢复。第三deque和queue都能完成 BFS但queue语义更清晰。题目不需要双端操作时直接用queue就够了别为了花哨引入不必要的数据结构。5.3 调试搜索题的一个土办法搜索题的 bug 很难通过单元测试覆盖因为状态空间太大。我自己常用的调试手段是“小数据 打印”。先构造一个非常小的测试用例比如迷宫缩小到 3×3、棍子只有 3 根然后在关键位置输出当前状态和步数。这样能直观看到搜索是不是朝着预期的方向推进。如果程序在某种输入下陷入死循环不要急着加各种判断先在 BFS 的入队位置打印状态确认是否真的出现了重复状态。如果是基本就是标记数组没生效或状态设计不完整。6. 读完这一章之后你可以继续往哪个方向走6.1 把“模板”变成“思考习惯”我的建议是不需要死记 BFS 模板或者 DFS 模板更重要的是形成一套做题时的分析路径看到题目先用一两句话描述状态空间判断这个状态空间是“逐层扩展”还是“一条路走到底”再决定用 BFS 还是 DFS最后考虑标记和剪枝。这个分析过程比代码模板更重要因为模板是固定的分析思路才是活的。为了让这个思路固定下来我平时刷题时会专门用一个笔记记录每道题的状态定义、搜索方式、剪枝条件。每道题只写三四行但写完就印象深刻。后面复习时比重新读一遍代码效率高很多。6.2 相关知识点可以提前预热搜索这一章绝不是学完就结束。它和后面的动态规划、图论都有联系。最典型的是“记忆化搜索”用 DFS 搜索时如果某个状态的最优结果已经被计算过就可以直接返回避免重复计算。这个技巧本质上就是动态规划。所以读这一章时可以稍微留意哪些搜索题里存在大量重复状态提前感受一下“用数组缓存结果”这种思路。另外图论里的连通块计数、环检测、最短路径很多底层也都依赖 DFS 或 BFS。基础搜索学扎实了后面学图算法会轻松很多。6.3 我的一个小习惯每种搜索至少动手写三遍读这一章时我要求自己把书里的经典题在理解之后不看答案完整地写三遍。第一遍写完能过样例就停第二遍优化结构和剪枝第三遍把代码换成不同风格比如把递归 DFS 改成栈模拟。三遍写下来很多细节才能真正变成自己的东西。书里第五章的练习题数量不算多但每一题都有很强的代表性。我个人觉得这个章节最值得花时间的反而不是“刷更多题”而是把已经出现的题吃透能把题目的状态空间讲清楚。能做到这一点机试里的搜索题基本不会成为障碍。
阅读完成 · 觉得有帮助？
求解)
