Editing State space (computer science) (section)

==Exploration==
{{main|State space search}}

Exploring a state space is the process of enumerating possible states in search of a goal state. The state space of [[Pacman]], for example, contains a goal state whenever all food pellets have been eaten, and is explored by moving Pacman around the board.<ref name=BAIL2/>

===Search states===
A search state is a compressed representation of a world state in a state space, and is used for exploration. Search states are used because a state space often encodes more information than is necessary to explore the space. Compressing each world state to only information needed for exploration improves efficiency by reducing the number of states in the search.<ref name=BAIL2/> For example, a state in the Pacman space includes information about the direction Pacman is facing (up, down, left, or right). Since it does not cost anything to change directions in Pacman, search states for Pacman would not include this information and reduce the size of the search space by a factor of 4, one for each direction Pacman could be facing.

===Methods===
Standard search algorithms are effective in exploring discrete state spaces. The following algorithms exhibit both [[Completeness_(logic)|completeness]] and optimality in searching a state space:<ref name=BAIL2/><ref name=BAIL3/>
* [[Breadth-first search]]
* [[A* search]]
* [[Uniform cost search]]

These methods do not extend naturally to exploring continuous state spaces. Exploring a continuous state space in search of a given goal state is equivalent to optimizing an arbitrary [[continuous function]] which is not always possible; see [[mathematical optimization]].