文档介绍：搜索是人工智能中的一个基本问题,并与推理密切相关,搜索策略的优劣,将直接影响到智能系统的性能与推理效率。
搜索的基本概念
状态空间的盲目搜索
状态空间的启发式搜索
与/或树的盲目搜索
与/或树的启发式搜索
博弈树的启发式搜索
第4章搜索策略
1
搜索的基本概念
搜索的含义
状态空间法
问题归约法
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=(Sk0, Sk1)表示问题的状态,其中,Sk0表示金片A所在的钢针号,Sk1表示金片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/11)
6
A
B
A
B
A
B
1 2 3
1 2 3
1 2 3
二阶梵塔问题的初始状态和目标状态
问题的初始状态集合为S={S0}
目标状态集合为G={S4, S5}
初始状态S0和目标状态S4、S8如图所示
S0=(1, 1)
S4=(2, 2)
S8=(3, 3)
状态空间法
3. 状态空间的例子(2/11)
7
操作分别用A(i, j)和B(i, j)表示
A(i, j)表示把金片A从第i号钢针移到j号钢针上;
B(i, j)表示把金片B从第i号钢针一到第j号钢针上。共有12种操作,它们分别是:
A(1, 2) A(1, 3) A(2, 1) A(2, 3) A(3, 1) A(3, 2)
B(1, 2) B(1, 3) B(2, 1) B(2, 3) B(3, 1) B(3, 2)
根据上述9种可能的状态和12种操作,可构成二阶梵塔问题的状态空间图,如下图所示。
状态空间法
3. 状态空间的例子(3/11)
8
(3,3) (1,3) (1,2) (2,2)
二阶梵塔的状态空间图
从初始节点(1, 1)到目标节点(2, 2)及(3, 3)的任何一条路径都是问题的一个解。其中,最短的路径长度是3,它由3个操作组成。例如,从(1, 1)开始,通过使用操作A(1, 3)、B(1, 2)及A(3, 2),可到达(3, 3)。
A(1,2)
B(1,3)
A(2,3)