Search problem
In theoretical computer science, a search problem is a problem in which the best possible solution is sought for a given input. The search problem differs from the associated optimization problem in that the optimization problem is not looking for the solution itself, but for the numerical value assigned to it.
Formally, a search problem is defined by a start and target state description presented in a symbolic representation, a set of operators and a function which determines whether the current state is a target state. The application of all available operators to the start state and the resulting states open up the search space, which can often be noted as a search tree.
For example, it is the 8-queens problem is a search problem, in which the search space the set of chess boards with a maximum of 8 placed thereon Ladies is. The starting condition here is an empty chessboard, the target function accepts chessboards with 8 queens that do not threaten each other. The operators map a chessboard S with queens onto a chessboard with k + 1 queens, where k queens are on the same squares as on S and the additional queen is on a square that was free on S.
