人工智能的搜索算法PPT讲稿.ppt

人工智能的搜索算法第1页，共16页，编辑于2022年，星期四p在智能过程中，搜索是不可避免的 Nilssonp一个物理符号系统解决任何智能问题的充分和必要条件 Newell第2页，共16页，编辑于2022年，星期四搜索法简介p搜索法是人工智能中问题求解的基本方法p可大致分为有信息搜索和无信息搜索p约束满足问题和博弈问题的求解均可表述为搜索过程pAgent的学习过程亦可表述为搜索过程p搜索法的本质是在状态空间中从问题的初始状态搜索到通向目标状态的路径第3页，共16页，编辑于2022年，星期四搜索法简介p当前的智能计算方法本质上也是搜索方法，如神经网络、遗传算法、蚁群算法等p搜索法的设计主要考虑解路径的耗散值以及搜索过程中的耗散值耗费最低化第4页，共16页，编辑于2022年，星期四算法性能的评价p评价算法性能的四个方面：p完备性：有解时能保证找到解（可判定问题）p最优性：能否找到最优解p时间复杂度p空间复杂度第5页，共16页，编辑于2022年，星期四搜索算法的评价p搜索法要处理的是状态空间图p在人工智能领域，状态空间图是由初始状态和后继函数隐含表示的（与通常的计算机图搜索算法不同）p搜索算法可从以下三个方面评价：pb:分支因子pd:最浅目标节点的深度pm:状态空间中最大路径长度（考虑耗散）第6页，共16页，编辑于2022年，星期四问题的形式化p搜索法首先要对问题进行形式化描述p问题通常可形式化定义为下述四个部分pAgent所处的初始状态pAgent可采纳的行动：后继函数p目标测试：确定当前状态是否是目标状态p路径耗散函数：为每条路径分配量化的耗散值第7页，共16页，编辑于2022年，星期四举例：八数码问题第8页，共16页，编辑于2022年，星期四盲目搜索p广度优先搜索：p在下一层节点被扩展之前保证本层节点都被扩展p通常用FIFO队列实现p能保证找到最浅的目标节点（不一定是最优的）p在单步耗散相同时是最优算法p空间复杂度大,p目标节点较深时，时间复杂度亦很大第9页，共16页，编辑于2022年，星期四盲目搜索p代价一致搜索:p与广度优先搜索类似，但首先扩展耗费最低的节点p须保证算法的完备性（为每一步设定最小耗散）p最坏时间复杂度为第10页，共16页，编辑于2022年，星期四深度优先搜索p首先扩展搜索树中最深最边缘的未扩展节点p通常通过LIFO的栈实现p空间复杂度低，p对于状态复杂的问题，可变形为回溯搜索，空间复杂度降为p最坏时间复杂度p通常应用中变形为深度有限搜索（需要知识的支持）,通常lm第11页，共16页，编辑于2022年，星期四双向搜索p思想基础：p从初始状态和目标状态同时开始相向搜索，形成两棵搜索树p若某一待扩展节点出现在另一棵搜索树中，则找到解p后向搜索较难实现，无固定方法第12页，共16页，编辑于2022年，星期四启发式搜索p使用启发信息，对待扩展节点到目标节点的距离给出估计p定义：pf(n):对经过节点n的最低耗散解的估计值pg(n):初始节点到节点n的路径耗散ph(n):从节点n到目标节点的耗散估计值p每次首先扩展队列中具有最低f(n)的节点第13页，共16页，编辑于2022年，星期四A*算法pA*算法的要求：p启发函数满足可采纳约束：p其中 是节点n到目标节点的最低耗散p一致性约束：pA*算法是可采纳算法：当解存在时能保证找到最优解p当满足 时，A*算法效率最高第14页，共16页，编辑于2022年，星期四A*算法的复杂性估计p若h(n)满足：则有：p故A*并不能保证克服指数爆炸p非指数级增长的条件：第15页，共16页，编辑于2022年，星期四禁忌搜索(TS)算法pGlover于1986年提出p特点：p具有记忆功能，可有效避免局部最优p适用于多参数优化问题第16页，共16页，编辑于2022年，星期四