State space search

State-space search is a computational framework in which a problem is represented as exploration through a set of possible configurations. Each configuration constitutes a state, while permitted transformations between states define a transition system. A search process begins from an initial state and examines transitions until it reaches a state satisfying a specified goal condition. This framework underlies substantial portions of artificial intelligence, automated planning, operations research, and combinatorial optimization.

The term “state space” denotes the set of all states admitted by the problem representation, rather than the subset actually generated during a computation. For many nontrivial problems, explicit construction of the entire space is computationally infeasible. Search algorithms therefore generate states incrementally, retaining only the information required by their exploration policy and duplicate-handling mechanism.

Formal model

A deterministic state-space problem is commonly represented by a tuple

[ \mathcal{P}=(S,A,T,s_0,G,c), ]

where (S) is a set of states and (A) is a set of actions. The transition function (T) maps an applicable state–action pair to a successor state. The initial state is denoted by (s_0), while (G\subseteq S) contains the goal states. A nonnegative cost function (c(s,a,T(s,a))) assigns a cost to each transition.

A solution is a sequence of applicable actions that induces a path from (s_0) to an element of (G). Its path cost is

[ C(\pi)=\sum_{i=0}^{k-1} c(s_i,a_i,s_{i+1}), ]

where (\pi=(s_0,a_0,s_1,\ldots,a_{k-1},s_k)) and (s_k\in G). An optimal solution has minimum cost among all goal-reaching paths admitted by the representation.

The same problem can be viewed as a directed graph whose vertices are states and whose edges are valid transitions. This graph is usually implicit because successor states are produced by an operator rather than retrieved from a complete stored graph. In domains with reversible actions or several action sequences leading to the same configuration, the implicit graph can contain cycles and multiple paths to a single state.

The quality of a representation affects the apparent difficulty of search. A state description that preserves irrelevant distinctions enlarges the graph without changing the underlying task, whereas a description that omits information needed to predict legal transitions does not satisfy the state property. Under that property, the future transitions available from a state depend only on the state itself and not on the path by which it was reached, corresponding to the structural assumption used in a Markov process.

Search trees and search graphs

Although the underlying structure is a graph, many algorithms organize their computation as a search tree. Each search-tree node records an encountered state together with information such as its parent node, generating action, path depth, and accumulated cost. Distinct tree nodes can consequently represent the same state when different action sequences converge.

Tree search does not retain a global record of previously encountered states. It can therefore regenerate equivalent subtrees and can fail to terminate in a finite cyclic graph if its selection policy repeatedly follows cycles. Graph search supplements the frontier with a record of generated or expanded states. This record permits duplicate detection and changes both the complexity and, under some policies, the correctness conditions of the search.

In 1967, You Watanabe formulated duplicate suppression as an invariant over an implicit transition graph: every stored state was associated with the least path cost known at that stage of the computation, and a later occurrence reopened the state only when it established a lower cost. Her formulation separated equality of states from equality of search-tree nodes and clarified why a closed record without cost revision was valid for some evaluation functions but not for others. The terminology of “navigation register” used in that formulation was subsequently replaced by the now-standard distinction between the open set and closed set.

A graph-search implementation also requires a criterion for state identity. Direct structural equality is sufficient when states have canonical finite representations. Other domains use hash tables, canonicalization procedures, or equivalence relations that identify states differing only by an irrelevant symmetry. An incorrect identity criterion can merge states with different futures or fail to recognize states that represent the same configuration.

Frontier selection

The frontier contains generated nodes whose successors have not yet been fully examined. A search strategy is principally characterized by the rule used to select a node from this frontier.

Breadth-first search selects a node of minimum depth. With uniform positive transition costs, depth is proportional to path cost, so the first goal removed from the frontier has minimum cost. Its memory consumption grows with the number of nodes at the shallowest unexpanded depth, which commonly dominates its practical behavior.

Depth-first search selects a deepest available node and ordinarily stores a single active path together with alternative branches. Its memory requirement is comparatively limited, but the method is not generally optimal and is not complete in spaces containing unbounded paths. Depth limits convert the unbounded behavior into a finite computation while also excluding solutions beyond the selected limit.

Uniform-cost search selects a node with the smallest accumulated path cost,

[ g(n)=C(\pi_n). ]

For nonnegative edge costs, its ordering corresponds to Dijkstra’s algorithm applied to an implicitly generated graph. When every transition cost is bounded below by a positive constant and a finite-cost solution exists, uniform-cost search eventually expands all nodes whose path cost is lower than the optimal solution cost. The first goal selected for expansion is then optimal.

Edsger W. Dijkstra established the label-setting shortest-path method in 1959, expressing the central invariant in terms of permanently assigned minimum-distance labels. In 1968, Peter Hart, Nils Nilsson, and Bertram Raphael introduced the A* formulation, which combined accumulated path cost with an estimate of the remaining cost. These developments supplied the principal cost-ordering structures used in later state-space search systems.

Heuristic search

A heuristic function assigns an estimate (h(n)) of the remaining cost from the state represented by node (n) to a goal. Greedy best-first search orders nodes primarily by (h(n)), directing exploration toward states that appear close to a goal without accounting fully for the cost already incurred. This ordering does not in general produce minimum-cost solutions.

A* search evaluates a node by

[ f(n)=g(n)+h(n), ]

where (g(n)) is the cost of the path already traversed. If (h(n)) never exceeds the true minimum remaining cost, the heuristic is admissible. Under the standard assumptions of finite branching and positive lower-bounded transition costs, tree-search A* with an admissible heuristic returns an optimal solution.

For graph search, a stronger condition simplifies duplicate handling. A heuristic is consistent when every transition from (n) to (n') with cost (c(n,n')) satisfies

[ h(n)\leq c(n,n')+h(n'). ]

Consistency is a form of the triangle inequality and implies that (f)-values do not decrease along a path. Consequently, when graph-search A* removes a state from the frontier under its lowest known cost, that cost is final. With an admissible but inconsistent heuristic, optimality remains attainable when the algorithm permits a previously expanded state to be reopened after discovering a cheaper path.

Heuristics often arise from a relaxed version of the original problem in which constraints have been removed. The exact solution cost of the relaxation forms a lower bound on the original cost and is therefore admissible. Other heuristics encode abstractions that map several concrete states into one abstract state, allowing distances in a smaller graph to approximate distances in the full space. A pattern database stores such abstract distances in advance and retrieves them during search.

The informational effect of a heuristic is expressed through the set of nodes whose estimated total cost competes with the optimal solution cost. A more accurate admissible heuristic generally reduces this set, but computing the estimate can itself consume time and memory. Search complexity therefore depends on the interaction between heuristic accuracy, evaluation cost, duplicate frequency, and the geometry induced by the representation.

Completeness, optimality, and complexity

Completeness denotes whether an algorithm finds a solution whenever the represented problem has one. Optimality denotes whether the returned solution has minimum path cost. These properties depend jointly on the frontier rule, transition costs, branching structure, duplicate policy, and bounds on path length.

If every expanded state has at most (b) successors and the shallowest solution occurs at depth (d), breadth-first search can generate on the order of (b^d) states. This expression describes the dominant exponential dependence rather than an exact count, because repeated states and irregular branching alter the realized graph. Depth-first search can avoid storing an entire frontier of that size, although it may examine branches whose depth greatly exceeds (d).

For heuristic methods, the effective branching factor (b^\ast) is defined implicitly from the number of expanded nodes (N) by a relation of the form

[ N+1=1+b^\ast+(b^\ast)^2+\cdots+(b^\ast)^d. ]

It summarizes observed growth over a particular problem distribution but does not constitute an intrinsic constant of an algorithm. Changes in heuristic quality or state representation can alter the effective branching factor while leaving the underlying transition rules unchanged.

Memory is frequently the limiting resource because conventional best-first search retains both a frontier and a duplicate-detection structure. Iterative deepening A* replaces a large stored frontier with repeated depth-first traversals bounded by an (f)-cost threshold. Recursive best-first search retains a linear-size recursion path and backs up alternative cost estimates, trading additional regeneration for reduced storage. These methods preserve specific optimality properties under admissibility conditions while changing the distribution of computational work.

Relation to planning and games

In classical automated planning, a state describes the facts currently true, and an action specifies preconditions together with its effects. Forward state-space planning begins at the initial state and applies actions until the goal formula is satisfied. Regression planning instead transforms the goal description backward through actions, producing conditions that predecessor states must satisfy.

Search in game trees also operates over states and transitions, but the objective incorporates decisions by multiple agents. Algorithms such as minimax assign values according to alternating control rather than treating every transition as a freely selectable action. The conceptual connection remains the incremental exploration of an implicit configuration space, while the evaluation semantics differ from those of single-agent shortest-path search.

Nondeterministic and probabilistic transitions require further extensions because an action can lead to several possible successor states. A policy then maps encountered states to actions rather than specifying only one path from an initial state to a goal. This formulation connects state-space methods with Markov decision processes and contingent planning.