State-space search
Template:Short description 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.
RepresentationEdit
In state-space search, a state space is formally represented as a tuple <math> S: \langle S, A, \operatorname{Action}(s), \operatorname{Result}(s,a), \operatorname{Cost}(s,a) \rangle </math>, in which:
- <math>S</math> is the set of all possible states;
- <math>A</math> is the set of possible actions, not related to a particular state but regarding all the state space;
- <math>\operatorname{Action}(s)</math> is the function that establishes which action is possible to perform in a certain state;
- <math>\operatorname{Result}(s,a)</math> is the function that returns the state reached performing action <math>a</math> in state <math>s</math>;
- <math>\operatorname{Cost}(s,a)</math> is the cost of performing an action <math>a</math> in state <math>s</math>. In many state spaces, <math>a</math> is a constant, but this is not always true.
Examples of state-space search algorithmsEdit
Uninformed searchEdit
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.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>
- Traditional depth-first search
- Breadth-first search
- Iterative deepening
- Lowest-cost-first search / Uniform-cost search (UCS)
Informed searchEdit
These methods take the goal's location in the form of a heuristic function.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> Poole and Mackworth cite the following examples as informed search algorithms:
- Informed/Heuristic depth-first search
- Greedy best-first search
- A* search
See alsoEdit
- State space
- State-space planning
- Branch and bound – Method for making state-space search more efficient by pruning subsets of it
ReferencesEdit
<references />
- Stuart J. Russell and Peter Norvig (1995). Artificial Intelligence: A Modern Approach. Prentice Hall.