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 $S: \langle S, A, \operatorname(s), \operatorname(s,a), \operatorname(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;
*$\operatorname(s)$ is the function that establishes which action is possible to perform in a certain state;
*$\operatorname(s,a)$ is the function that returns the state reached performing action $a$ in state $s$;
*$\operatorname(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.
* Traditional depth-first search
* Breadth-first search
* Iterative deepening
* Lowest-cost-first search / Uniform-cost search (UCS)

Informed search

These methods take the goal's location in the form of a heuristic function. Poole and Mackworth cite the following examples as informed search algorithms:
* Informed/Heuristic depth-first search
* Greedy best-first search
* A* search

See also

* State space
* State-space planning
* Branch and bound – Method for making state-space search more efficient by pruning subsets of it

References

* Stuart J. Russell and Peter Norvig (1995). ''Artificial Intelligence: A Modern Approach''. Prentice Hall.

Search algorithms

{{compu-ai-stub