State space search
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 intention of finding a "goal state" with the 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. Representation. In state space search, a state space is formally represented as a tuple formula_1, in which: Examples of state-space search algorithms. Uninformed search. According to Poole and Mackworth, the following are "uninformed" state-space search methods, meaning that  they do not have any prior information about the goal's location. Heuristic search. Some algorithms take into account information about the goal node's location in the form of a heuristic function. Poole and Mackworth cite the following examples as informed search algorithms: