人工智能的搜索算法.ppt

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

则有：
故A*并不能保证克服指数爆炸
非指数级增长的条件：
禁忌搜索(TS)算法
Glover于1986年提出
特点：
具有记忆功能，可有效避免局部最优
适用于多参数优化问题