State space search
|
|
The concept of state space search is widely used in artificial intelligence. Successive configurations or states of an instance are considered, with the goal of finding a goal state with a desired property. This 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 search can be though of as a tree search with the addition of leaf-level heuristics to terminate searches of various branches. In game-playing, the min-max algorithm is the optimal form of such heuristic search.
See also: state space