状态空间 (计算机科学)

在计算机科学中，状态空间是用来描述一组用在简单模型的离散状态。可以用多元组[N, A, S, G]来定义，其中：

• N是由状态组成的集合。
• A是连接集合N中所有状态的弧的集合。
• S是一个集合N的非空子集合，其中包括启始状态。
• G是一个集合N的非空子集合，其中包括目的状态。

此状态空间就是状态空间搜寻要搜寻的范围。借由图论可以理解及分析状态空间的含意。

状态空间有以下共同的特质：

• 状态空间的复杂度和分枝数有密切的关系。
• 状态的结构，请参考图论：
  • 边的方向性（单向或双向）
  • 树
  • 有根图（英语：Rooted graph）