椰程信奥 · 教案
搜索2 · 教案
课题
CSP复赛专题15 · 搜索2（剪枝策略 + BFS） —— 对应视频 21′11″，课件 18 页
教学目标
| 维度 | 内容 |
|---|
| 知识与技能 | ① 说出五种剪枝策略及适用场景；② 独立写出 BFS 四步框架（入队即判重）；
③ 完成八皇后的对角线判重与回溯；④ 完成抓住那头牛的 BFS 最短路。 |
| 过程与方法 | 通过对同一棵搜索树"剪枝前后访问节点数"的量化对比，建立可度量的优化意识。 |
| 情感态度价值观 | 认识到"优化必须以正确性为前提"，养成暴力对拍验证的习惯。 |
教学重难点
重点：BFS 的"入队即判重"与"首次到达即最优"；八皇后的三数组判冲突与回溯恢复。
难点：最优性剪枝的成立条件（代价单调不减 + best 正确初始化）；把实际问题建模成状态图。
教学过程
| 环节 | 页码 | 教师活动 | 学生活动 | 设计意图 |
|---|
| 引入 | P2 | 给出量级冲击：3 分支 15 层 ≈ 1400 万，20 层 ≈ 35 亿 | 估算并惊叹 | 建立"必须剪枝"的动机 |
| 剪枝 | P3–4 | 讲五法；跑动画①对比 | 先猜剪掉几个 | 量化而非玄学 |
| BFS | P5–7 | 讲四步框架；跑动画② | 口述队列变化 | 抓住 BFS 的骨架 |
| 例1 | P8–10 | 降维 → 三数组 → 动画③ → 代码 | 指认下一次试哪列 | DFS 综合训练 |
| 例2 | P11–12 | 建模 → 动画④ | 猜步数再验证 | 认知冲突 → 记住 BFS |
| 例3 | P13 | 三剪枝汇合，动画⑤ | 对号入座 | 综合应用 |
| 辨析 | P14 | 四个高频失分点 | 改错 | 防 WA |
| 检测 | P15–16 | 动画⑥ + 四道题 | 独立完成 | 形成性评价 |
板书设计
BFS 四步：① 起点入队并标记 ② 取队首 ③ 是目标 → dist 即答案 ④ 邻居未访问 → 标记+入队
★ 入队即判重（不是出队时）
八皇后：col[c] ／ d1[行−列+N] ／ d2[行+列] → ★ 标记后必恢复
剪枝五法：顺序 ／ 冗余 ／ 可行性 ／ 最优性 ／ 记忆化
易错预警（逐条点名）
① 出队时才判重 → 队列爆炸；② 八皇后漏回溯 → 解数为 0；
③ 对角线下标负数 → 越界；④ best 初值写成 0 → 剪光整棵树。
作业
- 必做：OJ 题包 QUEEN（八皇后）、COW（抓住那头牛），要求 AC。
- 选做：把小猫爬山写成完整搜索（含三种剪枝），并与不剪枝版本对比运行时间。