A state-space search solves a problem by exploring a transition system: a state records the current situation, a transition relation specifies legal moves, and a goal state specifies success. The answer is usually a path in a transition system, rather than just the final configuration. This separates modeling the problem from choosing the search algorithm.
For a sliding-tile puzzle, the state is the arrangement of tiles and the empty square; one move slides a neighboring tile into that square. Breadth-first search finds a solution using the fewest moves when all moves have equal cost. Depth-first search can use less working storage but need not find a shortest solution. Remembering visited configurations prevents repeatedly exploring a cycle. The same formulation applies to route finding and automated planning.[ref]
Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig. Chapter 3, problem formulation and search strategies
Articles by others on the same topic
State space search is a problem-solving technique used in various fields such as artificial intelligence (AI), computer science, and operations research. It involves exploring a set of possible states and moves to find a solution to a particular problem. Here are the key components and concepts associated with state space search: ### Components 1. **State**: A representation of a specific configuration of the problem at a given moment. Each state can be defined by its attributes and the values they take.