State space
|
|
In computer science, a state space is a description of a configuration of 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
See also
- State space (controls) for information about state space in control engineering.