State-Space Search for Problem Solving

Search is the primary technique used in Computer Science and Operations Research for solving computation-intensive combinatorial optimization problems, typically those in the NP-hard class [35]. The goal of a search is to quickly find an optimal or near-optimal solution from a finite or infinite but countable set of solutions. The size of the solution space of an NP-hard problem is exponential in term of the problem size in the worst case. Even in an average case, a search algorithm typically explores an exponential number of solutions in order to find an optimal one.