State-space search is a method used in computer science and artificial intelligence where successive states of a problem are examined to find a goal state. Problems are represented as a state space, a set of possible states forming a graph with edges representing operations between states. Unlike traditional search methods, the state space is often implicit and too large to store in memory, so nodes are generated and discarded dynamically. Solutions may be the goal state or a path from an initial state to it, common in combinatorial search.
Representation
In state-space search, a state space is formally represented as a tuple S : ⟨ S , A , Action ( s ) , Result ( s , a ) , Cost ( s , a ) ⟩ {\displaystyle S:\langle S,A,\operatorname {Action} (s),\operatorname {Result} (s,a),\operatorname {Cost} (s,a)\rangle } , in which:
- S {\displaystyle S} is the set of all possible states;
- A {\displaystyle A} is the set of possible actions, not related to a particular state but regarding all the state space;
- Action ( s ) {\displaystyle \operatorname {Action} (s)} is the function that establishes which action is possible to perform in a certain state;
- Result ( s , a ) {\displaystyle \operatorname {Result} (s,a)} is the function that returns the state reached performing action a {\displaystyle a} in state s {\displaystyle s} ;
- Cost ( s , a ) {\displaystyle \operatorname {Cost} (s,a)} is the cost of performing an action a {\displaystyle a} in state s {\displaystyle s} . In many state spaces, a {\displaystyle 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
- 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.2 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
- Stuart J. Russell and Peter Norvig (1995). Artificial Intelligence: A Modern Approach. Prentice Hall.
References
Poole, David; Mackworth, Alan. "3.5 Uninformed Search Strategies‣ Chapter 3 Searching for Solutions ‣ Artificial Intelligence: Foundations of Computational Agents, 2nd Edition". artint.info. Retrieved 7 December 2017. http://artint.info/2e/html/ArtInt2e.Ch3.S5.html ↩
Poole, David; Mackworth, Alan. "3.6 Heuristic Search‣ Chapter 3 Searching for Solutions ‣ Artificial Intelligence: Foundations of Computational Agents, 2nd Edition". artint.info. Retrieved 7 December 2017. http://artint.info/2e/html/ArtInt2e.Ch3.S6.html ↩