人工智能的搜索算法.ppt

第一页，共十六页，2022年，8月28日 在智能过程中，搜索是不可避免的 ———— Nilsson 一个物理符号系统解决任何智能问题的充分和必要条件 ———— Newell 第二页，共十六页，2022年，8月28日 搜索法简介 搜索法是人工智能中问题求解的基本方法 可大致分为有信息搜索和无信息搜索 约束满足问题和博弈问题的求解均可表述为搜索过程 Agent的学习过程亦可表述为搜索过程 搜索法的本质是在状态空间中从问题的初始状态搜索到通向目标状态的路径 第三页，共十六页，2022年，8月28日 搜索法简介 当前的智能计算方法本质上也是搜索方法，如神经网络、遗传算法、蚁群算法等 搜索法的设计主要考虑解路径的耗散值以及搜索过程中的耗散值——耗费最低化 第四页，共十六页，2022年，8月28日 算法性能的评价 评价算法性能的四个方面： 完备性：有解时能保证找到解（可判定问题） 最优性：能否找到最优解 时间复杂度 空间复杂度 第五页，共十六页，2022年，8月28日 搜索算法的评价 搜索法要处理的是状态空间图 在人工智能领域，状态空间图是由初始状态和后继函数隐含表示的（与通常的计算机图搜索算法不同） 搜索算法可从以下三个方面评价： b:分支因子 d:最浅目标节点的深度 m:状态空间中最大路径长度（考虑耗散） 第六页，共十六页，2022年，8月28日 问题的形式化 搜索法首先要对问题进行形式化描述 问题通常可形式化定义为下述四个部分 Agent所处的初始状态 Agent可采纳的行动：后继函数 目标测试：确定当前状态是否是目标状态 路径耗散函数：为每条路径分配量化的耗散值 第七页，共十六页，2022年，8月28日 举例：八数码问题 第八页，共十六页，2022年，8月28日 盲目搜索 广度优先搜索： 在下一层节点被扩展之前保证本层节点都被扩展 通常用FIFO队列实现 能保证找到最浅的目标节点（不一定是最优的） 在单步耗散相同时是最优算法 空间复杂度大, 目标节点较深时，时间复杂度亦很大 第九页，共十六页，2022年，8月28日 盲目搜索 代价一致搜索: 与广度优先搜索类似，但首先扩展耗费最低的节点 须保证算法的完备性（为每一步设定最小耗散） 最坏时间复杂度为 第十页，共十六页，2022年，8月28日 深度优先搜索 首先扩展搜索树中最深最边缘的未扩展节点 通常通过LIFO的栈实现 空间复杂度低， 对于状态复杂的问题，可变形为回溯搜索，空间复杂度降为 最坏时间复杂度 通常应用中变形为深度有限搜索（需要知识的支持） , 通常lm 第十一页，共十六页，2022年，8月28日 双向搜索 思想基础： 从初始状态和目标状态同时开始相向搜索，形成两棵搜索树 若某一待扩展节点出现在另一棵搜索树中，则找到解 后向搜索较难实现，无固定方法 第十二页，共十六页，2022年，8月28日