Editing State-space search

{{short description|Class of search algorithms}}
'''State-space search''' is a process used in the field of [[computer science]], including [[artificial intelligence]] (AI), in which successive [[Configuration graph|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 (mathematics)|set]] of ''states'' that a problem can be in. The set of states forms a [[Graph (discrete mathematics)|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 algorithm|search]] methods because the state space is [[Implicit graph|''implicit'']]: the typical state-space graph is much too large to generate and store in [[Computer storage|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]] <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 (mathematics)|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 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.<ref>{{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}}</ref>
* [[Depth-first search|Traditional depth-first search]]
* [[Breadth-first search]]
* [[Iterative deepening depth-first search|Iterative deepening]]
* [[Dijkstra's algorithm#Practical_optimizations_and_infinite_graphs|Lowest-cost-first search / Uniform-cost search (UCS)]]

===Informed search ===
These methods take the goal's location in the form of a [[heuristic function]].<ref>{{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}}</ref> Poole and Mackworth cite the following examples as informed search algorithms:
* Informed/Heuristic depth-first search
*[[Best-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==
<references />
* Stuart J. Russell and Peter Norvig (1995). ''Artificial Intelligence: A Modern Approach''. Prentice Hall.

[[Category:Search algorithms]]


{{compu-ai-stub}}