人工智能通识教程课件 第3章 搜索技术

搜索技术3自强不息厚德载物TsinghuaUniversityofChinaContents.目录3.1搜索技术概述3.2图搜索策略3.3盲目搜索方法3.4启发式搜索3.5博弈搜索3.6群智能3.7搜索应用案例课程导入当我们面对一个迷宫般复杂的问题，该如何让机器像人类一样‘摸索-反馈-优化’，并用最少成本找到答案？机器人怎样在复杂地形中自动规划路径？自动驾驶汽车如何预测障碍物出现的可能性？围棋AI如何判断下一步落子才是制胜关键？这些问题的共同点：没有固定规则，答案隐藏在庞大的可能性中。搜索技术：让计算机像人一样“试错–判断–优化”，从状态空间中逐步接近目标。本章学习目标、内容学习目标理解搜索算法如何解决复杂问题能实现经典搜索算法代码掌握搜索策略的适用场景探索“人类如何试错”，计算机如何更快做到？学习内容搜索问题的状态空间表示与图结构建模盲目搜索（BFS、DFS、UCS）与启发式搜索（贪心、A*）的原理与效率对比博弈搜索如何做出最优对策（Minimax、α–β剪枝）群体智能算法（蚁群、粒子群、遗传算法等）的自然启发设计理念3.1搜索技术概述搜索的基本概念什么是搜索？当人类面对没有固定解法的难题，会通过尝试、反馈、再尝试的方式寻找解决方案搜索技术就是让计算机模仿这种“试错+优化”的智能过程用于解决：路径规划、对弈决策、预测分析等复杂问题🤔搜索问题的三大核心组成状态（State）算符（Operator）状态空间（StateSpace）3.1搜索技术概述状态（State）问题某一时刻的完整描述（例如：棋局布局、机器人位置）通常表示为变量组合：Sk={Sk0,Sk1,…}算符（Operator）将一个状态变为另一个状态的“操作规则”如魔方旋转、迷宫中移动一步等状态空间（StateSpace）全部可能状态+状态之间的连接关系定义为三元组：S（初始状态集）、F（算符集）、G（目标状态集）3.1搜索技术概述状态空间法求解问题的基本过程什么是状态空间法？一种通用的搜索问题建模与求解方法，通过“状态+算符”组合，模拟从初始状态到目标状态的逐步演化过程。基本求解流程初始化状态扩展目标检测🔄选择起始状态或目标状态设为“当前状态”进行搜索起点扫描算符集，作用于当前状态得到新的状态，并记录“来自哪个父节点”检查是否到达目标状态到达→沿父节点指针回溯解路径否则→将新状态设为当前状态，继续搜索”3.1搜索技术概述状态空间法求解实例：二阶梵塔问题背景故事：源自印度神庙的数学传说起源：梵塔（TowerofHanoi）传说中，僧侣需将64个金盘从一根柱子搬至另一根柱子规则：

每次只能移动一个盘

不能将大盘放在小盘上

借助中间柱作为辅助若用1秒/次移动金盘，需5800亿年才能完成全部移动！🕰️3.1搜索技术概述状态空间法求解实例：二阶梵塔问题简化模型：二阶梵塔问题使用2个盘子A（小）和B（大），分别标号为A<B三根柱子：编号1、2、3目标：将两个盘从柱子1→柱子3规则依然不变：一次只动一个盘，大盘不能压小盘🧩3.1搜索技术概述状态空间法建模步骤：二阶梵塔问题🧠第一步：状态表示Sk用二元组(SkA,SkB)表示状态，其中SkA：小盘A所在柱编号SkB：大盘B所在柱编号举例：Sk=(2,3)表示小盘A在柱2，大盘B在柱3第二步：算符设计移动盘A：Aij

表示把A从柱i移到柱j，共6种

移动盘B：Bij

表示把B从柱i移到柱j，共6种共计12个操作符，每次移动一步改变状态3.1搜索技术概述状态空间法建模步骤：二阶梵塔问题🧠第三步：状态空间图建模节点：9个合法状态Sk边：12个算符作用下的状态转移起点：S0=(1,1)终点：S8=(3,3)每一条从S0→S8

的路径都是一个解3.2图搜索策略图搜索：一种在状态图中寻找从起始状态到目标状态路径的方法。本质上就是在“状态构成的图”中找路，从一个节点（状态）出发，寻找通往目标节点的路径。类型描述类比1️⃣正向搜索从起点向目标搜索从家出发去学校2️⃣逆向搜索从目标向起点反推从学校出发找回家的路3️⃣双向搜索起点与目标各走一半，碰头即完成家和学校分别出发在途中相遇图搜索的三种策略：3.2图搜索策略搜索过程中的数据结构图搜索中最重要的“两张表”数据结构类比功能Open表（开放表）待办清单存放“还没探索”的节点（状态）Closed表（封闭表）已完成记录存放“已探索完”的节点，防止重复Open表Closed表3.2图搜索策略搜索过程中的数据结构图搜索的通用性算法：(1)把初始节点S0放入Open表,设g(S0)=0,建立一个Closed表，置为空；(2)检查Open表是否为空表，若为空，则问题无解，失败退出；(3)把Open表的第一个节点取出放入Closed表，并记该节点为n；(4)考察节点n是否为目标节点，若是则得到问题的解成功退出；(5)若节点n不可扩展，则转第（2）步；(6)下一步为扩展节点，依据不同的搜索策略（深度/广度优先搜索等）进行扩展。3.2图搜索策略搜索策略的分类【一】盲目搜索(BlindSearch)概念：不依赖问题中的任何信息，根据预先设定的规则执行搜索。关键算法：宽度优先搜索(BFS)：按照节点层级进行扩展，保证最短路径，但占用空间大。深度优先搜索(DFS)：先尽可能深入，有效用于短解路径，但易陷入无限循环。等代价搜索(UCS)：按照路径总代价扩展节点，选择路径费用最小的节点。3.2图搜索策略搜索策略的分类【二】启发式搜索(Informed/HeuristicSearch)概念：利用问题本身的启发信息，展开更有指向性的搜索。关键算法：贪心搜索(GreedyBest-FirstSearch)：优先扩展启发值h(n)最小的节点，搜索速度快，但容易失去全局最优解。A算法*：结合实际费用g(n)和启发值h(n)，计算f(n)=g(n)+h(n)，能够找到全局最优解，应用广泛。3.2图搜索策略搜索策略的分类【三】博弈搜索(AdversarialSearch)概念：多智能体对抗下的搜索，常规于棋筹类游戏中。关键算法：极大极小算法(Minimax)：尽量选择对己最优的动作，而对手选最坏的动作。α-β剪枝(Alpha-BetaPruning)：在不改变结果前提下，删除无效分支，大大降低搜索维度和计算量。3.2图搜索策略搜索策略的分类【四】群智能优化(SwarmIntelligenceOptimization)

概念：抽象自然界群体合作行为，模拟性形成高效解答路径。关键算法：遗传算法(GA)：模拟生物进化过程，通过选择、交叉、变异进化解答。蚁群算法(ACO)：模拟蚁蚁的采食行为，利用信息素寻找最优路径。粒子群优化(PSO)：模拟鸟群解答搜索，根据自身和群体最优解调整方向。人工蜂群(ABC)：模拟蜜蜂采蜜行为，分工合作进行搜索与优化。鲸鱼优化(WOA)：模拟座头鲸捕食行为，应用于应急与多目标优化场景。3.2图搜索策略搜索技术的应用领域应用领域搜索技术典型案例路径规划BFS、DFS、A*算法、Dijkstra机器人导航、自动驾驶、物流调度博弈AI极大极小、α-β剪枝国际象棋AI、五子棋AI、围棋AI约束满足问题（CSP）回溯搜索、启发式搜索八皇后问题、数独求解组合优化遗传算法、蚁群算法、模拟退火旅行商问题（TSP）、生产调度机器学习参数优化粒子群优化、遗传算法神经网络超参数调优3.3盲目搜索方法不使用任何问题特定信息，仅依靠预设规则遍历状态空间，又称无信息搜索（UninformedSearch）。核心思想

通过优化Open表中节点的排序，提高搜索效率。

若每次扩展的节点都在最终解路径上，可显著减少搜索代价。定义算法描述优点缺点BFS（宽度优先）按层扩展节点一定找到最短路径占用空间大DFS（深度优先）优先向下探索占用空间少易陷入死循环UCS（等代价）按总代价排序扩展可处理路径带权问题效率依赖代价设计3.3盲目搜索方法宽度优先搜索🔍基本思想使用队列（FIFO）结构管理节点（Open表）每次从队首取出节点，扩展其所有子节点，并将子节点加入队尾按“层次”方式进行搜索，优先拓展离起点近的节点🧠算法特点逐层搜索：从起点出发，先搜索所有一步可达节点，再搜索两步……保证最短路径：在无权图中，一定找到最短路径空间开销大：需记录所有已访问节点和其邻居节点3.3盲目搜索方法宽度优先搜索(1)初始节点S0

入队(2)若队列为空→失败(3)出队队首节点X，加入Closed表(4)若X是目标节点→成功(5)若X不可扩展→重复第2步(6)扩展X的所有子节点→入队尾📋算法步骤无向简单图3.3盲目搜索方法宽度优先搜索fromcollectionsimportdequedefbfs_path(graph,start,goal):queue=deque([(start,[start])])visited=set()whilequeue:node,path=queue.popleft()ifnode==goal:returnpathifnodenotinvisited:visited.add(node)forneighboringraph[node]:ifneighbornotinvisited:queue.append((neighbor,path+[neighbor]))bfs_result=bfs_path(graph,'A','F')print("BFS路径:",bfs_result)#输出：['A','C','F']Python实现代码（简化）3.3盲目搜索方法深度优先搜索🔍基本思想使用栈结构（LIFO）管理节点（Open表）每次扩展当前节点后，子节点插入队首优先“纵深”搜索，遇死胡同再回溯🧠算法特点先深入后回溯：沿当前路径走到不能再走为止不保证最短路径：搜索结果可能不是最优内存开销较小：仅保存当前路径，但存在栈溢出风险3.3盲目搜索方法深度优先搜索(1)初始节点S0

入栈(2)若栈为空→搜索失败(3)出栈节点X，放入Closed表(4)若X为目标→搜索成功(5)若X不可扩展→重复第2步(6)将子节点插入栈顶→重复第2步📋算法步骤3.3盲目搜索方法深度优先搜索defdfs_path(graph,start,goal):visited,path=set(),[]defdfs(node):ifnode==goal:returnTrueifnodeinvisited:returnFalsevisited.add(node)path.append(node)forneighboringraph[node]:ifdfs(neighbor):returnTruepath.pop();returnFalsereturnpath+[goal]ifdfs(start)elseNonedfs_result=dfs_path(graph,'A','F')print("DFS路径:",dfs_result)#输出：['A','B','E','F']Python实现代码（简化）3.3盲目搜索方法等代价搜索（UCS）🧭基本思想适用于带权图寻找从起点到终点总代价最低的路径每次扩展总代价最小的节点是BFS的推广：若边权都为1，UCS≈BFS📌核心机制Open表=优先队列（按总代价排序）每轮选出总代价最小的节点进行扩展若发现更优路径，更新邻居节点信息并重排队列当目标节点出现在Open表首位→搜索终止3.3盲目搜索方法等代价搜索（UCS）(1)起点入Open表，代价为0(2)Open表为空→搜索失败(3)取总代价最小节点X：

-若X是目标→成功并回溯路径

-否则扩展X的邻居Y(4)对每个邻居Y：

-若Y不在Open/Closed→加入Open，记录代价

-若已在Open且当前代价更小→更新

-若在Closed且代价更小→更新并重入Open📋算法步骤3.3盲目搜索方法盲目搜索方法比较搜索方法数据结构适用场景优势劣势BFS队列（FIFO）无权图，寻找最短路径保证最短路径高内存消耗DFS栈（LIFO）约束满足问题、路径搜索占用内存较少可能非最优路径UCS优先队列（最小堆）带权图，寻找最短路径适用于加权图，保证最优解计算代价较高3.4启发式搜索启发式搜索是一类利用问题领域的启发式信息（HeuristicInformation）来引导搜索方向、提升搜索效率的算法。其核心是通过评估函数选择最有希望通往目标的节点进行扩展，从而减少不必要的状态遍历。核心思想构造启发式函数ℎ(𝑛)：估算当前节点𝑛到目标节点的代价优先扩展估价较小的节点，跳过“低潜力”路径启发式搜索兼具效率与准确性定义⚙️优势：避免盲目遍历，显著降低时间和空间复杂度能处理更大规模的问题状态空间常用于路径规划、博弈、机器学习等领域3.4启发式搜索启发性信息和评估函数✅启发式搜索的核心目标：利用领域知识，优先扩展“最可能”通向目标的节点，从而提升搜索效率。🧠启发性信息的三种用途：选择扩展节点：判断下一步应扩展哪个节点，避免盲目搜索。选择生成节点：控制扩展时生成哪些子节点，节省资源。选择删除节点：剪枝无效节点，降低空间复杂度。3.4启发式搜索启发性信息和评估函数📐评估函数f(n)=g(n)+h(n)g(n)：从起始节点到当前节点n的真实代价h(n)：从节点n到目标节点的代价估计（启发函数）f(n)：总代价估计，用于排序待扩展节点启发策略h(n)计算方法不在位数码个数法h(n)=与目标棋局位置不同的数字个数（如：3）曼哈顿距离法h(n)=所有数码移动到目标位置的最短路径之和（如：4）🎲示例：八数码问题中的启发函数h(n)3.4启发式搜索有序搜索✅核心思想：

通过评估函数f(n)=g(n)+h(n)，对所有候选节点进行排序，

优先扩展f值最小的节点，从而有计划地靠近目标状态。🔧评估函数构成：g(n)：从起点到当前节点的实际代价h(n)：当前节点到目标节点的估计代价f(n)：总评估值，决定扩展优先级

→f(n)=g(n)+h(n)3.4启发式搜索有序搜索🎮应用示例：八数码问题g(x)：当前节点在搜索树中的深度h(x)：每个错位数字移动到目标位置所需步数的总和f(x)：当前局面的整体评估优劣指标3.4启发式搜索A*算法✅定义与应用：A*是一种启发式搜索算法，广泛用于

路径规划、游戏寻路、机器人导航等实际问题中。目标：在图或网格中高效找到从起点到目标的最优路径。🧠核心机制：

评估函数：f(n)=g(n)+h(n)g(n)：起点到当前节点的实际代价h(n)：当前节点到目标的启发式估计代价始终扩展f值最小的节点，集中探索高潜力路径。3.4启发式搜索A*算法🧪示例：10×10网格地图机器人寻路起点：(0,0)，目标：(9,9)0表示可通行，1表示障碍使用曼哈顿距离作为启发函数h(n)3.5博弈搜索🎯博弈搜索的定义博弈搜索是AI在对抗性环境中决策的核心算法常用于象棋、围棋、五子棋、国际跳棋、卡牌游戏等核心目标：为AI制定最优对策🔑常见博弈搜索算法极小极大算法（Minimax）α-β剪枝算法（Alpha-BetaPruning）📊博弈树（GameTree）特点节点表示局面，边表示走法“或”节点：轮到己方走，可选多种走法之一“与”节点：对手走棋，AI需应对所有情况与/或节点层层交替出现，构成决策路径终局节点：胜→可解，败→不可解3.5博弈搜索极小极大搜索（MinimaxAlgorithm）🔍基本原理适用于零和博弈（一方赢即另一方输）AI=Max玩家：最大化得分对手=Min玩家：最小化AI得分通过递归遍历博弈树，评估每个可行方案的最坏结果3.5博弈搜索极小极大搜索（MinimaxAlgorithm）📐核心步骤1️⃣构建博弈树：节点为局面，边为走法

2️⃣定义评估函数：叶节点得分（胜=+1，负=−1，平=0）

3️⃣叶节点评估：得到静态估值

4️⃣倒推得分：

  -Max节点：取子节点中最大值

  -Min节点：取子节点中最小值

5️⃣选出最优行动：根节点中得分最高的子节点对应的走法3.5博弈搜索极小极大搜索（MinimaxAlgorithm）♟️示例：井字棋起始状态：空棋盘，共9个落子选择限定搜索深度为3层Minimax计算各落子的最终得分选择评估值最大的落子作为首选3.5博弈搜索α-β剪枝（Alpha-BetaPruning）📌定义与作用α-β剪枝是极小极大搜索的优化算法通过剪去不会影响最终决策的冗余节点显著提升搜索效率，减少计算开销🧠核心思想在搜索过程中维护两个值：α：当前极大节点能达到的最大下限β：当前极小节点能接受的最小上限若发现某一子节点无法改善结果——立即剪枝，不再扩展3.5博弈搜索α-β剪枝（Alpha-BetaPruning）节点类型剪枝类型条件含义极大节点（Max）β剪枝α≥β对手不会选，剪枝极小节点（Min）α剪枝β≤α我方不会选，剪枝✂️剪枝规则🔁算法流程简图初始化：α=-∞，β=+∞自顶向下扩展，更新α或β满足剪枝条件时，停止继续搜索该分支保留必要路径，跳过无效路径3.6群智能📌定义群智能是一类模拟自然群体行为的优化方法启发自蚂蚁觅食、鸟群飞行、鱼群游动等现象广泛用于路径规划、机器学习、控制与数据挖掘等领域🌟关键特性分布式计算：多智能体协同优化，无需中央控制器自组织性：个体通过局部规则，产生全局有序行为鲁棒性强：部分个体失败不影响整体优化能力3.6群智能算法简称中文名称启发来源GA遗传算法生物进化ACO蚁群算法蚂蚁觅食PSO粒子群优化鸟群飞行ABC人工蜂群算法蜜蜂采蜜WOA鲸鱼优化算法鲸鱼围捕猎物🧠常见群智能算法📈应用领域最优路径规划、机器学习模型调参、智能控制系统设计、大数据特征选择与挖掘3.6群智能遗传算法📌定义遗传算法是一种模拟自然选择与遗传机制的智能优化方法通过选择、交叉、变异等操作，逐代进化，逼近最优解🔁基本流程初始化：随机生成种群（染色体）适应度评估：计算个体适应度选择：保留适应度高的个体（如轮盘赌）交叉：个体基因组合产生新个体变异：随机改变基因增强多样性迭代进化：直到满足终止条件🚀应用领域组合优化：TSP、路径规划机器学习：超参数调优、特征选择工业工程：生产调度、资源分配优化3.6群智能蚁群算法📌核心思想模拟蚂蚁觅食：路径上释放信息素信息素浓度越高→表示路径越短，被选中概率越大多次迭代后，短路径上的信息素积累最多→得到最优解🔁基本流程蚂蚁初始化：每只蚂蚁从起点出发路径选择：依据信息素浓度+启发信息（如距离）信息素更新：路径越短，释放越多信息素信息素挥发：避免陷入局部最优迭代优化：逐步收敛至最优路径🚀应用领域TSP问题：旅行商路径优化路径规划：机器人导航、物流调度组合优化：资源分配、排课问题等3.6群智能粒子群优化算法📌基本原理模拟鸟群觅食行为每个解为一个粒子，具有位置与速度粒子根据个体最优经验和全局最优经验动态调整位置实现全局搜索与局部优化的平衡🔁算法流程初始化粒子位置与速度适应度计算（如：f(x,y)=x²+y²）更新速度与位置

 速度更新：v=ω·v+c₁·r₁·(p_best-x)+c₂·r₂·(g_best-x)迭代优化直到收敛🚀应用场景神经网络参数优化多变量函数极值求解工程调度与复杂系统建模3.6群智能人工蜂群算法🐝算法灵感模拟蜜蜂觅食行为蜜蜂虽个体行为简单，但群体可高效采蜜并适应环境由Karaboga于2005年提出，用于解决函数优化问题🔧角色划分引领蜂（EmployedBees）：与一个食物