State space
From Wikipedia, the free encyclopedia
 |
This article does not cite any references or sources. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. (December 2009) |
In computer science, a state space is a description of a configuration of discrete states used as a simple model of machines. Formally, it can be defined as a tuple [N, A, S, G] where:
- N is a set of states
- A is a set of arcs connecting the states
- S is a nonempty subset of N that contains start states
- G is a nonempty subset of N that contains the goal states.
The state space is what state space search searches in. Graph theory is helpful in understanding and reasoning about state spaces.
A state space has some common properties:
- complexity, where branching factor is important
- structure of the space, see also graph theory:
- directionality of arcs
- tree
- Rooted graph
[edit] See also
- State space (controls) for information about continuous state space in control engineering.
- State space (physics) for information about continuous state space in physics.
- Phase space for information about phase state (like continuous state space) in physics and mathematics.
- Probability space for information about state space in probability.
