State Space Search: Formulation, Trees vs Graphs, and Complexity

The formal five-part problem definition, why a small state space produces an infinite search tree, the difference between a node and a state, tree-search vs graph-search, and the completeness and complexity of every uninformed strategy.

The overview said a problem is a graph and you search it. That’s the right mental picture, but it hides three distinctions that decide whether your search terminates, whether it finds the best answer, and whether it fits in memory:

a state is not a node
the state space is not the search tree
tree search is not graph search

Get these wrong and you write a search that loops forever on a five-state problem. This page is the rigorous version.

Formal problem formulation

A search problem is defined by five components. Not four — the transition model and the action set are separate things, and separating them is what lets you write a solver that never mentions your problem domain.

Component	Signature	What it says
Initial state	$s_0$	Where the agent starts
Actions	$\text{ACTIONS}(s)$	The set of actions applicable in $s$
Transition model	$\text{RESULT}(s, a)$	The state reached by doing $a$ in $s$
Goal test	$\text{GOAL-TEST}(s)$	Is $s$ a goal?
Step cost	$c(s, a, s')$	Cost of that one action — must be ≥ 0

Together the first three implicitly define the state space: the set of all states reachable from $s_0$ by any sequence of actions. You never build it. You generate it lazily, and for most interesting problems you only ever touch a sliver of it.

class Problem:
    """Every search algorithm on this site works against exactly this interface."""
    def initial(self): ...
    def actions(self, state): ...
    def result(self, state, action): ...
    def goal_test(self, state): ...
    def step_cost(self, state, action, next_state): return 1

Why step costs must be non-negative. Uniform-cost search and A* both stop the moment they pop a goal, on the reasoning that nothing cheaper can still be in the frontier. A negative edge breaks that reasoning — a longer path could turn out cheaper — and both algorithms silently return wrong answers. If you genuinely have negative costs you need Bellman-Ford, not A*.

Goal test: a predicate, not a state

Notice GOAL-TEST is a function, not a target state. This matters more than it looks:

8-puzzle — one specific goal board. state == GOAL is fine.
Water jug — any state with 2 gallons in a jug. Four states qualify.
Block world — any state where ON(A,B) and ON(B,C) hold, regardless of where the arm is. A subset test.
N-queens — any complete non-attacking arrangement. 92 of them for $n = 8$ .

Writing state == goal when the real goal is a predicate is the single most common bug in student search code. It makes a solvable problem look unsolvable, because no reachable state ever equals your one hand-picked target.

Abstraction: choosing what a state is

Before any of this you make a modelling decision that dominates everything else: what do you put in the state?

Consider “drive from Arad to Bucharest”. The real world state includes your speed, the weather, the radio station, the fuel level, the passengers, the scenery. The useful state is: which city you are in. That’s it.

The test for a valid abstraction is precise: every abstract solution must be expandable into a real solution. “Drive Arad → Sibiu” must be something you can actually carry out, whatever the weather is doing. If some abstract action can’t be executed in the real world, your plan is fiction.

The test for a useful abstraction is that the removed detail doesn’t change which plan is best. Fuel level would matter if you could run dry; if you can’t, dropping it is free.

Almost all of the engineering in applying search is here, in deciding what belongs in the state — not in picking BFS over DFS.

The state space is not the search tree

Here is the distinction that catches everyone.

The state space is a graph: each state appears exactly once, and edges are actions. It can have cycles.

The search tree is what your algorithm actually explores: a tree of paths, rooted at $s_0$ . The same state appears once per distinct path that reaches it.

A three-state cyclic graph generates an infinite search tree:

Three states. Infinite tree. A depth-first search on this never terminates, and it isn’t a bug in DFS — it’s what the tree genuinely looks like.

The practical consequence: the size of your state space tells you almost nothing about the cost of searching it, unless you also say whether you are detecting repeated states.

A node is not a state

A state is a configuration of the world. A node is a bookkeeping record in your search:

from dataclasses import dataclass
from typing import Any, Optional

@dataclass
class Node:
    state:  Any                     # the world configuration
    parent: Optional['Node'] = None # the node we came from
    action: Any = None              # the action that got us here
    g:      float = 0.0             # path cost from the root
    depth:  int = 0                 # number of actions from the root

    def path(self):
        """Walk parent pointers back to the root, then reverse."""
        node, actions = self, []
        while node.parent is not None:
            actions.append(node.action)
            node = node.parent
        return actions[::-1]

The differences that matter:

	State	Node
Represents	a world configuration	a path to a configuration
Has a parent	no	yes
Has a cost	no	yes — the cost of getting there
Duplicates	each state exists once	many nodes can share one state

In the diagram above, state A appears in eight different nodes at depth 4. They’re different nodes — different paths, different costs — holding the same state.

Store nodes in the frontier; store states in the explored set. Mixing them up gives you either a set that never matches (because Node isn’t hashable by state) or a search that can’t reconstruct its own answer.

The parent pointer is also why you don’t need to carry the whole path in the frontier. Copying a growing list into every child, as the beginner-friendly code on the other pages does for clarity, is $O(d)$ per node; parent pointers make it $O(1)$ and reconstruct the path only once at the end.

Tree search vs graph search

These are the same algorithm apart from three lines.

def tree_search(problem, frontier):
    """No memory of where it has been. Can loop forever."""
    frontier.push(Node(problem.initial()))
    while frontier:
        node = frontier.pop()
        if problem.goal_test(node.state):
            return node.path()
        for child in expand(problem, node):
            frontier.push(child)
    return None


def graph_search(problem, frontier):
    """Remembers expanded states. Terminates on any finite state space."""
    frontier.push(Node(problem.initial()))
    explored = set()                                  # <-- added
    while frontier:
        node = frontier.pop()
        if problem.goal_test(node.state):
            return node.path()
        if node.state in explored:                    # <-- added
            continue                                  # <-- added
        explored.add(node.state)                      # <-- added
        for child in expand(problem, node):
            frontier.push(child)
    return None


def expand(problem, node):
    for action in problem.actions(node.state):
        nxt = problem.result(node.state, action)
        yield Node(nxt, node, action,
                   node.g + problem.step_cost(node.state, action, nxt),
                   node.depth + 1)

That explored set changes the algorithm’s fundamental properties:

	Tree search	Graph search
Terminates on a cyclic space	❌ no	✅ yes
Memory	frontier only	frontier + every state seen
Nodes explored	up to infinite	≤ number of states
Right choice when	the space is a genuine tree, or memory is the binding constraint	almost always

The cost is real: graph search’s memory is $O(|S|)$ — proportional to the whole state space, not the frontier. For the 8-puzzle (181,440 states) that’s nothing. For chess it’s impossible, which is exactly why game engines use tree search plus a transposition table — a fixed-size cache that behaves like an explored set but is allowed to forget.

The subtle bug in graph search. Discarding a state you’ve already explored is safe for BFS with uniform costs, but wrong for uniform-cost search and A* — a later path may reach the same state more cheaply. Those algorithms need best_g[state] rather than a plain set, so a cheaper route can get back in. The 8-puzzle solver does exactly this.

Measuring a search algorithm

Four criteria, always in this order:

Completeness — if a solution exists, is it guaranteed to find one?
Optimality — is the solution it finds the cheapest one?
Time complexity — how many nodes does it generate?
Space complexity — how many nodes does it hold at once?

Complexity is expressed in three quantities:

Symbol	Meaning
$b$	branching factor — max successors of any node
$d$	depth of the shallowest goal
$m$	maximum depth of the state space (may be ∞)

Note $d$ and $m$ are different, and the gap between them is the whole story of BFS vs DFS. A space can have a goal at depth 2 and paths running to depth 1,000,000.

The uninformed strategies, compared

Strategy	Complete?	Optimal?	Time	Space
Breadth-first	✅ if $b$ finite	✅ if step costs equal	$O(b^d)$	$O(b^d)$
Uniform-cost	✅ if costs ≥ ε > 0	✅ always	$O(b^{1+\lfloor C^*/\varepsilon\rfloor})$	same
Depth-first	❌ (tree search) ✅ (graph, finite)	❌	$O(b^m)$	$O(bm)$
Depth-limited	❌ if $\ell < d$	❌	$O(b^\ell)$	$O(b\ell)$
Iterative deepening	✅ if $b$ finite	✅ if step costs equal	$O(b^d)$	$O(bd)$
Bidirectional	✅	✅ if BFS both ways	$O(b^{d/2})$	$O(b^{d/2})$

Read the space column, not the time column. That’s the one that kills you.

Why memory is the real constraint

Take $b = 10$ , one million nodes generated per second, one kilobyte per node — all generous assumptions:

Depth	Nodes	Time	Memory
2	110	0.1 ms	110 KB
4	11,110	11 ms	10.8 MB
6	10⁶	1.1 s	1.06 GB
8	10⁸	1.9 min	106 GB
10	10¹⁰	3.1 hours	10.3 TB
12	10¹²	12.9 days	1.01 PB
14	10¹⁴	3.5 years	101 PB

Look at depth 8: under two minutes of compute, but 106 GB of RAM. You will run out of memory hours before you run out of patience. This is why BFS, despite being complete and optimal, is rarely the algorithm that ships.

Iterative deepening: the resolution

The fix is almost too neat. Run depth-limited search with limit 0, then 1, then 2, until you find a goal. You get BFS’s completeness and optimality with DFS’s memory — $O(bd)$ instead of $O(b^d)$ .

The obvious objection is that you re-generate the shallow nodes over and over. It turns out not to matter, because in an exponentially growing tree the last level contains most of the nodes:

Depth $d$	BFS nodes generated	IDS nodes generated	Overhead
3	1,111	1,234	1.11×
5	111,111	123,456	1.11×
8	111,111,111	123,456,789	1.11×

An 11% time penalty in exchange for an exponential memory saving. The ratio stays at 1.11 because it converges to $b/(b-1)^2 \cdot$ … — in short, for $b = 10$ the repeated work is a rounding error.

That trade is why iterative deepening is the standard uninformed search, and why its heuristic cousin IDA* is what solves the 15-puzzle when A* runs out of RAM.

Bidirectional search

Search forward from the start and backward from the goal simultaneously; stop when the frontiers meet. Two trees of depth $d/2$ are dramatically smaller than one of depth $d$ :

$b^{d/2} + b^{d/2} \ll b^{d}$

$d$ (with $b = 10$ )	One-way $b^d$	Two halves $2b^{d/2}$	Saving
4	10,000	200	50×
8	10⁸	20,000	5,000×
12	10¹²	2 × 10⁶	500,000×
16	10¹⁶	2 × 10⁸	5 × 10⁷×

It looks like free money, and sometimes it is — bidirectional Dijkstra is genuinely how route planners work. But it needs three things that often aren’t available:

An explicit goal state, not a predicate. You can’t search backward from “any non-attacking queen arrangement” — you’d have to enumerate all 92 of them first.
Reversible actions — you need $\text{PREDECESSORS}(s)$ , and for many problems computing it is far harder than computing successors.
Memory for at least one frontier, since you must test every new node against the other side’s frontier.

Miss any one and bidirectional search isn’t applicable.

Problem characteristics: choosing before you code

Before picking an algorithm, answer these seven questions. They come from Rich and Knight’s Artificial Intelligence, and each one rules techniques in or out.

The recoverability question in particular maps straight onto implementation:

Class	Meaning	Example	What your code needs
Ignorable	Steps can be ignored	Theorem proving — a useless lemma costs nothing	Simple control, no backtracking
Recoverable	Steps can be undone	8-puzzle, block world	Backtracking + a visited set
Irrecoverable	Steps are permanent	Chess, surgery, a deployed migration	Plan-then-act; search before committing

And question 5 decides your whole architecture. If the answer is a state, you can use local search — hill climbing, min-conflicts, simulated annealing — and throw away the path entirely, which is why min-conflicts solves million-queens in about 50 moves. If the answer is a path, you’re stuck storing history, and you need BFS, A*, or IDA*.

Putting it together: a complete generic solver

import heapq
from collections import deque
from dataclasses import dataclass
from typing import Any, Optional


@dataclass
class Node:
    state: Any
    parent: Optional['Node'] = None
    action: Any = None
    g: float = 0.0
    depth: int = 0

    def path(self):
        node, out = self, []
        while node.parent is not None:
            out.append(node.action); node = node.parent
        return out[::-1]


def expand(problem, node):
    for a in problem.actions(node.state):
        nxt = problem.result(node.state, a)
        yield Node(nxt, node, a,
                   node.g + problem.step_cost(node.state, a, nxt),
                   node.depth + 1)


def best_first(problem, f):
    """The one algorithm. `f` decides the order and therefore the strategy:
         f = lambda n: n.depth   -> breadth-first
         f = lambda n: -n.depth  -> depth-first
         f = lambda n: n.g       -> uniform-cost / Dijkstra
         f = lambda n: n.g+h(n)  -> A*
    """
    start = Node(problem.initial())
    counter = 0
    frontier = [(f(start), counter, start)]
    reached = {start.state: start}                 # state -> cheapest node

    while frontier:
        _, _, node = heapq.heappop(frontier)
        if problem.goal_test(node.state):
            return node.path(), node.g
        for child in expand(problem, node):
            s = child.state
            # let a cheaper route back in — this is what a plain
            # `explored` set gets wrong for UCS and A*
            if s not in reached or child.g < reached[s].g:
                reached[s] = child
                counter += 1
                heapq.heappush(frontier, (f(child), counter, child))
    return None, float('inf')


def iterative_deepening(problem):
    """Complete and optimal on unit costs, in O(b*d) memory."""
    def dls(node, limit, on_path):
        if problem.goal_test(node.state):
            return node
        if limit == 0:
            return 'cutoff'
        cutoff = False
        for child in expand(problem, node):
            if child.state in on_path:            # cycle check along THIS path
                continue
            r = dls(child, limit - 1, on_path | {child.state})
            if r == 'cutoff':
                cutoff = True
            elif r is not None:
                return r
        return 'cutoff' if cutoff else None

    from itertools import count
    for depth in count():
        start = Node(problem.initial())
        r = dls(start, depth, {start.state})
        if r != 'cutoff':
            return r.path() if r else None

Two details worth stealing:

best_first with a pluggable f is every strategy on this page. BFS, DFS, Dijkstra and A* differ only in one lambda. Write it once.
Iterative deepening checks cycles against on_path, not a global set. A global set would be wrong: a state legitimately reachable at depth 5 on one branch might need to be re-reached at depth 3 on another. Only states on the current path are genuinely cycles.

Where to go next

Problem Solving with AI: The State-Space Framework — the gentler introduction
Issues in Search Techniques — what goes wrong, and how to tell which failure you’re looking at
The 8-Puzzle — all of this applied to one problem
A* Search — the informed strategy in full
BFS Shortest Path · Dijkstra — the uninformed workhorses