状態空間（コンピュータサイエンス）

コンピュータサイエンスにおいて、状態空間とは「システム」のあらゆる可能な構成の集合を表す離散空間である。 ^{[1]これは、与えられたシステムの動作を推論するための有用な抽象化であり、}人工知能やゲーム理論の分野で広く使用されている。

たとえば、おもちゃの問題であるVacuum World には、真空と汚れが存在できる構成の限られたセットが存在する離散有限状態空間があります。状態が1 から始まり、時間の経過とともに増加する自然数である「カウンター」システム^{[2]には、無限の離散状態空間があります。減衰のない}振り子の角度位置^[3]は、連続した (したがって無限の) 状態空間です。

状態空間は、コンピュータサイエンスにおいて、機械の単純なモデルとして役立ちます。正式には、状態空間はタプル[ N、  A、  S、  G ] として定義できます。ここで、

• Nは状態の集合である
• Aは状態を結ぶ弧の集合である
• SはNの開始状態を含む空でない部分集合である
• G は、目標状態を含むNの空でないサブセットです。

状態空間にはいくつかの共通の特性があります。

• 分岐要因が重要な複雑性
• 空間の構造についてはグラフ理論も参照:
  • 円弧の方向性
  • 木
  • ルート付きグラフ

たとえば、真空の世界では分岐係数は 4 です。これは、掃除機が移動した後に隣接する 4 つのマス目のうちの 1 つに到達できるためです (同じマス目に留まることも斜めに移動することもできないと仮定)。真空の世界のアークは双方向です。隣接するマス目から任意のマス目に到達できるためです。また、隣接する 4 つのマス目間を移動することでループに入ることができるため、状態空間はツリーではありません。

状態空間は、無限または有限、離散または連続のいずれかになります。

与えられたシステムの状態空間の大きさは、その空間の可能な構成の数である。^[3]

状態空間の大きさが有限である場合、状態空間の大きさを計算することは組み合わせ問題である。^[4]たとえば、エイトクイーンパズルでは、8x8のチェス盤に8つの駒を配置するすべての可能な方法を数えることで状態空間を計算できます。これは、64のセットから8つの位置を無交換で選択することと同じです。

${\displaystyle {\binom {64}{8}}=4,426,165,368}$

これは、クイーンの合法な配置の数である 92 よりも大幅に大きいです。多くのゲームでは、有効な状態空間は、すべての到達可能/合法な状態に比べて小さくなります。この特性はチェスでも見られ、有効な状態空間は、ゲームで合法な動きで到達できる位置の集合です。これは、利用可能なチェスの駒の組み合わせをボード上に直接配置することで達成できる位置の集合よりもはるかに小さくなります。

すべての連続状態空間は、対応する連続関数によって記述できるため、無限です。^[3]離散状態空間も（可算に）無限のサイズを持つことができます。たとえば、時間依存の「カウンター」システムの状態空間は、^[2]待ち行列理論で列に並んでいる顧客の数を定義するシステムに似ており、状態空間は {0、1、2、3、...} になります。

状態空間の探索とは、目標状態を探すために可能な状態を列挙するプロセスです。たとえば、パックマンの状態空間には、すべての餌が食べられたときの目標状態が含まれており、パックマンをボード上で動かすことで探索されます。^[5]

探索状態は、状態空間における世界状態の圧縮表現であり、探索に使用されます。探索状態が使用されるのは、状態空間が空間の探索に必要な情報よりも多くの情報をエンコードすることが多いためです。各世界状態を探索に必要な情報のみに圧縮すると、探索の状態数が減り、効率が向上します。^[5]たとえば、パックマン空間の状態には、パックマンが向いている方向 (上、下、左、右) に関する情報が含まれます。パックマンでは方向を変えるのにコストがかからないため、パックマンの探索状態にはこの情報は含まれず、パックマンが向いている可能性のある方向ごとに 1 つずつ、探索空間のサイズが 4 倍に縮小されます。

標準的な探索アルゴリズムは離散状態空間の探索に効果的です。以下のアルゴリズムは状態空間の探索において完全性と最適性の両方を示します。 ^{[5] [6]}

• 幅優先探索
• A*検索
• 均一コスト検索

これらの方法は、連続状態空間の探索には自然には拡張されません。与えられた目標状態を求めて連続状態空間を探索することは、任意の連続関数を最適化することと同等ですが、これは必ずしも可能ではありません。数学的最適化を参照してください。