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

1
搜索是人工智能中的一个基本问题,并与推理密切相关,搜索策略的优劣,将直接影响到智能系统的性能与推理效率。
搜索概述
搜索的含义
状态空间问题求解方法
问题归约求解方法
搜索的盲目策略
状态空间的启发式搜索
与/或树的启发式搜索
博弈树的启发式搜索
第3章搜索策略
2
搜索的含义
概念:
依靠经验,利用已有知识,根据问题的实际情况,不断寻找可利用知识,从而构造一条代价最小的推理路线,使问题得以解决的过程称为搜索
适用情况:
不良结构或非结构化问题;难以获得求解所需的全部信息;更没有现成的算法可供求解使用。
搜索的类型
按是否使用启发式信息:
盲目搜索:按预定的控制策略进行搜索,在搜索过程中获得的中间信息并不改变控制策略。
启发式搜索:在搜索中加入了与问题有关的启发性信息,用于指导搜索朝着最有希望的方向前进,加速问题的求解过程并找到最优解。
按问题的表示方式:
状态空间搜索:用状态空间法来求解问题所进行的搜索
与或树搜索:用问题归约法来求解问题时所进行的搜索
3
状态空间问题求解方法
1. 状态空间问题表示
状态(State)
是表示问题求解过程中每一步问题状况的数据结构,它可形式地表示为:
Sk={Sk0, Sk1, …}
当对每一个分量都给以确定的值时,就得到了一个具体的状态。
操作(Operator)
也称为算符,它是把问题从一种状态变换为另一种状态的手段。它可理解为状态集合上的一个函数,它描述了状态之间的关系。
状态空间(State space)
用来描述一个问题的全部状态以及这些状态之间的相互关系。常用一个三元组表示为:
(S, F, G)
其中,S为问题的所有初始状态集合;F为操作的集合;G为目标状态的集合。
状态空间也可用一个赋值的有向图来表示,该有向图称为状态空间图。在状态空间图中,节点表示问题的状态,有向边表示操作。
4
状态空间法求解问题的基本过程:
首先,为问题选择适当的“状态”及“操作”的形式化描述方法;
然后,从某个初始状态出发,每次使用一个“操作”,递增地建立起操作序列,直到达到目标状态为止;
最后,由初始状态到目标状态所使用的算符序列就是该问题的一个解。
状态空间问题求解方法
2. 状态空间问题求解
5
二阶梵塔问题
设有三根钢针,它们的编号分别是1号、2号和3号。在初始情况下,1号钢针上穿有A、B两个金片,A比B小,A位于B的上面。要求把这两个金片全部移到另一根钢针上,而且规定每次只能移动一个金片,任何时刻都不能使大的位于小的上面。
解:设用Sk=(SkA, SkB)表示问题的状态,其中,SkA表示金片A所在的钢针号,SkB表示金片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)
状态空间问题求解方法
3. 状态空间的例子(1/14)
6
A
B
A
B
A
B
1 2 3
1 2 3
1 2 3
二阶梵塔问题的初始状态和目标状态
初始状态集合
S={S0}
目标状态集合
G={S4, S8}
初始状态S0和目标状态S4、S8如下图
S0=(1, 1)
S4=(2, 2)
S8=(3, 3)
状态空间问题求解方法
3. 状态空间的例子(2/14)
7
操作
Aij 表示把金片A从第i号钢针移到j号钢针上;
Bij 表示把金片B从第i号钢针一到第j号钢针上。
共有12种操作,它们分别是:
A12 A13 A21 A23 A31 A32
B12 B13 B21 B23 B31 B32
根据上述9种可能的状态和12种操作,可构成二阶梵塔问题的状态空间图,如下图所示。
状态空间问题求解方法
3. 状态空间的例子(3/14)
8
从初始节点(1, 1)到目标节点(2, 2)及(3, 3)的任何一条路径都是问题的一个解。其中,最短的路径长度是3,它由3个操作组成。例如,从(1, 1)开始,通过使用操作A13、B12及A32,可到达(3, 3)。
(1,1)
B12
A13
(2,1)
(3,2)
(2,3)
(3,3)
(1,3)
(3,1)
(1,2)
(2,2)
A32
A12
B13
A23
状态空间问题求解方法
3. 状态空间的例子(4/14)
二阶梵塔的状态空间图