2. 搜索空间

状态空间：

全局状态空间，建模环境中包含的每一个可描述变量（细节）

搜索状态空间：仅需要建模解决特定搜索问题需要的变量

• 问题：路径寻址

  • 状态：（x,y）小黄人的位置
  • 动作：上下左右
  • 后继：根据动作更新位置
  • 目标：当前状态是否目标位置

• 问题：吃完所有豆子

  • 状态：｛（x,y），豆子分布情况｝
  • 动作：上下左右
  • 后继：根据动作状态
  • 目标：所有豆子被吃光

已如下为例：

6行5列

全局状态空间：豆子个数30，每个豆子状态为存在和被吃，因此可能状态有2^30，小黄人朝向有上下左右，因此可能状态30*4=120，鬼怪活动空间12，则全局状态空间为(2^30)120(12^2)*4

八皇后问题

全局状态空间：棋盘的各自数目64，八皇后数目8，每个皇后都可以放到每个格子上，因此全局状态空间为64^8次方种。如果考量每个皇后不重叠，则全局状态空间缩小为64636261605958*57种