文档介绍：1
第3章搜索方法
搜索的基本概念
状态空间的搜索方法
与/或树的搜索方法
2
搜索的基本概念
搜索的含义
问题求解过程的形式化表示
3
搜索的含义
概念:
依靠经验,利用已有知识,根据问题的实际情况,不断寻找可利用知识,从而构造一条代价最小的推理路线,使问题得以解决的过程称为搜索
4
搜索的类型
按是否使用启发式信息
盲目搜索(Blind Search):按预定的控制策略进行搜索,在搜索过程中获得的中间信息并不改变控制策略。没有考虑到问题本身的特性,所以这种搜索效率不高。
启发式搜索(Heuristic Search):在搜索中加入了与问题有关的启发性信息,用于指导搜索朝着最有希望的方向前进,加速问题的求解过程并找到最优解。
按问题的表示方式
状态空间(State Space)搜索:用状态空间法来求解问题所进行的搜索
与或树(And/Or Tree)搜索:用问题归约法来求解问题时所进行的搜索
搜索的含义
5
问题求解过程的形式表示
为了进行搜索,首先必须考虑问题及其求解过程的形式表示,其表示是否适当,将直接影响到搜索求解的效率。
状态空间表示法
与或树表示法
6
状态空间表示法
状态空间表示法用“状态”和“算符”来表示问题
状态—描述问题求解过程不同时刻的状态
算符—表示对状态的操作
算符的每一次使用就使状态发生变化。当到达目标状态时,由初始状态到目标状态所使用的算符序列就是问题的一个解。
7
状态空间表示法
①状态:是描述问题求解过程不同时刻的状态的数据结构,可用一组变量的有序集表示:
当给每一个分量以确定的值时,就得到了一个具体的状态
②算符:引起状态中某些分量发生变化,从而使问题由一个状态变为另一个状态的操作称为算符。在产生式系统中,每一条产生式规则就是一个算符
Sk = (Sk1, Sk2, …, Skn)
8
状态空间表示法
③状态空间:
由问题的全部状态及一些可用算符所构成的集合称为问题的状态空间,一般用一个三元组表示:(S, F, G)
其中S是问题的所有初始状态构成的集合; F是算符的集合;G是目标状态的集合。
状态空间的图示形式称为状态空间图。其中节点表示状态;有向边表示算符。
9
状态空间表示法
二阶“梵塔”问题状态空间方法
有三个柱子(1,2,3)和两个不同尺寸的圆盘(A,B)。在每个圆盘的中心有个孔,所以圆盘可以堆叠在柱子上,最初,全部两个圆盘都堆在柱子1上(最大的在底部,最小的在顶部)。要求把所有圆盘都移到另一个柱子上,搬动规则为:
(1)一次只能搬一个圆盘
(2)不能将大圆盘放在小圆盘
(3)可以利用空柱子。
10
状态空间表示法
用状态空间方法来描述问题:
状态的表示
柱的编号用i,j来代表 (i,j)表示问题的状态其中: i代表A所在的柱子
j 代表B所在的柱子
状态集合(9种可能的状态) s0=(1,1), s1=(1,2), s2=(1,3) s3=(2,1), s4=(2,2), s5=(2,3) s6=(3,1), s7=(3,2), s8=(3,3)