人工智能第三章_搜索策略-1.ppt

2017/11/18
1
第3章搜索策略
问题求解系统划分为两大类
知识贫乏系统
依靠搜索技术解决问题
知识贫乏、缺乏针对性
效率低
知识丰富系统
依靠推理技术解决问题
基于丰富知识的推理技术,直截了当
效率高
2017/11/18
2
第3章搜索策略
两大类搜索技术:
1、一般图搜索、启发式搜索
2、基于问题归约的与或图搜索
两种典型的推理技术:
1、基于归结的演绎推理
归结反演
2、基于规则的演绎推理
正向演绎推理
逆向演绎推理
2017/11/18
3
引言
对于给定的问题,智能系统的行为一般是找到能够达到所希望目标的动作序列,并使其所付出的代价最小、性能最好。
基于给定的问题,问题求解的第一步是目标的表示。
搜索就是找到智能系统的动作序列的过程。
2017/11/18
4
搜索算法的输入是给定的问题,输出时表示为动作序列的方案。
一旦有了方案,就可以执行该方案所给出的动作了。(执行阶段)
因此,求解问题包括:
目标表示
搜索
执行
2017/11/18
5
(1)初始状态集合:定义了初始的环境。
(2)操作符集合:把一个问题从一个状态变换为另一个状态的动作集合。
(3)目标检测函数:用来确定一个状态是不是目标。
(4)路径费用函数:对每条路径赋予一定费用的函数。
其中,初始状态集合和操作符集合定义了问题的搜索空间。
一般给定问题就是确定该问题的一些基本信息,一个问题由4部分组成:
2017/11/18
6
和通常的搜索空间不同,人工智能中大多数问题的状态空间在问题求解之前不是全部知道的。
在人工智能中,搜索问题一般包括两个重要的问题:
搜索什么
搜索什么通常指的就是目标。
在哪里搜索
在哪里搜索就是“搜索空间”。搜索空间通常是指一系列状态的汇集,因此称为状态空间。
2017/11/18
7
所以,人工智能中的搜索可以分成两个阶段:
状态空间的生成阶段
在该状态空间中对所求问题状态的搜索
搜索可以根据是否使用启发式信息分为
盲目搜索
启发式搜索
2017/11/18
8
盲目搜索
只是可以区分出哪个是目标状态。
一般是按预定的搜索策略进行搜索。
没有考虑到问题本身的特性,这种搜索具有很大的盲目性,效率不高,不便于复杂问题的求解。
启发式搜索
是在搜索过程中加入了与问题有关的启发式信息,用于指导搜索朝着最有希望的方向前进,加速问题的求解并找到最优解。
2017/11/18
9
根据问题的表示方式分为
状态空间搜索
与或图搜索
状态空间搜索是用状态空间法来求解问题所进行的搜索
与/或图搜索是指用问题规约方法来求解问题时所进行的搜索。
2017/11/18
10
考虑一个问题的状态空间为一棵树的形式。
宽度优先搜索
深度优先搜索
如果根节点首先扩展,然后是扩展根节点生成的所有节点,然后是这些节点的后继,如此反复下去。
在树的最深一层的节点中扩展一个节点。只有当搜索遇到一个死亡节点(非目标节点并且是无法扩展的节点)的时候,才返回上一层选择其他的节点搜索。