状态空间 (计算机科学)

计算机科学里的状态空间是对应一系统中所有可能组态的离散空间^[1]。状态空间是可以了解系统行为的抽象化工具，常用在人工智能以及博弈论中。

Vacuum World是有限状态空间的最短路问题

以玩具问题Vacuum World为例，吸尘器和灰尘可以存在的组态只有有限多个，因此状态空间是有限个。而从一开始计数，随时间递增的计数系统^[2]也是离散的，数量则是无限多个。没有阻尼的摆^[3]其状态空间是连续的，因此其数量为无限多个。

定义

状态空间可以用多元组[N, A, S, G]来定义，其中：

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

性质

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

国际象棋八个皇后问题的一个状态

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

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

以Vacuum World为例，假设吸尘器不能停在原来位置，也不会对角线行走，吸尘器接下来有四个位置可以移动，所以分枝数为4。Vacuum World的边是双向的，吸尘器移动到下个位置之后，可以再移动回来，吸尘器可以在四个相邻方格中移动，使状态空间出现环的结构，因此其状态空间不是树。

状态空间可以是连续的或是离散的，有限的或是无限的。

相关条目

• 状态空间 (物理)（英语：State space (physics)）：物理学的相关内容。
• 相空间：物理学和数学中关于控制工程中有关相空间（例如连续的状态空间）的资讯。
• 几率空间：几率领域的资讯。