大学人工智能导论《搜索策略》课堂讲授课件

人工智能导论人工智能导论：搜索策略状态空间·盲目搜索·启发式·A星算法课程人工智能导论讲授时间2026年课程导览01搜索问题是什么状态空间建模与问题形式化02盲目搜索无信息条件下的穷举策略03启发式搜索用评价函数引导方向04A星算法最优性原理与可采纳性05搜索策略的评估与展望算法比较与前沿方向搜索算法基础01搜索问题是什么把问题变成可搜索的空间从迷宫到地图导航，搜索无处不在什么是搜索问题搜索，就是在众多可能中找到通往目标的那条路生活处处是搜索地图导航：找最短路线游戏：找通关步骤下棋：推演下一步人工智能中的搜索智能体在状态空间中寻找动作序列搜索问题回答三件事我现在在哪我能做什么我要去哪里全课两大主线盲目搜索：没有线索启发式搜索：借助经验指引把问题变成状态空间“形式化建模：把模糊的现实问题转写为可计算的结构”状态对当前局面的完整描述示例：棋盘上所有棋子的位置动作从当前状态可以执行的操作状态转移执行某个动作之后到达的新状态初始状态问题开始时智能体所处的局面目标状态判定问题解决的条件，可以是一个状态或一组状态路径代价每走一步所付出的代价，可以相同也可以不同状态空间图与搜索树状态空间图看全局，搜索树看过程——同一张地图，两种展开方式状态空间图把所有状态和转移画成一张图节点是状态边是动作同一状态可被多条路径重复到达搜索树从初始状态出发以初始状态为根把走过的路径展开成一棵树同一状态记录为不同分支关键差别状态重复是搜索效率的大敌，后续算法会用闭表避免重复处理同一状态解、路径代价与最优解定义解与最优解，为算法评价标准埋下伏笔接下来分别用不带信息与带信息两种方式去搜索解从初始状态到目标状态的一条动作序列路径代价这条路径上每一步动作代价的累加最优解所有解当中路径代价最小的那一个任意一个解有的问题只要求找到任意一个解代价最小的解有的问题必须找到代价最小的解能否保证找到解能否保证最优耗费多少时间与空间VS搜索算法的通用框架各算法的差别只在开表排序规则与新节点处理方式，记住框架即掌握全部变体。几乎所有搜索算法都可以用

开表加闭表

来描述开开表存放已生成但尚未扩展的节点决定下一个该扩展谁闭闭表存放已经扩展过的节点防止重复走回头路通用循环从开表取出节点›判断是否目标›扩展后继›新节点放回开表搜索算法基础02盲目搜索没有线索时只能一步步试广度与深度，两种截然不同的探索节奏广度优先搜索：层层推进层层向外扩散，先扩展初始状态，再扩展全部后继，逐层推进特点与代价特点只要分支有限，找到的第一个解就是步数最少的解代价需保存整层节点，空间消耗随层数急剧上升开表机制与适用场景开表用队列管理，先进先出，先进入的节点先被扩展场景解较浅、状态空间不大的问题，如求迷宫的最少步数深度优先搜索：一路走到底总是优先扩展最新生成的节点，沿一条路一直往下走，开表用栈管理，后进先出核核心机制栈管理后进先出搜索方向沿一条路一直往下走优特点与优势空间占用小，只需保存当前路径上的节点险风险与适用场景主要风险可能扎进很深的死胡同，迟迟找不到解，甚至陷入无限深分支适用场景解数量较多、路径较深或状态空间极其庞大的问题广度与深度的取舍同样是盲目搜索，两种节奏各有代价广度优先搜索队列·逐层扩展深度优先搜索栈·沿路径深入广广度优先搜索开表结构队列完备性分支有限时完备最优性每步代价相同时最优空间占用大，保存整层适合场景解较浅深深度优先搜索开表结构栈完备性可能陷入无限深分支最优性不保证空间占用小，保存当前路径适合场景解较多、空间受限一致代价搜索：最便宜优先当每一步的代价并不相同时，层数最少并不等于总代价最小策一致代价搜索·要点解析思路开表按路径代价从小到大排序，每次都取出代价最小的节点进行扩展特点只要每一步的代价都为正，找到的第一个解就是代价最小的解关系如果每步代价都相等，一致代价搜索就退化为广度优先搜索局限仍然可能扩展大量无关节点，因为它对目标所在方向一无所知迭代加深：兼顾空间与最优反复进行深度优先搜索，每次都限定最大深度，深度限制从

1

逐步加大说明盲目搜索也能取两者之长，但它始终没有利用任何关于目标的信息因动机广度优先找得浅但耗费空间深度优先省空间却可能找不到解析特点与代价特点保留深度优先的小空间优势，又具备逐步达到较深解的能力代价浅层节点会被重复扩展，但重复量在可接受范围内搜索算法进阶03启发式搜索让经验为搜索指路用评价函数把搜索引向更有希望的方向启发函数：来自领域的线索盲目搜索的通病对四周平均探索没有方向感浪费大量力气启发式搜索的突破用启发函数h

表示从当前节点到目标的估计代价启发函数来自问题领域的知识不同的启发函数会显著影响搜索效率“就像有人告诉你离目的地还有多远，搜索自然就会朝更近的方向走”关键前提：估计值不能超过真实代价，这一点会在A星算法

部分严格讨论从通病到突破：启发函数让搜索有了方向感VS贪婪最佳优先搜索优点1项通常能很快找到解扩展节点数远少于盲目搜索“直觉：只盯着离目标近不近，完全不管已经走了多远”代价2项不保证最优可能被启发函数误导，先到达的路径并非代价最小可能走进死路看似有希望却被迫折返，反而浪费大量时间好的启发函数从哪里来把原问题的某些约束放宽，求出放宽后问题的最优代价，作为启发函数法核心方法松弛把原问题的某些约束放宽，求出放宽后问题的最优代价，作为启发函数规律放宽得越多，启发函数越容易计算，但估计越松、引导作用越弱原则在保证不高估真实代价的前提下，启发函数越接近真实值，搜索效率越高例一：错位数字个数允许数字自由移动到任意位置，统计已错位的数字个数例二：曼哈顿距离之和允许数字直接平移穿过障碍，计算各数字到目标位置的横向+纵向距离之和启发式搜索的陷阱贪婪策略并非万能，三个陷阱需警惕贪婪策略看似高效，却潜藏三个容易踩中的陷阱。需要同时考虑「已经走了多远」和「还差多远」——这正是下一章

A星算法要解决的核心问题。陷阱一把估计当成真相h只是猜测，并非真实代价。猜错方向就会被带偏。陷阱二只顾眼前贪婪策略只看h。忽视了已付出的路径代价。陷阱三启发函数设计不当性能下滑。甚至不如盲目搜索。启发式搜索04A星算法既找得到，又找得最优估价函数f等于g加h的精妙平衡A星算法：同时看两头每次扩展

f最小的节点；与贪婪搜索的区别：多了

g

这一项，不再只看离目标近不近，而是看整体划不划算。核心公式：f=g+hg：实际路径代价从初始状态到当前节点已经发生、确定无疑h：估计代价从当前节点到目标尚未发生，由启发函数给出f：总代价估计经过当前节点到达目标开表按

f从小到大排序一个A星搜索的实例同一个状态若被以更低代价重新到达，需要更新它的

g值地图上从起点走向终点，每段道路的代价标注在相应边上第1步起点步骤一起点放入开表，计算它的

f值第2步扩展步骤二取出

f最小的节点扩展，生成后继并分别计算

g与h第3步排序步骤三后继节点放入开表，按

f重新排序，继续取出最小者第4步成功步骤四取出节点为目标时搜索成功，沿父节点指针回溯得最优路径可采纳性：不高估才最优不高估，才最优定理只要启发函数可采纳，A星算法一定能够找到最优解。反例如果h高估了某条路径，算法可能过早放弃它，从而错过真正的最优解。可采纳性是A星最优性的第一块基石，也是设计启发函数的硬约束。可采纳性是A星最优性的第一块基石，也是设计启发函数的硬约束。定义对任意节点，启发函数的估计值都不大于从该节点到目标的真实最小代价。直观含义估计永远不夸大剩余难度。h

始终是乐观的。一致性：更强的条件记忆点：可采纳性管

最优不最优，一致性管

要不要反复改定义启发函数在节点

n

处的估计值，不大于从n到后继的代价

加上

后继处的估计值直观含义启发函数的估计不会突然跳变沿着边走时变化是平缓的关关系蕴含一致性蕴含可采纳性，但反过来不成立效好处一次一致时每个节点只需处理一次高效无需反复更新路径代价，实现更高效A星的优化与现实应用A*是启发式搜索中兼顾最优与效率的经典代表从理论走向工程加权A星给

h

乘一个大于1的系数牺牲最优性换取速度迭代加深A星结合深度优先思想显著降低内存占用更紧的启发函数取多个可采纳启发式中的最大值地图导航的最短路径规划游戏角色寻路机器人运动规划物流配送路线优化拼图类益智游戏的自动求解搜索算法进阶05搜索策略的评估与展望没有最好，只有最合适从完备性到最优性，用统一标准衡量算法评估搜索算法的四个维度评价要点：时间与空间消耗通常以节点数计量；实践提醒：真正选算法时，空间往往比时间更早成为限制完备性问题存在解时，算法是否一定能找到有解必达最优性找到的解是否一定是代价最小的解代价最小时间复杂度扩展节点数随问题规模如何增长节点数增长空间复杂度需保存的节点数，往往是实际中的真正瓶颈真正瓶颈主流算法横向对比没有最好的算法，只有最合适的选择算法完备性最优性空间占用广度优先是每步代价相同时是大深度优先否否小一致代价是是大贪婪最佳优先否否中A星是可采纳时是中从搜索到博弈：对抗搜索现实中的搜索往往不止一个决策者，对手会对你的选择做出反应极小极大算法假设对手总是选择对我最不利的一步评估据此评估局面好坏对抗评估剪枝思想判断某些分支显然不影响最终结果动作提前放弃，减少搜索量提前放弃局限前提博弈树既深又宽时结果完整搜索在现实中不可行现实不可行搜索策略的前沿方向学习建议：先吃透盲目搜索与启发式搜索的对比，再理解A星最优性的证明思路方向一启发函数学习在大规模状态空间下，自动学习高质量的启发函数。方向二搜索+强化学习把搜索与强化学习结合，让智能体在试错中逐渐学会策略。方向三实时重规划面向真实机器人与自动驾驶的实时搜索与动态重新规划。方向四多智能体协同多智能体之间的协同搜索与分布式决策。全