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:
“Marriage is the highest state of friendship: If happy, it lessens our cares by dividing them, at the same time that it doubles our pleasures by mutual participation.”
—Samuel Richardson (1689–1761)
“No being exists or can exist which is not related to space in some way. God is everywhere, created minds are somewhere, and body is in the space that it occupies; and whatever is neither everywhere nor anywhere does not exist. And hence it follows that space is an effect arising from the first existence of being, because when any being is postulated, space is postulated.”
—Isaac Newton (1642–1727)
“At any age we must cherish illusions, consolatory or merely pleasant; in youth, they are omnipresent; in old age we must search for them, or even invent them. But with all that, boredom is their natural and inevitable accompaniment.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)