Defining the Problem as a State Space Search

Before any search algorithm can run, a problem must be formally defined. AI formalises problem-solving as a search through a state space.

Components of a State Space Search Problem

A solution is a sequence of operators (actions) that transforms the initial state into a goal state; an optimal solution is the one with the lowest path cost among all solutions.

Worked Example: The 8-Puzzle

• States: every possible arrangement of the 8 numbered tiles + blank on the 3×3 board
• Initial state: the given scrambled arrangement
• Operators: move blank Up / Down / Left / Right (swap blank with the adjacent tile)
• Goal test: does the board match the target arrangement?
• Path cost: each move costs 1, so path cost = number of moves

Worked Example: The Water Jug Problem

Given a 4-litre jug and a 3-litre jug, no measuring marks, an unlimited water supply — measure exactly 2 litres.

• State: (x, y) = current litres in the 4-litre and 3-litre jug
• Initial state: (0, 0)
• Goal state: (2, y) for any y
• Operators: fill a jug, empty a jug, pour one jug into the other (until full or empty)

The State Space as a Graph

The state space is naturally a directed graph: nodes are states, edges are operator applications. Searching for a solution is searching this graph for a path from the initial-state node to a goal-state node — which is exactly what BFS, DFS, and heuristic search algorithms do (covered next).