State space search
Encyclopedia
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 goal 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.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, including artificial intelligence
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
(AI), in which successive configurations
Configuration graph
Configuration graphs are a theoretical tool used in computational complexity theory to prove a relation between graph reachability and complexity classes.- Definition :...
or states of an instance are considered, with the goal of finding a goal state with a desired property.
Problems are often modelled as a state space
State space
In the theory of discrete dynamical systems, a state space is a directed graph where each possible state of a dynamical system is represented by a vertex, and there is a directed edge from a to b if and only if ƒ = b where the function f defines the dynamical system.State spaces are...
, a set of states that a problem can be in. The set of states forms a graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
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
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
search
Search algorithm
In computer science, a search algorithm is an algorithm for finding an item with specified properties among a collection of items. The items may be stored individually as records in a database; or may be elements of a search space defined by a mathematical formula or procedure, such as the roots...
methods because the state space is implicit: the typical state space graph is much too large to generate and store in memory
Computer storage
Computer data storage, often called storage or memory, refers to computer components and recording media that retain digital data. Data storage is one of the core functions and fundamental components of computers....
. 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.