======================================================================
=                         State space search                         =
======================================================================

                             Introduction
======================================================================
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 a 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, Action(s), Result(s,a), Cost(s,a) \rangle , in which:
*S is the set of all possible states;
*A is the set of possible action, not related to a particular state
but regarding all the state space;
*Action(s) is the function that establish which action is possible to
perform in a certain state;
*Result(s,a) is the function that return the state reached performing
action a in state s
*Cost(s,a) is the cost of performing an action a in state s. In many
state spaces is a constant, but this is not true in general.


 Uninformed Search
===================
According to Poole and Mackworth, the following are 'uninformed'
state-space search methods, meaning that they do not know information
about the goal's location.
* Traditional depth-first search
* Breadth-first search
* Iterative deepening
* Lowest-cost-first search


 Heuristic Search
==================
Some algorithms take into account information about the goal node's
location in the form of a heuristic function. Poole and Mackworth cite
the following examples as informed search algorithms:
* Heuristic depth-first search
*Greedy best-first search
* A* search


                               See also
======================================================================
* State space
* State space planning


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


 License
=========
All content on Gopherpedia comes from Wikipedia, and is licensed under CC-BY-SA
License URL: http://creativecommons.org/licenses/by-sa/3.0/
Original Article: http://en.wikipedia.org/wiki/State_space_search


.