When is breadth-first search optimal?

Breadth-first search is optimal when every step has the same cost, because it finds the shallowest goal first. When step costs differ, uniform-cost search (which orders the frontier by accumulated path cost) is the uninformed strategy that guarantees a least-cost solution.

Why use iterative deepening instead of plain breadth-first search?

Breadth-first search stores the entire frontier and can require memory exponential in the depth. Iterative deepening repeatedly does depth-first search with growing depth limits, using only linear memory while still being complete and optimal on unit-cost problems, at the cost of re-expanding shallow nodes.

State-Space Search

State-space search is the systematic exploration of the set of states reachable from an initial state via available actions, in order to find a state that satisfies a goal test or a path that reaches one.

Definition

State-space search treats a problem as a graph whose nodes are states and whose edges are actions, and proceeds by expanding states from a frontier according to a fixed strategy until a goal state is found or the space is exhausted.

Scope

This topic covers the formulation of a problem as a state space (states, actions, transition model, goal test, path cost) and the uninformed search strategies that explore it without domain-specific guidance: breadth-first, uniform-cost, depth-first, depth-limited, and iterative-deepening search. It includes the analysis of these strategies by completeness, optimality, time complexity, and space complexity, and the distinction between tree search and graph search with repeated-state detection. Heuristic guidance is treated in the separate topic on heuristic search and A*.

Core questions

How is a problem represented as states, actions, a transition model, and a goal test?
How do breadth-first, depth-first, uniform-cost, and iterative-deepening search differ in their frontier ordering?
What are the completeness, optimality, time, and space guarantees of each uninformed strategy?
How does graph search avoid the wasteful re-exploration of states that tree search permits?

Key concepts

initial state and goal test
transition model and successors
frontier (open list) and explored set
breadth-first search
depth-first search
uniform-cost search
iterative deepening
tree search vs. graph search

Key theories

Frontier ordering determines the strategy: Uninformed search algorithms are distinguished only by the order in which they remove states from the frontier: a FIFO queue gives breadth-first, a LIFO stack gives depth-first, and a priority queue on path cost gives uniform-cost search.
Iterative deepening as a space-efficient optimum: Depth-first iterative-deepening search repeatedly runs depth-limited depth-first search with increasing limits, combining the linear space of depth-first search with the completeness and optimality (on unit costs) of breadth-first search.

Clinical relevance

Uninformed state-space search is the conceptual and implementation foundation for pathfinding, puzzle solving, reachability analysis in model checking, and as the substrate on which heuristic and adversarial search build; understanding its complexity guides when blind search is feasible versus when heuristics are required.

History

Systematic state-space search descends from graph-traversal algorithms of the 1950s, including Moore's and Dijkstra's shortest-path work, and was framed as a model of problem solving in early AI. Korf's 1985 analysis of iterative-deepening established its optimality among admissible tree searches with linear space.

Key figures

Nils J. Nilsson
Richard E. Korf
Edward F. Moore
Edsger W. Dijkstra

Seminal works

nilsson1971
russell2020

Frequently asked questions

When is breadth-first search optimal?: Breadth-first search is optimal when every step has the same cost, because it finds the shallowest goal first. When step costs differ, uniform-cost search (which orders the frontier by accumulated path cost) is the uninformed strategy that guarantees a least-cost solution.
Why use iterative deepening instead of plain breadth-first search?: Breadth-first search stores the entire frontier and can require memory exponential in the depth. Iterative deepening repeatedly does depth-first search with growing depth limits, using only linear memory while still being complete and optimal on unit-cost problems, at the cost of re-expanding shallow nodes.