状态空间 (计算机科学)

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

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

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

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

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

参见

• 状态空间：控制工程中有关状态空间的资讯。
• 状态空间 (物理)：物理学中有关状态空间的资讯。
• 相空间：物理学和数学中关于控制工程中有关相空间（例如连续的状态空间）的资讯。
• 机率空间：机率中关于状态空间的资讯。

参考文献

• Equivalence Relations on Finite Dynamical Systems （页面存档备份，存于互联网档案馆）, Laubenbacher, R. Pareigis, B., ADVANCES IN APPLIED MATHEMATICS, 2001, VOL 26; PART 3, pages 237–251
• State-space search: algorithms, complexity, extensions, and applications, Weixiong Zhang, Springer, 1999, ISBN 978-0-387-98832-0