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:03, 20 November 2019 (Add inline citation for unused source in →Definition). 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

For a discrete dynamical system defined by a function f, the state space of the system can be modeled as 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.Cite error: A <ref> tag is missing the closing </ref> (see the help page). [1] [4] [5] [2] [6] [7] }}

  1. ^ a b Nykamp, Duane. "State space definition". Math Insights. Retrieved 17 November 2019.
  2. ^ a b Papernick, Norman. "Infinite States and Infinite State Transitions". Carnegie Mellon University. Retrieved 12 November 2019.
  3. ^ Cite error: The named reference MIDYNS was invoked but never defined (see the help page).
  4. ^ Abbeel, Pieter. "Lecture 2: Uninformed Search". UC Berkeley CS188 Intro to AI. Retrieved 30 October 2019.
  5. ^ Abbeel, Pieter. "Lecture 3: Informed Search". UC Berkeley CS188 Intro to AI. Retrieved 12 November 2019.
  6. ^ Zhang, Weixong (1999). State-space search: algorithms, complexity, extensions, and applications. Springer. ISBN 978-0-387-98832-0.
  7. ^ Laubenbacher, R. Pareigis, B. (2001). "Equivalence Relations on Finite Dynamical Systems" (PDF). ADVANCES IN APPLIED MATHEMATICS. 26: 237–251.{{cite journal}}: CS1 maint: multiple names: authors list (link)
Retrieved from "https://en.wikipedia.org/w/index.php?title=State_space_(computer_science)&oldid=927175928"