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:
“[17th-century] Puritans were the first modern parents. Like many of us, they looked on their treatment of children as a test of their own self-control. Their goal was not to simply to ensure the child’s duty to the family, but to help him or her make personal, individual commitments. They were the first authors to state that children must obey God rather than parents, in case of a clear conflict.”
—C. John Sommerville (20th century)
“Even the most subjected person has moments of rage and resentment so intense that they respond, they act against. There is an inner uprising that leads to rebellion, however short- lived. It may be only momentary but it takes place. That space within oneself where resistance is possible remains.”
—bell hooks (b. c. 1955)
“You that do search for every purling spring
Which from the ribs of old Parnassus flows,
And every flower, not sweet perhaps, which grows
Near thereabouts into your poesy wring;
You that do dictionary’s method bring
Into your rhymes, running in rattling rows;”
—Sir Philip Sidney (1554–1586)