State-space search
= State-space search
A <state-space search> solves a problem by exploring a <transition system>: a <state (computer science)> 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 (computer science)> 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>.<Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig>[Chapter 3, problem formulation and search strategies]{ref}