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{Action}(s), \operatorname{Result}(s,a), \operatorname{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;
$\operatorname{Action}(s)$ is the function that establishes which action is possible to perform in a certain state;
$\operatorname{Result}(s,a)$ is the function that returns the state reached performing action $a$ in state $s$ ;
$\operatorname{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.{{cite web|last1=Poole|first1=David|last2=Mackworth|first2=Alan|title=3.5 Uninformed Search Strategies‣ Chapter 3 Searching for Solutions ‣ Artificial Intelligence: Foundations of Computational Agents, 2nd Edition|url=http://artint.info/2e/html/ArtInt2e.Ch3.S5.html|website=artint.info|accessdate=7 December 2017}}

=Informed search =

These methods take the goal's location in the form of a heuristic function.{{cite web|last1=Poole|first1=David|last2=Mackworth|first2=Alan|title=3.6 Heuristic Search‣ Chapter 3 Searching for Solutions ‣ Artificial Intelligence: Foundations of Computational Agents, 2nd Edition|url=http://artint.info/2e/html/ArtInt2e.Ch3.S6.html|website=artint.info|accessdate=7 December 2017}} Poole and Mackworth cite the following examples as informed search algorithms:

Informed/Heuristic depth-first search
Greedy best-first search
A* search

References

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

Category:Search algorithms