State space search is a process used in the field of computer science, including 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.
Problems are often modelled as a state space, a set of states that a problem can be in. The set of states forms 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 often 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.
Famous quotes containing the words state, space and/or search:
“Scepticism is an ability, or mental attitude, which opposes appearances to judgments in any way whatsoever, with the result that, owing to the equipollence of the objects and reasons thus opposed we are brought firstly to a state of mental suspense and next to a state of “unperturbedness” or quietude.”
—Sextus Empiricus (2nd or 3rd cen., A.d.)
“The within, all that inner space one never sees, the brain and the heart and other caverns where thought and feeling dance their sabbath.”
—Samuel Beckett (1906–1989)
“Man is eminently a storyteller. His search for a purpose, a cause, an ideal, a mission and the like is largely a search for a plot and a pattern in the development of his life story—a story that is basically without meaning or pattern.”
—Eric Hoffer (1902–1983)