AI_3-搜索技术.ppt

第三章搜索技术
教学内容:    1、搜索的概念及种类
    2、盲目搜索策略    3、启发式搜索策略
第三章搜索技术
教学重点:宽度优先搜索、深度优先搜索及代价树的搜索算法,最佳优先搜索算法。
教学难点:利用各种搜索算法解决实际问题,尤其是估价函数的选取。
第三章搜索技术
上一章我们学习了知识的表示,接下来要研究的是实现问题求解的过程,采用的基本方法包括搜索和推理。
本章介绍搜索技术,将讨论问题求解的搜索原理及常用的搜索技术。
搜索的概念及种类
搜索的概念
根据问题的实际情况,按照一定的策略和规则,从知识库中寻找可利用的知识,从而构造出一条使问题获得解决的最优的推理路线的过程称为搜索。
搜索包含两层含义,一层含义是从问题的初始状态到问题最终答案的一条推理路线;另一层含义是找到的这条路线是时间和空间复杂度最小的求解路线。
搜索的概念及种类
搜索的种类
搜索分为盲目搜索和启发式搜索。
盲目搜索又叫做无信息搜索,一般只适用于求解比较简单的问题。我们将学习的宽度优先搜索和深度优先搜索,属于盲目搜索方法。
把利用启发信息的搜索方法叫做启发式搜索。这种搜索技术一般需要某些有关具体问题领域的特性的,与具体问题求解过程有关的,并可指导搜索过程朝着最有希望方向前进的控制信息,把此种信息叫做启发信息。
盲目搜索策略
图搜索策略
可把图搜索策略看成一种在图中寻找路径的方法。我们已经介绍过有关图的表示方法。
图中的节点对应于状态,而连线对应于操作符。
盲目搜索策略
在介绍图搜索策略之前,让我们来看一个例子。例:从某张姓家族的四代中找张A的后代且其寿命为X的人。 张A:寿命47,有儿子张B1、张B3、张B2 张B1:寿命77,有儿子张C1、张C2 张B3:寿命52,有儿子张D1 张B2:寿命65,有儿子张E1、张E2 张F1:寿命32 张G1:寿命96 张C2:寿命87,有儿子张F1 张D1:寿命77,没有儿子 张E1:寿命57,有儿子张G1
盲目搜索策略
张E2:寿命92,有儿子张H1  张C1:寿命27,没有儿子 张H1:寿命51若X=57,下面讨论一种可通用的图搜索策略求解此问题。 如果是一个N代的家族表中找其寿命为X的人,我们最可能用的手工方法是从家族表的开始往下,本例中还要求所找的人是某人的后代,就比较复杂了。如果用图来表示,就很容易了。图中把姓氏省去,每个成员的后代按例子中给出名字的先后顺序。图示为:
盲目搜索策略
图 用图表示方法的家族表
盲目搜索策略
图搜索算法中的几个重要名词
1)已扩展节点和未扩展节点:所谓扩展就是用适合的算符对某个节点进行操作生成一组后继节点,扩展过程实际就是求后继节点的过程;所以,对状态空间图的某个节点,如果求了它的后继节点,则此节点为已扩展的节点;而尚未求出它的后继节点的节点称为未扩展节点。未扩展节点存入OPEN表中,已扩展节点存入CLOSED表中。