《人工智能导论》 教案 第4章 搜索技术与问题求解

章节名称第4章搜索技术与问题求解授课方式理论(√);实验(√);实习()教学时数7（含实验2学时）教学目的及要求1.掌握搜索的基本概念、经典搜索问题及基本搜索策略；2.理解状态空间的定义、表示方法及状态空间图的搜索原理；3.熟练掌握盲目搜索策略（广度优先、深度优先等）的流程、优缺点及应用场景；4.理解启发式搜索的核心思想，掌握估价函数的设计，熟练运用A算法和A*算法求解问题；5.了解博弈问题的特点，掌握博弈树的概念、极大极小搜索策略及α-β剪枝技术；6.能够运用所学搜索技术解决实际问题，提升逻辑推理和问题求解能力。教学内容导言在人工智能领域，问题求解的核心是通过搜索技术探索问题的状态空间，找到从初始状态到目标状态的有效路径。无论是机器人路径规划、智能调度还是游戏博弈，都离不开高效的搜索策略。本节课将系统学习搜索技术的基本概念、各类搜索策略及实际应用，帮助大家理解如何在复杂空间中高效寻找最优解。4.1搜索的基本概念4.1.1经典的搜索问题1.硬币翻转问题：三枚硬币初始状态为“反正反”，每次翻转一个硬币，连续三次能否达到“正正正”或“反反反”。2.八数码问题：3×3九宫格中，8个数码棋子与1个空格，通过棋子向空格移动，从初始棋局到达目标棋局。3.猴子摘香蕉问题：猴子借助箱子摘取天花板上的香蕉，需描述从初始位置到成功摘到香蕉的过程。4.野人与传教士问题：3名传教士与3名野人渡河，满足船上人数≤2、野人数不超过传教士（允许无传教士）的约束条件。5.走迷宫问题：从入口出发，选择分岔路口路径，找到通往出口的路线。4.1.2基本搜索策略1.按搜索行进方向分类：正向搜索（从初始状态向目标状态推进）、逆向搜索（从目标状态回溯）、双向搜索（正向与逆向同时进行，寻找交集）。2.按是否运用启发信息分类：盲目搜索：无信息搜索，按预定规则搜索，如广度优先、深度优先搜索；启发式搜索：利用问题相关信息引导搜索，提高效率，如A算法、A*算法。4.2状态空间与图搜索4.2.1状态空间的概念与表示1.状态空间定义：对问题所有可能状态的抽象表示，包含问题不同阶段的全部情况，可通过图、向量、数组等形式描述。2.状态空间四元组：(S,O,S₀,G)，其中S为所有合法状态集合，O为操作算子集合，S₀为初始状态（S₀⊂S），G为目标状态集合（G⊂S）。3.示例：八数码问题的状态空间表示，状态集合为所有棋盘布局，操作算子为空格的上下左右移动，初始状态为任意布局，目标状态为固定有序布局。4.2.2状态空间图1.定义：表示问题全部可能状态及变迁的有向图，节点代表状态，有向弧代表状态变迁，弧上标签为操作算子，根节点为初始状态，解为初始到目标状态的操作路径。2.示例：旅行商问题的状态空间图，节点为城市，弧为城市间路径，标签为路径费用，需寻找总费用最低的回路。4.2.3状态空间图的搜索1.基本思想：从初始节点出发，按规则探索节点和边，直到找到目标节点或确定无解。2.核心数据结构：OPEN表：存放已生成未扩展的待考察节点；CLOSED表：记录已扩展节点及节点间关系（如父节点指针）。3.搜索过程：初始化→循环（取出节点→判断目标→扩展节点→更新表格→排序OPEN表）。图1图搜索的一般过程4.3盲目搜索策略盲目搜索又称无信息搜索，不利用问题特定信息，按预定策略搜索，通用性强但效率较低，常用策略包括回溯策略、广度优先、深度优先搜索。4.3.1回溯策略1.基本思想：回溯策略是一种系统地尝试状态空间中不同路径的搜索技术。它通过逐步深入探索路径，当遇到无法继续搜索时，会回溯到上一步，尝试其他可能的路径。这样，回溯策略能够有效地探索解空间，直到找到通向目标状态的正确路径。2.回溯策略示意图图2回溯策略示意图3.回溯算法存在的问题及解决方案回溯算法面临的两大问题：（1）回溯的深度问题：递归的深度往往与问题的规模密切相关，随着问题规模的增大，深度通常会呈指数级增长，容易导致内存栈溢出。解决方案：为了避免深度爆炸，通常需要对搜索的深度加以限制。（2）死循环问题：搜索陷入无效状态的无限递归，比如迷宫搜索当中的环路陷阱。解决方案：为了避免算法在环形结构中无限循环，需要对已访问的边进行标记，记录从初始状态到当前状态的路径。4.3.2广度优先搜索1.基本思想：按节点在树中的层次逐层搜索，优先扩展深度最浅的节点，新生成子节点放入OPEN表尾部（队列结构），保证先生成节点先考察。2.算法流程：初始化OPEN表（含初始节点）和CLOSED表（空）→循环：取出OPEN表首节点→判断是否为目标→扩展节点，生成子节点放入OPEN表尾部→重复至目标找到或OPEN表为空。图3广度优先搜索算法流程3.举例：八数码问题的广度优先搜索过程，展示OPEN表和CLOSED表的动态变化。4.性质：有解时必找到解，单位耗散下必为最优解，通用性强，但搜索空间大时效率低。4.3.3深度优先搜索1.基本思想：优先扩展最新生成的节点，新生成子节点放入OPEN表头部（堆栈结构），沿单一路径向下搜索，直至无后裔节点或找到目标，再回溯探索其他路径。2.算法流程：初始化OPEN表（含初始节点）和CLOSED表（空）→循环：取出OPEN表首节点→判断是否为目标→扩展节点，生成子节点放入OPEN表头部→重复至目标找到或OPEN表为空。图4深度优先搜索算法流程3.举例：以八数码问题为例，利用深度优先搜索算法求解从初始棋局到目标棋局的最佳走步4.改进策略：有界深度优先：设置深度限制dm，避免无限扩展；迭代加深搜索：逐步增大dm，反复搜索，回避dm选择难题。5.性质：又称纵向搜索，不能保证最优解，深度限制不合理时可能无解，最坏情况等同于穷举。4.4启发式搜索策略4.4.1启发式搜索概述盲目搜索效率低，启发式搜索通过引入与问题相关的启发性信息，引导搜索向最有希望的方向进行，核心是设计估价函数评估节点“希望”程度。4.4.2估价函数定义：f(n)=g(n)+h(n)，其中g(n)为从初始节点到n的实际代价，h(n)为从n到目标节点的估计代价（启发函数），启发函数的合理性直接影响搜索效率。4.4.3A算法1.基本思想：设计启发函数h(n)，以f(n)大小排列OPEN表中节点次序，优先扩展f(n)最小的节点。2.举例：八数码问题的A算法求解，估价函数f(n)=d(n)+w(n)（d(n)为节点深度，w(n)为错位数字数目），展示搜索树及OPEN表、CLOSED表变化。4.4.4A*算法1.定义：对A算法的改进，要求对所有节点n满足h(n)≤h*(n)（h*(n)为n到目标节点的最小代价），是最优图搜索算法。2.特点：单调性：启发函数满足h(ni)-h(nj)≤cost(ni,nj)且h(Goal)=0时，可减少路径调整工作量；可采纳性：有解时必找到最优解；信息性：h(n)越大，携带启发信息越多，搜索节点越少，但计算成本可能增加。3.举例：罗马尼亚度假问题，以城市到目标城市的直线距离为h(n)，求解最优路径。4.5博弈搜索4.5.1博弈的基本概念博弈是二人或多人对抗性活动，本节聚焦二人博弈，特点为轮流操作、结局为胜平负，如一字棋、象棋等，核心是寻找最优策略。4.5.2博弈树1.定义：博弈问题的状态空间图，节点为棋局状态，边为合法走步，我方为MAX方（求极大值），对方为MIN方（求极小值），与、或层交替出现。图5博弈树示意图2.核心概念：或节点（MAX节点）：我方走步，选择任一子节点即可通往胜利；与节点（MIN节点）：对方走步，需考虑所有子节点的干扰。4.5.3极大极小值搜索1.基本思想：从叶节点开始，向上倒推各节点的极大极小值，MAX节点取子节点最大值，MIN节点取子节点最小值，以此确定最优走步。2.流程：扩展节点至指定深度→计算叶节点静态估值→倒推内部节点倒推值→根据根节点倒推值选择最优走步。4.5.4α-β剪枝1.基本思想：生成博弈树与评估倒推值同时进行，通过α值（MAX节点下界）和β值（MIN节点上界）剪去无意义的子节点扩展，提高效率。2.剪枝规则：α剪枝：子节点β值≤父节点α值时，剪去该子节点及后续子节点；β剪枝：子节点α值≥父节点β值时，剪去该子节点及后续子节点。3.示例：通过α-β剪枝简化博弈树搜索过程，减少节点扩展数量。教学重点与难点重点：1.状态空间的表示及图搜索的基本流程；2.广度优先搜索与深度优先搜索的算法实现及应用；3.估价函数的设计及A算法、A*算法的求解过程；4.极大极小搜索与α-β剪枝的原理。难点：1.启发函数的合理性设计及对搜索效率的影响；2.A算法的最优性证明及实际应用；3.α-β剪枝的具体实现及剪枝时机判断；4.不同搜索策略的场景适配选择。教学步骤与时间分配1.搜索的基本概念（0.5学时）：经典搜索问题讲解及搜索策略分类；2.状态空间与图搜索（1学时）：状态空间表示及状态空间图搜索流程；3.盲目搜索策略（1学时）：广度优先+深度优先（含改进策略）的算法、示例及性质；4.启发式搜索策略（1学时）：估价函数+A算法+A*算法的原理与示例；5.博弈搜索（1学时）：博弈树+极大极小搜索+α-β剪枝的讲解与示例；6.总结与习题讲解（0.5学时）：知识点梳理+典型习题分析。7.实验教学（2学时）：盲目搜索和启发式搜索策略的实现和性能对比。教学手段电子教案PPT+板书+课堂演示+案例分析+实验实操教学方法1.线上：智慧课程平台提供PPT、视频、习题等拓展资料供学生预习和复习；2.线下：通过案例导入、分步讲解、例题演算、小组讨论等方式，结合可视化工具展示搜索过程，帮助学生理解抽象概念；3.采用“理论+实践”结合模式，通过经典问题求解强化对算法的掌握。思政教育讲解科技赋能与责任担当相关内容：AI搜索技术快速筛选抗病毒药物小分子，缩短研发周期，