Search Space

Search space is the set of all possible states through which an AI system may move while looking for a solution. The more possibilities a problem contains, the larger the search space becomes and the more expensive the solution process is. Chess, route optimization, planning, and decision problems are classic examples. Many AI methods are, directly or indirectly, attempts to explore search spaces more efficiently. For that reason, the concept of search space offers a foundational way of understanding why some problems are hard.