大学本科计算机科学与技术专业《人工智能》第3章搜索推理应用教学设计

大学本科计算机科学与技术专业《人工智能》第3章搜索推理应用教学设计

一、教学背景与前端分析

（一）课程定位与内容属性

本课程面向大学本科计算机科学与技术专业三年级学生开设，属于专业核心必修课“人工智能基础”的关键章节。第3章“搜索推理应用”在整门课程中起到承上启下的枢纽作用：前承第2章“问题表示与状态空间”，后启第4章“机器学习”及后续的自然语言处理、计算机视觉等应用模块。本章内容系统讲授确定性搜索、非确定性推理及其在复杂任务中的协同机制，是学生从理论认知过渡到工程实践的核心跳板。依据工程教育认证标准与计算机类专业教学质量国家标准，本章设计强调“解决复杂工程问题”的能力达成，深度融合计算思维与系统建模素养。

（二）学情分析

授课对象为已完成数据结构、算法分析与设计、离散数学等前置课程的大三本科生。认知特点表现为：具备扎实的编程基础与算法逻辑，但多数学生对人工智能领域特有的“状态爆炸”“组合爆炸”“不完备信息处理”等挑战缺乏具身经验；能熟练使用Python/Java实现经典排序与查找，却较少将搜索策略抽象为智能体决策框架；对推理机制的理解往往停留在逻辑学命题演算层面，尚未建立概率图模型与搜索代价之间的关联。调查显示，约65%的学生认为搜索算法仅是“更复杂的循环”，而无法洞察启发式函数对求解效率的数量级影响。因此，教学需在认知冲突处设阶，在抽象概念处搭桥，在代码实现处提格。

（三）教材与资源开发

选用“十三五”国家规划教材《人工智能导论（第4版）》作为主本，同时引入CMU、斯坦福CS221公开课讲义作为平行阅读材料。自行开发了“搜索推理虚拟仿真沙盘”——基于Web的交互式平台，支持学生拖拽构建状态空间图、动态可视化多种搜索算法的节点扩展顺序与剪枝过程；该平台已嵌入校级SPOC，并开放API接口供学生自测启发式函数的可采纳性与一致性。本章课件采用“双主线并行”架构：左侧持续展开理论推导的思维导图，右侧同步呈现对应代码框架与实时运行时间曲线。

二、教学目标与核心素养

（一）知识目标

1.精准复述状态空间图、搜索树、解路径的形式化定义，区分完全状态空间与隐式图搜索的异同【基础】【高频考点】。

2.系统阐述无信息搜索策略（广度优先、深度优先、一致代价、迭代加深）的完备性、最优性与时空复杂度【重要】。

3.严格论证启发式搜索的核心机制，包括A*算法的可采纳性定理与Consistency条件，以及如何通过松弛问题设计启发函数【非常重要】【高频考点】【难点】。

4.分类归纳对抗搜索中的极小化极大算法、α-β剪枝原理及其在博弈环境下的优化变体【热点】。

5.厘清确定性逻辑推理、概率推理与搜索过程的耦合模式，特别是贝叶斯网络中的近似推理与MCMC搜索【拓展】。

（二）能力目标

1.能够针对给定的经典问题（如八数码、旅行商、华容道、井字棋）独立完成从状态建模、算子定义到搜索算法选型与实现的全流程，并能在10000节点规模下通过实验对比验证算法效率【非常重要】。

2.具备为具体问题构造可采纳且计算代价低的启发式函数的能力，并能通过实验数据修正启发值的误差偏移【难点】。

3.能够在两人零和博弈场景中手工模拟极小化极大算法及α-β剪枝，并利用评价函数编写简单的博弈智能体【重要】。

4.初步形成“搜索即推理”的元认知，能够将未知环境下的探索—利用困境转化为搜索策略的在线调参问题【高阶】。

（三）素养目标

1.通过搜索算法的演进史（从图灵测试到AlphaZero），树立“理论突破驱动技术迭代”的学科价值观。

2.在对抗搜索案例分析中（如自动驾驶策略博弈），渗透人工智能伦理意识，理解自私搜索与全局最优的冲突。

3.养成对算法效率的“执念”——将降低时空开销视为算法工程师的职业尊严，培养精益求精的工匠精神。

三、教学重难点与关键信号

（一）教学重点

1.状态空间建模方法：状态表示、操作符集合、初始状态、目标测试、路径代价【基础】。

2.A*算法的原理与证明：f=g+h的评价函数、OPEN/CLOSED表的管理、可采纳性对最优性的保证【非常重要】【高频考点】。

3.α-β剪枝的阈值传递机制：通过父子节点值的反向更新实现剪枝【重要】。

（二）教学难点

1.启发式函数的设计策略：从曼哈顿距离到模式数据库，如何平衡启发值的精确度与计算开销【难点】。

2.对A*算法最优性证明的理解——尤其是当启发函数不可采纳时最优性丧失的数学本质【高频考点】【难点】。

3.将现实问题（如智能仓储路径规划）映射为搜索问题的形式化过程，包含代价函数的设定与约束处理。

（三）教学关键信号

1.认知冲突点：为什么深度优先不保证最优解，但工业界仍大量使用？

2.概念拐点：启发式搜索中的“启发”究竟指什么——不是盲目猜测，而是利用领域特定知识引导搜索方向。

3.情感触发点：当学生亲手编写的A*算法在八数码难题中瞬间求解15步最优解，而广度优先扩展数十万节点时产生的震撼。

四、教学准备与环境配置

1.硬件环境：智慧教室，支持小组研讨的六边形桌椅布局；每位学生配备可编程设备（笔记本电脑），教师机具备多屏广播能力。

2.软件环境：预装Python3.9+，集成开发环境推荐VSCode并统一安装PythonTestExplorer插件；自研“SearchPlay”可视化平台部署在校内镜像服务器，支持Chrome/Edge无插件访问。

3.教学资源：分层递进的实验语料库——基础层（八数码、missionaries-cannibals）、进阶层（拼图15、四皇后）、挑战层（自动驾驶静态轨迹规划简化版）；博弈对战平台，支持学生编写智能体进行在线锦标赛。

4.预习任务：在SPOC平台发布第3章前置微课视频，重点剖析状态空间图与树的差异，完成三个简单问题的状态建模作业，系统自动评判格式规范性。

五、教学实施过程（核心环节）

本环节共安排3课时，每课时50分钟，第1、2课时连续授课，第3课时与实验课融合为120分钟大课。教学实施过程采用“认知学徒制”范式，以真实问题为锚点，通过示范、脚手架、撤除、探索四阶段完成能力内化。

（一）第一课时：状态空间奠基与无信息搜索体系

1.情境创设与问题暴露（8分钟）

教师打开“SearchPlay”平台，展示罗马尼亚度假问题简化版——仅包含5个城市，但隐含环路。要求学生凭借直觉快速点击，找出从Arad到Bucharest的最短路径。平台实时记录每位学生的操作序列与耗时。

3分钟后停止，抽取一位操作步数少但非最优的学生，一位扩展节点极多的学生，将其操作轨迹回放。教师追问：“你刚刚的尝试本质上在做什么？为什么感觉走了很多重复路？”由此引出状态空间图形式化定义。

此环节【非常重要】——让学生在无算法指导下暴露朴素搜索的低效，产生对系统化方法的认知渴求。

2.形式化建模的精准拆解（12分钟）

教师以罗马尼亚问题为母版，从数学定义出发逐层剥解：状态是城市名称，初始状态集单一，操作符定义为“沿公路移动到邻接城市”，目标测试为“当前城市==布加勒斯特”，路径代价为公路里程。

随即迁移至八数码问题：要求学生用3×3元组表示状态，空白格的上下左右移动为操作符，目标测试为与目标布局逐一比对，路径代价为单位步数。教师巡视，收集2名学生的建模表述并投射到大屏，全班逐词批注【重要】。

本环节强调形式化的严密性：例如操作符必须定义前置条件（空白格不在边界），否则将产生非法状态。现场演示非法操作导致程序崩溃的后果，建立工程规范意识。

3.无信息搜索策略的树状推演与复杂度对冲（25分钟）

教师提出核心任务：“既然有了建模，现在用系统化方式遍历状态空间。”不提供任何启发提示，逐种讲解广度优先、深度优先、一致代价、迭代加深。

对于广度优先：使用队列动画模拟八数码的节点扩展顺序，每一层用不同颜色高亮。学生立刻发现——第零层1节点，第一层2节点，第二层4节点，指数爆炸直观呈现【基础】。教师追问：“你愿意用BFS解21点游戏吗？”催生对空间开销的警觉。

对于深度优先：以迷宫生成算法为类比，演示深度受限下的回溯。突然在搜索深度8时指向一个已经访问过的状态，引出环路与重复检测的必要性。此时不急于给出闭环表，而是让学生陷入思考——“如何避免原地转圈？”【认知冲突】

一致代价：突出与BFS的区别——队列换成优先队列，按累计代价g排序。在罗马尼亚图上手算模拟，当目标节点第一次出队时即找到最优解。教师故意将一个非最优解先入队，学生紧盯优先队列弹出序列，发现代价更小的节点始终抢占队首，深刻理解Dijkstra思想在搜索中的映射【重要】。

迭代加深：以“既想要深度优先的内存节省，又想要广度优先的最优性”为矛盾起点，逐层递增深度限制。现场用递归函数动画演示depth=1,2,3时的扩展情况，虽然多次重复扩展上层节点，但学生开始计算时间与空间的权衡。教师立刻给出理论结论：迭代加深在分支因子有限时时间复杂度仅略高于BFS，空间复杂度却等同于DFS【高频考点】。

本环节全程不使用PPT静态罗列，每一算法均以“教师模拟—学生猜测下一步—平台验证—总结规律”循环推进。

4.课堂诊断与即时巩固（5分钟）

通过智慧教学系统推送两道选择题：第一题判定BFS是否一定能找到最优解（设置代价非1的陷阱），正确率仅为58%，教师捕捉此数据，现场修改罗马尼亚图中一条边权重大于1，BFS立刻失效，学生顿悟“一致代价才是真正的通用最优算法”。第二题计算特定深度下迭代加深的相对冗余工作量，学生动手列等比数列求和式，现场反馈答案分布。

（二）第二课时：启发式搜索——智能的核心引擎

1.困境复盘与启发式直觉唤醒（6分钟）

回顾上一课留白：无信息搜索虽系统，但在15步以上的八数码实例中BFS内存耗尽、DFS可能永远找不到解。教师反问：“人类解决八数码时，为什么不会乱移？”学生回答：“我们会把棋子往目标位置靠近。”教师立刻抽象：“这种‘离目标还有多远’的估计，就是启发函数h(n)。”【非常重要】

2.启发函数的设计实验（14分钟）

平台展示八数码问题初始状态与目标状态，现场征集学生的“估价直觉”。多数人提出“错位数”，少数提出“曼哈顿距离”。教师不加评判，将两种h(n)分别注入A*骨架，同时运行并实时绘制扩展节点数与时间。

当曼哈顿距离算法在0.3秒内输出最优解而错位法用了2.1秒且扩展节点多三倍时，教室响起惊叹。教师立刻追问：“为什么曼哈顿距离更高效？它比错位数多捕捉了什么信息？”引导出“排序信息”与“距离信息”的差异。

此时引出严格定义：启发函数是对当前状态到目标状态最小代价的估计。并强调【基础】要求：估计值必须≤真实代价——这就是可采纳性。用八数码实例，曼哈顿距离永远不大于实际移动步数（因为每次移动只能缩小曼哈顿距离1或0），因此是可采纳的；错位数往往低估不充分（实际移动一次最多纠正一个错位？其实可能同时影响两个格子，但学生易在此误解），因此可采纳但信息量少。

3.A算法的形式化证明（12分钟）

本环节是【难点】与【高频考点】的交汇处。教师不直接呈现证明，而是铺设矛盾链：

首先明确定理：若h(n)可采纳，且搜索树中所有节点的代价非负，则A

首次扩展目标节点时一定找到最优解。

通过反证法引导：假设首次目标出队时不是最优，则OPEN表中必存在最优路径上的某个节点m，其f(m)<f(目标实际值)。由于h(m)可采纳，f(m)≤真实最优代价，而目标实际值就是真实最优代价，因此f(m)≤目标实际值。但优先队列以f值排序，若f(m)更小，m应在目标之前出队，矛盾。

逐句拆解此逻辑，并用平台展示一个反例——当h(n)不可采纳时，A*可能提前将非最优目标弹出。学生亲见不可采纳启发式导致算法失误，对可采纳性的必要性刻骨铭心【非常重要】。

4.启发式函数的增强策略（10分钟）

学生产生新疑问：可采纳的曼哈顿距离已经很快，还能优化吗？教师引出Consistency（一致性）与优势概念。以八数码为例，介绍“曼哈顿距离”与“气体距离”的差异，并推广至模式数据库（PatternDatabase）方法：预先计算任意棋子子集到目标位置的最短距离，存储于查找表，在线查表求最大值以保证可采纳且信息更丰富。

现场展示五年前学生设计的“24点计算启发式”作品，虽然不如当前先进，但其设计思路激励学生敢于创造【情感渗透】。

5.工程化迁移：罗马尼亚问题的真实地图（8分钟）

切换至完整罗马尼亚问题，包含20余个城市，公路距离已知。学生分组，各组设计不同的h(n)：直线距离、最小邻边、0函数（退化为一致代价）。通过平台API批量测试，记录扩展节点数、运行时间、是否保证最优。数据汇总后，全班发现直线距离虽弱但可采纳，计算极快；最小邻边不可采纳（为什么？因为到目标必须经过若干边，最小邻边仅是单步最小，累加可能小于真实距离），因此速度快但偶尔输出非最优。

结论导出：工业应用中，未必死守可采纳性，常通过牺牲最优性换取实时性——这是【热点】人机博弈、自动驾驶决策中的常态。

（三）第三课时（实验融合）：对抗搜索与推理应用综合实训

1.博弈树与极大极小思想（20分钟）

从单人搜索过渡至双人对战。以井字棋为实验对象，教师扮演先手，学生集体充当后手算法。教师在黑板画出初始空棋盘，提问：“如果你是AI，第一步应如何评估落子？”学生直觉给出位置优势评估。

教师引入形式化：定义局面评价函数（terminal：胜+1，负-1，平0）；MAX方试图最大化评价，MIN方最小化评价。

手工模拟三层深度下的极小化极大回溯：从叶子节点取值向上倒推。当推至根节点时，学生看到MAX方会选择导致最终值最大的分支，尽管该分支可能并非立即得利【重要】。

此过程中连续追问“如果对手不按最优走呢？”——引出最优策略的防御性本质，并关联到纳什均衡思想。

2.α-β剪枝阈值传播（25分钟）

在已有极小化极大树基础上，增加剪枝逻辑。教师设计一个典型剪枝案例：在MIN节点，若其当前最小值已不大于父节点MAX的当前最大值，则后续兄弟无需扩展。

逐帧动画演示α、β值的传递、更新、剪断过程。学生易在“α是MAX方保证，β是MIN方保证”上混淆，教师采用肢体语言：双臂张开表示β区间，收拢表示α值上升压缩β区间。当α≥β时双手交叉，剪枝。

随即每个学生获得一张随机生成的博弈树习题，要求在纸上标注搜索顺序与剪枝情况。教师巡视，揪出典型错误——错将父节点的α/β值与子节点混用。立即插入2分钟微讲解，并推送三道变式进行即时训练【难点突破】。

3.搜索与推理的交叉：概率搜索与贝叶斯推理（35分钟）

提升维度：搜索不仅能在确定环境中进行，亦能在不确定信息下推理。

设置情境：医疗诊断简化模型——三个症状，两种疾病，已知条件概率。问“若观察到症状1，最可能的疾病是什么？”学生尝试枚举所有疾病组合，但组合数随变量增多呈爆炸。

教师提出：这正是搜索问题——状态是变量赋值，操作是给未赋值变量赋值，目标测试是找到后验概率最大的完整赋值。但由于概率分布已知，可以用启发式引导搜索：优先选择对后验概率贡献大的变量赋值。

此处介绍束搜索（BeamSearch）在概率推理中的应用，保留k个高概率候选，舍弃其余。平台展示k=1、k=3、k=10时推理准确率与耗时曲线，学生发现k=3即可逼近全枚举精度，但时间仅为其1/50【拓展·热点】。

为加深理解，布置小组任务：利用平台提供的贝叶斯网络编辑器，构建一个3-5节点的地震/burglary报警网络，并用束搜索实现近似推理。各小组将推理结果与精确推理（变量消除法）对比，撰写误差分析报告。

4.综合实战：智能车静态路径规划（40分钟）

本环节作为三大课时的综合能力检核，采用真实工程简化案例。提供栅格地图（20×20），包含障碍物、不同路面代价（草地、砂石、公路）、时间窗约束。要求学生分组完成：

[1]状态空间建模——状态是（x,y,剩余时间窗），操作是上下左右。

[2]设计两种启发函数：欧氏距离/对角距离（可采纳）、基于障碍物密度的加权距离（不可采纳但更快）。

[3]分别用A、加权A

、IDA*求解，并统计成功率和平均规划时长。

[4]设置对抗情境：两车争夺同一目标点，各自用极小化极大思想制定抢占策略。

教师提供代码骨架，学生填充关键函数。现场气氛活跃，当某小组车辆在时间窗截止前0.1秒抵达目标时，全体鼓掌。教师随机抽取两组方案进行差异化对比，发现启发函数设计对结果影响巨大——仅使用欧氏距离的组扩展节点数是采用模式数据库组的8倍【非常重要】。

六、学习评价与反馈设计

1.诊断性评价：每课时前5分钟通过SPOC推送前测，依据作答情况调整讲授深度。例如在第二课时前发现40%学生混淆一致代价与A*，立即增