人工智能的搜索算法课件

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