Jump to content

State space (computer science)

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Thrice done french (talk | contribs) at 21:23, 18 November 2019. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
Vacuum World, a shortest path problem with a finite state space

In the theory of dynamical systems, a state space is the set of all possible configurations of a system.[1] It is a useful abstraction for reasoning about the behavior of a given system and is widely used in the fields of artificial intelligence and game theory.

State spaces can be either infinite or finite, and discrete or continuous. For instance, the toy problem Vacuum World has a discrete finite state space in which there are a limited set of configurations that the vacuum and dirt can be in. A "counter" system, where states are the natural numbers starting at 1 and are incremented over time[2] has an infinite discrete state space. The angular position of an undamped pendulum[3] is a continuous (and therefore infinite) state space.

Definition

Main article: State diagram

The states space is a directed graph where each possible state of a dynamical system is represented by a vertex, and there is a directed edge from a to b if and only if ƒ(a) = b where the function f defines the dynamical system.

State spaces are useful in computer science as a simple model of machines. Formally, a state space 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.

Properties

A state space has some common properties:

In many games the effective state space is small compared to all reachable states. For instance, in chess the effective state space is the set of positions that can be reached by game-legal moves. This is far smaller than the set of positions that can be achieved by placing combinations of the available chess pieces directly on the board.

State space search explores a state space.

See also

References

  1. ^ Cite error: The named reference MISSD was invoked but never defined (see the help page).
  2. ^ Cite error: The named reference CMUINF was invoked but never defined (see the help page).
  3. ^ Cite error: The named reference MIDYNS was invoked but never defined (see the help page).
  • 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
Retrieved from "https://en.wikipedia.org/w/index.php?title=State_space_(computer_science)&oldid=926812380"