狀態空間 (計算機科學)

本條目存在以下問題，請協助改善本條目或在討論頁針對議題發表看法。 此條目已列出參考文獻，但因為沒有文內引註而使來源仍然不明。 (2025年2月9日) 请加上合适的文內引註来改善这篇条目。 此條目需要补充更多来源。 (2025年2月9日) 请协助補充多方面可靠来源以改善这篇条目，无法查证的内容可能會因為异议提出而被移除。 致使用者：请搜索一下条目的标题（来源搜索："狀態空間 (計算機科學)" — 网页、新闻、书籍、学术、图像），以检查网络上是否存在该主题的更多可靠来源（判定指引）。

计算机科学裡的狀態空間是對應一系統中所有可能組態的离散空间^[1]。狀態空間是可以瞭解系統行為的抽象化工具，常用在人工智能以及博弈论中。

以玩具問題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)）：物理學的相關內容。
• 相空間：物理學和數學中關於控制工程中有關相空間（例如連續的狀態空間）的資訊。
• 機率空間：機率領域的資訊。