State space search

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.

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]

Heuristic Search

Some algorithms take into account information about the goal node's location in the form of a heuristic function[2]. Poole and Mackworth cite the following examples as informed search algorithms:

Heuristic depth-first search
Greedy best-first search
A* search

gollark: You CAN always abuse `set!`.

gollark: I guess just count total betrayals, take 2^that or something, and count if there was a betrayal in that many recent moves.

gollark: With my minor tweak where after round 93 of 100 they start engaging in evilness.

gollark: They're tit-for-tat clones.

gollark: This sounds hard, ħm.

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.
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.

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] 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.

[2] 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.