狀態空間 (計算機科學)

在計算機科學中，狀態空間是用來描述一組用在簡單模型的離散狀態。可以用多元組[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

计算机科学