The state-space model [N, A, S, GD]

The four-tuple

Luger gives one definition that every example in the chapter instantiates. A state space is the four-tuple

$$[N, A, S, GD]$$

where:

- $N$ — the set of nodes (states): every legal configuration the problem can be in. - $A$ — the set of arcs (operators): the legal moves that transform one state into another. - $S$ — a nonempty subset of $N$, the start state(s). - $GD$ — the goal description: a nonempty subset of $N$, the states you are trying to reach.

A solution path is any path from a node in $S$ to a node in $GD$. To *model* a problem is exactly to fill in these four slots — naming what a state is, what the legal moves are, where you begin, and what counts as done. Get the four-tuple right and the search algorithm is then mechanical.

Two kinds of goal

The goal description comes in two flavours, and confusing them leads to the wrong algorithm:

- Type 1 (state property). The goal is a *measurable property of a single state* — a winning tic-tac-toe board, the solved 8-puzzle configuration. You stop the instant you reach a node with that property; the *path* you took is incidental. - Type 2 (path property). The goal is a *measurable property of the whole path* — most famously the travelling-salesperson minimum-cost tour. No single state tells you whether you have won; you must track cumulative cost across the entire path. Type-2 goals force you to carry path information that type-1 goals let you discard.

The combinatorial explosion

The branching factor $B$ is the average number of children each state generates. At depth $d$ the number of nodes is $B^d$ — *exponential*. This single fact is why naive search fails on hard problems and why Chapter 4's heuristics exist. Chess has $B \approx 35$ and games run ~80 ply deep, giving on the order of $10^{120}$ possible game paths — vastly more than the number of atoms in the observable universe. Even modest branching factors are hopeless at depth: $B = 10$, $d = 10$ already means $10^{10}$ leaf nodes.

Worked example — the 8-puzzle as [N, A, S, GD]

The 8-puzzle is a $3\times 3$ frame with eight numbered tiles and one blank.

- $N$ = every arrangement of the eight tiles plus the blank ($9!/2 = 181{,}440$ *reachable* configurations — the full $9!$ space splits into two disconnected halves of equal size, so exactly half of all arrangements are reachable from any given start). - $A$ = the (up to) four operators slide the blank up / down / left / right — equivalently, slide an adjacent tile into the blank. - $S$ = the given scrambled board. - $GD$ = the single solved board $\{1,2,3 / 8,\_,4 / 7,6,5\}$ — a type-1 goal (a property of one state).

The blank has 2–4 legal moves depending on whether it sits in a corner, edge, or centre, so the branching factor averages roughly $B \approx 2.67$. At that rate the space is still huge at depth 20, which is exactly why the 8-puzzle becomes the running example for *heuristic* search in Module 4.