人工智能的搜索算法.ppt

人工智能的搜索算法
【教师试讲】【课堂演讲】【教学课件】【说课比赛】
人工智能的搜索算法
【教师试讲】【课堂演讲】【教学课件】【说课比赛】
举例：八数码问题
盲目搜索
广度优先搜索：
在下一层节点被扩展之前保证本层节点都被扩展
通常用FIFO队列实现
能保证找到最浅的目标节点（不一定是最优的）
在单步耗散相同时是最优算法
空间复杂度大,
目标节点较深时，时间复杂度亦很大
盲目搜索
代价一致搜索:
与广度优先搜索类似，但首先扩展耗费最低的节点
须保证算法的完备性（为每一步设定最小耗散）
最坏时间复杂度为
深度优先搜索
首先扩展搜索树中最深最边缘的未扩展节点
通常通过LIFO的栈实现
空间复杂度低，
对于状态复杂的问题，可变形为回溯搜索，空间复杂度降为
最坏时间复杂度
通常应用中变形为深度有限搜索（需要知识的支持） , 通常l<m
双向搜索
思想基础：
从初始状态和目标状态同时开始相向搜索，形成两棵搜索树
若某一待扩展节点出现在另一棵搜索树中，则找到解
后向搜索较难实现，无固定方法
启发式搜索
使用启发信息，对待扩展节点到目标节点的距离给出估计
定义：
f(n):对经过节点n的最低耗散解的估计值
g(n):初始节点到节点n的路径耗散
h(n):从节点n到目标节点的耗散估计值
每次首先扩展队列中具有最低f(n)的节点
A*算法
A*算法的要求：
启发函数满足可采纳约束：
其中 是节点n到目标节点的最低耗散
一致性约束：
A*算法是可采纳算法：当解存在时能保证找到最优解
当满足 时，A*算法效率最高
A*算法的复杂性估计
若h(n)满足：

则有：
故A*并不能保证克服指数爆炸
非指数级增长的条件：
演示结束，谢谢！