State space search

State space search

State space search is a process used in the field of artificial intelligence (AI) in which successive configurations or "states" of an instance are considered, with the goal of finding a "goal state" with a desired property.

In AI, problems are often modelled as a state space, a set of "states" that a problem can be in. The set of states form a graph where two states are connected if there is an "operation" that can be performed to transform the first state into the second.

State space search as used in AI differs from traditional computer science search methods because the state space is "implicit": the typical state space graph is much too large to generate and store in memory. Instead, nodes are generated as they are explored, and typically discarded thereafter. A solution to a combinatorial search instance may consist of the goal state itself, or of a path from some "initial state" to the goal state.

References

* Stuart J. Russell and Peter Norvig (2003). "Artificial Intelligence: A Modern Approach". Prentice Hall.

ee also

* state space


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • State space (dynamical system) — In the theory of discrete dynamical systems, a state 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… …   Wikipedia

  • State space — 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… …   Wikipedia

  • State (polity) — This article is about the general concept of the state. For the subjects of international law, see Sovereign state. For other uses, see State (disambiguation). The frontispiece of Thomas Hobbes Leviathan A state is an organised political… …   Wikipedia

  • Iterative deepening depth-first search — Graph and tree search algorithms Alpha beta pruning A* B* Beam Bellman–Ford algorithm Best first Bidirectional …   Wikipedia

  • Space music — Space music, also spelled spacemusic, is an umbrella term used to describe music that evokes a feeling of contemplative spaciousness. In fact, almost any music with a slow pace and space creating sound images could be called spacemusic. Stephen… …   Wikipedia

  • Space science — is an all encompassing term that describes all of the various science fields that are concerned with the study of the Universe, generally also meaning excluding the Earth and outside of the Earth s atmosphere . Originally, all of these fields… …   Wikipedia

  • State University of New York at New Paltz — Established 1828 Type Public President Donald P. Christian …   Wikipedia

  • Space opera — is a subgenre of speculative fiction or science fiction that emphasizes romantic, often melodramatic adventure, set mainly or entirely in space, generally involving conflict between opponents possessing powerful (and sometimes quite fanciful)… …   Wikipedia

  • State University of New York at Oswego — (SUNY Oswego) Motto To Learn, To Search, To Serve Established 1861 Type Public Endowment …   Wikipedia

  • Search for extraterrestrial intelligence — The search for extraterrestrial intelligence is sometimes abbreviated as SETI. For other uses, see SETI (disambiguation). Screen shot of the screensaver for SETI@home, a distributed computing project in which volunteers donate idle computer power …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”