NOIP 信息学：搜索及其优化 完整知识点文档
https://www.fmcraft.top/usr/uploads/2026/07/3625185257.pptx
一、前言：搜索算法定位
- 算法解题优先级：优先数学推导、递推、贪心、DP；无高效数学解法时，使用搜索。
- 搜索特点：通用性强、适用范围广；纯暴力搜索效率极低，必须配合各类优化才能通过大数据。
- 基础搜索分类：穷举、深度优先搜索（DFS）、广度优先搜索（BFS）。
二、核心基础概念
2.1 状态
- 定义：搜索的最小单元，决定搜索效率、思维难度、代码复杂度。
- 设计要点：靠刷题积累经验，状态定义优劣直接决定代码能否过时限。
2.2 搜索树
所有搜索过程均可抽象为一棵搜索树：
- DFS：纵向优先遍历整棵树，适合求全部可行解、构造方案；缺点是深度过大易栈溢出。
- BFS：逐层横向遍历，天然适合求最短/最小代价最优解；自带分层，第一次到达目标即为最优。
三、基础搜索算法实现
3.1 深度优先搜索 DFS（回溯）
通用模板
void dfs(int dep, [其他状态参数])
{
// 边界：到达目标状态
if(当前为目标状态){
记录答案/输出/计数;
return;
}
// 枚举所有可拓展状态
for(枚举所有下一步可能){
保存现场（修改全局/局部状态）;
if(该拓展合法) dfs(dep + 1, 新参数);
恢复现场（回溯，还原状态）;
}
}特点
- 使用系统栈/手动栈，递归实现；
- 不自动保证最优，需手动记录最优值；
- 深度过大时栈溢出（如POJ3278裸DFS会爆栈）。
3.2 广度优先搜索 BFS（队列）
通用模板
初始状态入队;
while(队列不为空){
取出队首元素，队首出队;
if(当前是目标状态){输出答案; return;}
// 拓展所有子状态
for(所有拓展方向){
if(状态未访问 && 拓展合法){
标记已访问（判重）;
新状态入队;
}
}
}特点
- 借助队列实现分层遍历；
- 第一次抵达终点一定是最小步数/最小代价，无需额外比较最优；
- 必须判重，否则重复入队无限循环。
四、经典入门例题：POJ3278 抓住那头牛
题目简述
农夫在数轴N，牛在K，三种移动方式，每次耗时1分钟：
- $X \to X-1$
- $X \to X+1$
- $X \to 2X$
求到达牛位置的最少时间。样例输入5 17，输出4。
算法选择分析
- 裸DFS：搜索树深度极大，系统栈溢出，且无法保证最优；
- BFS最优：分层遍历，首次走到K即为最小步数，是本题标准解法。
五、NOIP真题案例详解
5.1 NOIP2017提高组Day2 T1 奶酪（连通性DFS）
题意
无限大奶酪，高度$h$，内部有等半径球形空洞；空洞相交/相切可互通；空洞接触下表面$z=0$可进入，接触上表面$z=h$可逃出。判断老鼠能否从底部走到顶部。
核心思路
- 模型转化：无向图连通性，每个空洞是节点；
连通条件：两球心距离 $\le 2r$；
- 距离公式避免
sqrt防止精度丢失：平方比较
$$(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2 \le (2r)^2$$ - 全部变量使用
long long，防止大数溢出；
- 距离公式避免
- 起点集合：$z \le r$ 的空洞（接触下表面）；
- 终止条件：搜到任意满足 $z \ge h-r$ 的空洞（接触上表面）；
核心代码框架
void dfs(int id){
vis[id] = true;
// 判断是否连通上表面
if(hole[id].z + r >= h) flag = true;
for(int i = 1; i <= n; i++){
if(!vis[i] && 两球连通(id,i)) dfs(i);
}
}5.2 NOIP2014提高组Day2 T2 寻找道路（反向DFS+BFS最短路）
题意
有向图，边权均为1，求起点s到终点t的最短路径，约束：路径上每个点的所有出边指向的点，都能间接到达终点t。
分步解法
- 建两张图：正向图（原图）、反向图（所有边反转）；
- 反向图DFS：从终点t出发，标记所有能到达t的点
vis1[]； - 筛选合法点：一个点u合法当且仅当u所有出边指向的v都满足
vis1[v]=true； - 正向图BFS：仅走合法点，求s到t最短路；
数据注意
$n\le10^4,m\le2\times10^5$，稀疏图用vector邻接表；输入量大，禁用cin，改用scanf防超时。
5.3 NOIP2017普及组T3 棋盘（带状态记忆化DFS）
题意
$m\times m$棋盘，格子红/黄/无色；四向行走，异色花费1金币；可花2金币临时将无色格子染色，魔法不可连续释放。求左上角到右下角最小花费。
状态设计（三维记忆化）
f[x][y][can]：坐标$(x,y)$，can=0/1代表当前能否使用魔法，存储到达该状态最小金币；
状态转移
- 下一格有颜色：根据颜色是否相同累加金币，魔法重置为可用；
- 下一格无色：仅当魔法可用时，花费2金币，魔法置为不可用；
优化梯度
- 裸DFS：40分；
- 最优性剪枝：60分；
- 记忆化剪枝（记录每个状态最小代价）：100分。
5.4 NOIP2009提高组T4 靶形数独（DFS+搜索顺序优化）
题意
9×9数独，每个格子有分值，数字×格子分值总和最大化；无解输出-1。
优化梯度
- 暴力DFS顺序填格：40分；
- 预处理空白格、行/列/九宫格数字判重：75分；
最优优化（100分）：搜索顺序优化
每次优先选择可填数字最少的空白格填充，大幅剪枝无效分支；- 若某格无合法数字：可行性剪枝，直接回溯；
- 若只剩1种数字：直接填充，减少循环。
六、DFS核心优化：剪枝
6.1 可行性剪枝
当前状态已经不满足题目约束，后续无论怎么走都无解，直接回溯。
例：数独格子无可用数字、数轴坐标超出0~100000范围。
6.2 最优性剪枝
全局记录当前已知最优解；若当前已消耗代价 ≥ 最优解，后续路径只会更差，直接返回。
例：抓牛DFS记录当前最小步数，当前步数超过最优则剪枝。
6.3 记忆化剪枝（全局最优剪枝）
记录每个状态到达时的最小代价；再次走到同一状态时，若当前花费 ≥ 记录值，直接剪枝；否则更新记录。
适用：棋盘、最短代价类搜索问题。
6.4 搜索顺序优化
人为调整拓展节点的先后顺序，优先搜索分支少、更容易出解的路径，提前触发剪枝。
代表例题：靶形数独（优先填可选数字最少的格子）。
七、高阶搜索优化算法
7.1 迭代加深搜索 IDDFS
- 思路：限制DFS最大深度，从小到大逐层放宽深度限制；
- 优势：兼具DFS空间小、BFS保证最优的特点；解决深搜栈溢出问题；
- 适用：求最小步数、深度不确定的最优解问题。
7.2 双向BFS
- 思路：起点BFS、终点BFS同时向外拓展，两边相遇即得到最优解；
- 优势：搜索范围指数级缩小，大幅降低时间复杂度；
- 适用：起点终点明确、状态空间巨大的最短路问题（抓牛、迷宫最短路径）。
7.3 BFS配套优化：哈希判重
状态复杂（字符串、多维数组）无法开数组标记访问时，用哈希表存储已走过状态，避免重复入队。
八、搜索算法选择总结
| 算法 | 适用场景 | 核心优势 | 短板 |
|---|---|---|---|
| DFS | 求全部方案、连通性、构造解 | 代码简单、空间小 | 无法保证最优、深度大易栈溢出 |
| BFS | 最短步数、最小代价最优解 | 天然最优、分层遍历 | 队列占用空间大 |
| DFS+剪枝 | 最优值、代价最小类搜索 | 灵活，多重剪枝提速 | 需要手动维护最优答案 |
| IDDFS | 深度未知、需要最优、怕栈溢出 | 兼顾DFS与BFS优点 | 重复浅层搜索，轻微冗余 |
| 双向BFS | 超大状态空间最短路 | 搜索量指数级减少 | 代码逻辑更复杂 |
九、易错点汇总
- 距离比较时禁用
sqrt，平方后用long long避免精度、溢出问题； - 大数据输入使用
scanf/printf，cin关闭同步或直接淘汰； - DFS回溯必须恢复现场，否则状态污染；
- BFS必须判重，否则死循环；
- 连通性问题分清有向图/无向图，按需建反向图；
- 记忆化数组初始化无穷大，到达同一状态代价更小时才更新；
- 递归DFS注意递归深度上限，深度极大改用迭代加深或BFS。
十、配套上机习题
- 奶酪：基础连通DFS
- 飞越原野：BFS+记忆判重
- 寻找道路：反向DFS+正向BFS综合
- 棋盘：DFS+记忆化最优剪枝
- 靶形数独：DFS+搜索顺序优化
- 小木棍：DFS多重可行性/最优性剪枝
