椰程信奥 · 说课稿

搜索2 · 说课稿（对应视频 21′11″，课件 18 页）

一、教材与学情

本讲是《CSP复赛专题15-搜索2》，承接专题14 的 DFS。学生在上一讲已经会写"一条路走到黑 + 回溯"， 但两个问题没解决：一是跑得慢（搜索树指数爆炸），二是求不出最优（DFS 找到的解未必最短）。 本讲正是针对这两个痛点给出两套武器：剪枝与 BFS。

二、教学目标

三、教学流程（45 分钟，课件 18 页）

环节页码教师活动学生活动时间
① 复习引入P2复述 DFS 三个动作，抛出"深 15 层 3 分支 = 1400 万节点"的量级冲击估算自己上一讲代码的节点数4′
② 五种剪枝P3–4逐条讲策略，动画①现场对比访问 10 个 vs 剪掉 4 个先猜剪掉多少，再看动画揭晓8′
③ BFS 核心P5–7讲"入队即判重"与"首次到达即最优"，动画②盯队列口述队列每一步的变化9′
④ 八皇后P8–10降维建模 → 三数组判冲突 → 动画③逐行试放 → 代码走读上台指出下一次该试哪一列12′
⑤ 抓住那头牛P11–12建模为无权图最短路，动画④看距离圈层扩散先猜 5→17 几步，再验证7′
⑥ 小猫爬山P13三种剪枝同时上场，动画⑤演示说出每条剪枝对应哪一步3′
⑦ 辨析检测P14–16动画⑥同图对照，四道检测题完成检测，互评2′

四、教学亮点

  • 亮点一：把剪枝做成"看得见的数字"。动画①给出"不剪枝访问 10 个 / 剪枝后访问 6 个、剪掉 4 个"的精确对比， 学生对剪枝的价值从"听说有用"变成"看到省了多少"。
  • 亮点二：用"猜 5→17 几步"制造认知冲突。多数学生按贪心猜 3 或 5，实际是 4（要先 ×2 冲过头再回退）。 这个反差一次性讲清"为什么求最少必须用 BFS"。
  • 亮点三：三种剪枝在同一道题里汇合。小猫爬山把优化顺序、可行性、最优性三条一起用上， 是本节最好的综合案例。

    • 五、教学反思预设

    最容易翻车的点：学生把"最优性剪枝"写成 cum >= best 却在 best 未初始化时（初值 0）剪光整棵树。 课上必须强调 best 初值为无穷大，且只在代价单调不减时才成立。