用状态空间表示问题

用状态空间表示问题的基本步骤如下。

（1）定义状态的描述形式。

（2）用所定义的状态描述形式把所有问题的所有可能状态表示出来，并确定问题的初始状态集合和目标状态集合。

（3）定义一组算符。利用算符可以把问题由一种状态转变为另一种状态。

图2.6所示为吃豆人游戏的一些演示画面。图中小人在鼠标或者键盘的控制下可以东、南、西、北移动，移动时所经过路径上的豆豆就会被他吃掉。

(www.xing528.com)

图2.6　Pacman（吃豆人）游戏状态空间

这个问题怎样表示才方便用计算机进行处理呢？状态空间表示法就是不错的一种方法。但是将状态空间中的所有变量都拿来用往往不现实。以图2.6来说，直接能想到的变量有吃豆人坐标、吃豆人方向、豆豆的状态数。吃豆人坐标假设为3×3；吃豆人方向有4种；每个坐标点都有个豆豆，豆豆存在是否被吃2种状态，豆豆的状态数为29。总状态数为：9×4×29=18 432。可想而知，一旦地图面积大了，这个数字也会相当大。所以，在用状态空间表示问题的第（1）步中，需要根据问题的具体内容来选择状态的描述形式。

比如对于图2.6，如果任务目标是将所有豆豆都吃掉，那么就用豆豆及其是否存在作为状态变量，即状态变量选用豆豆坐标（x，y）和豆豆是否被吃掉即可。而问题的初始状态就是初始化时每个坐标点的豆豆状态，目标状态为所有位置的豆豆都被吃掉了。算符就是吃豆人东、南、西、北移动，会引起不同坐标的豆豆状态发生改变，如图2.7所示。

图2.7　以吃豆人向东和向北移动1步作为算符演示

同样，还是对于图2.6这个状态空间，但是任务目标变成了吃掉某个指定位置的豆豆，这时状态变量就可以选取吃豆人所在的位置（x，y）了；目标状态变成了吃豆人是否到达了指定的位置；算符不变，依然是吃豆人东、南、西、北移动。