Class of search algorithms

**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 $S:\langle S,A,Action(s),Result(s,a),Cost(s,a)\rangle$, in which:

- $S$ is the set of all possible states;
- $A$ is the set of possible actions, not related to a particular state but regarding all the state space;
- $Action(s)$ is the function that establish which action is possible to perform in a certain state;
- $Result(s,a)$ is the function that returns the state reached performing action $a$ in state $s$
- $Cost(s,a)$ is the cost of performing an action $a$ in state $s$. In many state spaces a is a constant, but this is not always true.

##
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.^{[1]}

###
Informed search

These methods take the goal's location in the form of a heuristic function.^{[2]} Poole and Mackworth cite the following examples as informed search algorithms: