State-space search

State space search is a process used in the field of artificial intelligence (AI) in which successive configurations or states of an instance are considered, with the goal of finding a goal state with a desired property.

In AI, 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 as used in AI 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.

The structure of state space search corresponds to the structure of the problem being solved in two different ways. They are,

• By making use of some legal operations, it enables to define a problem in order to convert the given situation into desired solution.
• It enables to define the procedure of solving a problem. Usually, this procedure is a combination of known techniques and search.

Advantages

• It is useful in finding the solutions to "hard" problems.
• It is widely used in artificial intelligence.

See also

• State space

References

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