欢迎下载

第五章

状态空间搜索策略

搜索是人工智能的一个基本问题，

是推理不可分割的一部分。

搜索是求解问

题的一种方法，是根据问题的实际情况，

按照一定的策略或规则，

从知识库中寻

找可利用的知识，

从而构造出一条使问题获得解决的推理路线的过程。

搜索包含

两层含义：

一层含义是要找到从初始事实到问题最终答案的一条推理路线；

另一

层含义是找到的这条路线是时间和空间复杂度最小的求解路线。

搜索可分为盲目

搜索和启发式搜索两种。

1

．

1  

盲目搜索策略

 1

．状态空间图的搜索策略

为了利用搜索的方法求解问题，

首先必须将被求解的问题用某种形式表示出来。

一般情况下，

不同的知识表示对应着不同的求解方法。

状态空间表示法是一种用

“状态”

和

“算符”

表示问题的方法。

状态空间可由一个三元组表示

(S

0

，

F

，

S

g

)

。

利用搜索方法求解问题的基本思想是：首先将问题的初始状态

(

即状态空间

图中的初始节点

)

当作当前状态，选择一适当的算符作用于当前状态，生成一组

后继状态

(

或称后继节点

)

，然后检查这组后继状态中有没有目标状态。如果有，

则说明搜索成功，从初始状态到目标状态的一系列算符即是问题的解；若没有，

则按照某种控制策略从已生成的状态中再选一个状态作为当前状态，

重复上述过

程，直到目标状态出现或不再有可供操作的状态及算符时为止。

算法

5

．

1  

状态空间图的一般搜索算法

①建立一个只含有初始节点

S

0

的搜索图

G

，把

S

0

放入

OPEN

表中。

②建立

CLOSED

表，且置为空表。

③判断

OPEN

表是否为空表，若为空，则问题无解，退出。

④选择

OPEN

表中的第一个节点，把它从

OPEN

表移出，并放入

CLOSED

表中，将

此节点记为节点

n

。