状态空间法

---

状态空间

• 状态，描述某一类事物在不同时刻所处于的信息状况

• 操作，描述状态之间的关系

• 问题的状态空间可用一个三元序组来表示<s,f,g>：

  S：问题的全部初始状态的集合     

  F：操作的集合     

  G：目标状态的集合  

   

---

利用状态空间图求解的具体思路和步骤：

（1）设定状态变量及确定值域；

（2）确定状态组，分别列出初始状态集和目标状态集；

（3）定义并确定操作集；

（4）估计全部状态空间数，并尽可能列出全部状态空间或予以描述之；

（5）当状态数量不是很大时，按问题的有序元组画出状态空间图，依照状态空间图搜索求解。

---

传教士和野人问题（The Missionaries and Cannibals Problem）

在河的左岸有三个传教士、一条船和三个野人，传教士们想用这条船将所有的成员都运过河去，但是受到以下条件的限制：

 

① 教士和野人都会划船，但船一次最多只能装运两个；

② 在任何岸边野人数目都不得超过传教士，否则传教士就会遭遇危险：被野人攻击甚至被吃掉。

此外，假定野人会服从任何一种过河安排，试规划出一个确保全部成员安全过河的计划。

（1）设定状态变量及确定值域。

为了建立这个问题的状态空间，设左岸传教士数为m，则

m={0,1,2,3}；

对应右岸的传教士数为3－m； 左岸的野人数为c，则有

c={0,1,2,3}；

对应右岸野人数为3-c;左岸船数为b,故又有b={0,1}，右岸船数为1－b 。

（2）确定状态组，分别列出初始状态集和目标状态集。

问题的状态可以用一个三元数组来描述，以左岸的状态来标记，即

Sk = (m,c,b),

右岸的状态可以不必标出。

初始状态一个： S0 =（3,3,1），初始状态表示全部成员在河的左岸；

目标状态也只一个：Sg =(0,0,0) ，表示全部成员从河左岸渡河完毕。

（3）定义并确定操作集。

仍然以河的左岸为基点来考虑，把船从左岸划向右岸定义为Pij操作。其中,第一下标i表示船载的传教士数, 第二下标j表示船载的野人数；同理，从右岸将船划回左岸称之为操作，下标的定义同前。则共有10种操作，操作集为:

F={P01，P10，P11，P02，P20，Q01，Q10，Q11，Q02，Q20}

（参考文献：《人工智能及其应用》-第五版-清华大学出版社-蔡自兴）