State space search
From Academic Kids
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
