Search Algorithms

Definition: Search algorithms are systematic procedures for finding a path or solution through a problem space — a set of states connected by actions — by exploring candidate states in some order until a goal is reached. They form the backbone of classical (pre-deep-learning) AI: every puzzle solver, route planner, and game-playing engine before the deep learning era was, at its core, a search algorithm plus a clever way to prioritize which states to expand next. The field splits into uninformed search (no domain knowledge, just the problem’s structure), informed search (guided by a heuristic estimate of remaining cost), and adversarial search (accounting for an opponent’s moves). Despite the rise of learned models, the underlying idea — represent a problem as states and transitions, then explore that graph intelligently — still governs how modern planners, LLM agents, and game engines decide what to do next.

How It Works

The field traces back to Newell and Simon’s General Problem Solver (1957) and Shakey the Robot at Stanford Research Institute, both of which framed intelligent behavior explicitly as search over a space of possible states. A* itself was published by Hart, Nilsson, and Raphael in 1968, and minimax dates back to game theory work by von Neumann decades earlier — this is one of the oldest continuously useful ideas in AI, not a passing technique.

The State-Space Formulation

Every search problem is defined by five components, and getting this formulation right is most of the work — a badly framed state space makes even the best algorithm useless.

Initial state — where the search begins
Actions — the finite set of moves available from any given state
Transition model — a function mapping (state, action) pairs to the resulting state
Goal test — a predicate that checks whether a given state counts as a solution
Path cost — a function assigning a numeric cost to any sequence of actions, used to compare solutions

Together these define a graph — nodes are states, edges are actions — and “solving” the problem means finding a path from the initial state to a goal state, ideally the cheapest one. Nearly every implementation shares the same generic loop, regardless of which strategy fills in the ordering:

function TREE-SEARCH(problem):
    frontier <- {problem.INITIAL-STATE}
    loop:
        if frontier is empty: return FAILURE
        node <- CHOOSE-AND-REMOVE(frontier)   # this line IS the algorithm
        if problem.GOAL-TEST(node.state): return SOLUTION(node)
        for each action in problem.ACTIONS(node.state):
            child <- CHILD-NODE(problem, node, action)
            frontier <- frontier + {child}

Everything that distinguishes BFS from DFS from A* from minimax lives in exactly one line of this loop: how CHOOSE-AND-REMOVE picks the next node. A FIFO queue gives BFS, a LIFO stack gives DFS, a priority queue on $g(n)$ gives uniform-cost search, and a priority queue on $g(n) + h(n)$ gives A*.

Worked example — formalizing the 8-puzzle: a state is any arrangement of the eight numbered tiles and one blank on a 3x3 grid; the initial state is the specific shuffled arrangement given; actions are “slide the blank up/down/left/right” (fewer near edges and corners); the transition model swaps the blank with the adjacent tile; the goal test checks for the tiles in numerical order; and path cost is simply the number of slides made. This tiny formalization is enough to hand the problem to any of the algorithms below without further modification. The full state space has $9! = 362{,}880$ permutations of the nine positions, but only half of those, $181{,}440$ , are actually reachable from any given start — a useful reminder that a state space’s theoretical size and its reachable size are frequently very different numbers.

Search Trees vs. Search Graphs

The pseudocode above hides an important design choice: whether CHOOSE-AND-REMOVE and node expansion ever check for repeated states.

Tree search expands nodes with no memory of states visited before. It’s simpler and uses less bookkeeping, but on any state space with cycles or multiple paths to the same state, it can re-explore the same subtree endlessly or blow up combinatorially re-deriving states it has already seen.
Graph search adds the explored set: before expanding a node, check whether its state has already been visited, and skip it if so. This guarantees termination on finite graphs and avoids redundant work, at the cost of memory to store every visited state (typically a hash set for $O(1)$ lookup).
Almost every practical implementation uses graph search — the 8-puzzle, road networks, and game boards all have many paths converging on the same state, so tree search would waste enormous effort re-deriving positions it already knows about.
The tradeoff resurfaces in memory-constrained variants like IDA*, which deliberately falls back toward tree-search behavior (no persistent explored set) specifically to keep memory linear in search depth.

Uninformed strategies have no information about which unexpanded state is closer to the goal — they rely purely on the graph’s structure.

Breadth-first search (BFS): the frontier is a FIFO queue, so nodes are expanded in order of increasing depth — level by level. BFS is complete (it finds a solution if one exists, given a finite branching factor) and optimal when all step costs are equal, but memory is its downfall: it must hold the entire frontier at depth $d$ , which grows as $O(b^d)$ for branching factor $b$ .
Depth-first search (DFS): the frontier is a LIFO stack, so the algorithm plunges down one branch before backtracking. Memory use is only $O(bm)$ for maximum depth $m$ — far cheaper than BFS — but DFS is neither complete (it can loop forever down an infinite or cyclic branch) nor optimal (it returns the first solution found, not the cheapest).
Uniform-cost search (UCS): the frontier is a priority queue ordered by cumulative path cost $g(n)$ . This is Dijkstra’s algorithm in disguise — complete and optimal whenever step costs are non-negative, and it generalizes BFS to weighted graphs.
Depth-limited search: plain DFS with a fixed cutoff depth $\ell$ , refusing to expand any node beyond that limit. It trades completeness (a solution deeper than $\ell$ will never be found) for a guaranteed-terminating, memory-bounded search — and it’s the exact building block that iterative deepening repeats with a growing $\ell$ .
Iterative deepening DFS (IDDFS): runs depth-limited search repeatedly with an increasing depth limit (0, 1, 2, …), discarding each attempt that fails. It sounds wasteful, but the repeated shallow levels are cheap compared to the deepest level, so IDDFS gets BFS’s completeness and optimality (for uniform costs) with DFS’s linear memory footprint — the standard choice when the state space is huge and solution depth is unknown.
Bidirectional search: runs two simultaneous searches — one forward from the initial state, one backward from the goal — and stops when their frontiers meet. If both directions use BFS, the cost drops from $O(b^d)$ to roughly $O(b^{d/2})$ each, a dramatic saving, though it requires the goal state to be known explicitly and the actions to be reversible.

Here is a tiny search tree, with the exploration order for two of these strategies:

BFS expansion order:   A  B  C  D  E  F  G  H
DFS expansion order:   A  B  E  F  C  D  G  H

BFS finishes each depth level before moving deeper, so it reaches every depth-1 node (B, C, D) before touching any depth-2 node. DFS instead commits to the leftmost branch (A -> B -> E) before ever looking at C or D — it only discovers the goal H after exhausting B’s whole subtree.

Informed (Heuristic) Search

Informed search adds a heuristic function $h(n)$ : an estimate of the cost from node $n$ to the nearest goal. A good heuristic turns a blind crawl through the state space into a directed hunt.

Greedy best-first search expands whichever frontier node has the lowest $h(n)$ , ignoring how much it already cost to get there. It’s fast in practice but neither complete nor optimal — a misleading heuristic can send it down a dead end or a needlessly long path.
A* search expands the node minimizing the evaluation function $f(n) = g(n) + h(n)$ , where $g(n)$ is the cost already paid and $h(n)$ is the estimated cost remaining. This balances UCS’s guarantee of optimality with greedy search’s speed.

A* is optimal provided $h(n)$ is admissible — it never overestimates the true remaining cost:

h(n) \le h^{*}(n)

and, for graph search, consistent — it satisfies a triangle inequality along every edge:

h(n) \le c(n, a, n') + h(n')

Consistency implies admissibility and guarantees that once A* expands a node, it has found the optimal cost to reach it, so no node ever needs re-expansion.

Proof sketch — why admissibility guarantees optimality: suppose A* terminates by returning a suboptimal goal $G_2$ while a cheaper goal $G$ exists. Some node $n$ on the optimal path to $G$ must still be sitting in the frontier when $G_2$ is chosen. Because $h$ is admissible, $f(n) = g(n) + h(n) \le g(n) + h^{*}(n) = \text{cost}(G) < \text{cost}(G_2) = f(G_2)$ . A* always expands the lowest- $f$ frontier node next, so it would have expanded $n$ — and eventually reached $G$ — before ever selecting $G_2$ . The contradiction is what makes A*‘s optimality a proof rather than an empirical observation.

Iterative-deepening A* (IDA*) replaces A*‘s memory-hungry priority queue with repeated depth-first passes bounded by an increasing $f$ -cost threshold, giving A*-quality solutions with DFS-level memory use — the standard choice for large puzzles like the 15-puzzle or Rubik’s Cube.
Weighted A* multiplies the heuristic by a factor greater than one ( $f(n) = g(n) + w \cdot h(n)$ , $w > 1$ ), sacrificing strict optimality for substantially faster search — common in time-constrained robotics planning where “good enough, fast” beats “perfect, slow.”
Dominance between heuristics: if $h_2(n) \ge h_1(n)$ for every node while both remain admissible, $h_2$ is said to dominate $h_1$ and will never expand more nodes — which is why combining several admissible heuristics with $h(n) = \max(h_1(n), h_2(n), \ldots)$ is a common, always-safe way to strengthen a search.
Classic heuristic examples: straight-line (Euclidean) distance for road-network routing, Manhattan distance for grid-based puzzles, and the count of misplaced tiles or sum of tile distances for the 8-puzzle.

Worked example — why the heuristic matters: for a puzzle with branching factor $b = 10$ and a solution 12 steps deep, uninformed BFS explores on the order of $10^{12}$ nodes in the worst case. A heuristic that’s even modestly informative can cut the effective branching factor to around 2, shrinking the search to roughly $2^{12} \approx 4{,}096$ nodes — the difference between a search that never finishes and one that returns instantly.

Heuristic Design: Relaxed Problems and Pattern Databases

Good heuristics don’t come from guesswork — two systematic techniques dominate how they’re actually built.

Relaxed problems derive a heuristic by solving a simplified version of the original where some constraint is removed — dropping the “one tile at a time” rule in the 8-puzzle gives Manhattan distance, and dropping the adjacency requirement entirely gives the count of misplaced tiles. The exact solution cost of a relaxed problem is always admissible for the original, because removing a constraint can only make the problem easier, never harder.
Pattern databases precompute exact solution costs for a sub-problem — for instance, moving just four of the eight tiles into place — and store the results in a lookup table. At search time, a table lookup gives a far tighter admissible heuristic than any formula, at the price of upfront memory and precomputation.
Landmark heuristics, used heavily in production route planning, precompute shortest-path distances from every node to a small set of fixed “landmark” points, then combine those distances with the triangle inequality to derive a tight, fast admissible bound for any query — part of what makes continent-scale mapping services return routes in milliseconds.
A heuristic doesn’t need to be perfect to be useful. It needs to stay admissible, for correctness, and get as close to the true remaining cost as is computationally affordable, for speed — the entire heuristic-design literature is a search for that balance.

Adversarial and Stochastic Search

When another agent is actively working against you, search must account for their moves too. The minimax value of a node is defined recursively:

\text{minimax}(n) = \begin{cases} \text{Utility}(n) & n \text{ is terminal} \\ \max_{s \in \text{Successors}(n)} \text{minimax}(s) & n \text{ is a MAX node} \\ \min_{s \in \text{Successors}(n)} \text{minimax}(s) & n \text{ is a MIN node} \end{cases}

Minimax builds a game tree alternating between a maximizing player and a minimizing player, and backs up values from the leaves using the recursion above. It’s complete and optimal for finite, fully observable, zero-sum games — but the tree size is $O(b^m)$ , which is intractable for anything beyond trivial depth in games like chess, whose branching factor of roughly 35 already makes a full-depth search of a 40-move game utterly infeasible without pruning.
Alpha-beta pruning cuts branches of the minimax tree that cannot possibly influence the final decision, without changing the result. With good move ordering it reduces the effective branching factor from $b$ to roughly $\sqrt{b}$ , doubling the depth reachable in the same time budget — the single most important optimization in classical game AI.
The horizon effect and quiescence search: cutting a search off at a fixed depth can miss an important tactical sequence — a forced capture or checkmate — sitting just past the cutoff. Production chess engines counter this with quiescence search, selectively extending the search at “noisy” positions (captures, checks) rather than applying a uniform depth limit everywhere.
Expectimax replaces the minimizing player with a chance node (a weighted average over outcomes), used for games with randomness like backgammon or dice-based board games, where the opponent isn’t adversarial but probabilistic.
Monte Carlo Tree Search (MCTS) abandons exhaustive expansion in favor of repeated random rollouts, cycling through four phases each iteration:

Phase	What Happens
Selection	Walk down the tree from the root, picking children by a formula like UCB1 that balances exploring untried moves against exploiting known-good ones
Expansion	Add one new child node to the tree at the point selection stopped
Simulation	Play out a fast, often random policy from the new node to a terminal state
Backpropagation	Push the simulation’s result back up every node on the path, updating visit counts and win-rate estimates

The UCB1 selection rule balances exploration and exploitation explicitly:

UCB1 = \bar{X}_i + C\sqrt{\frac{\ln N}{n_i}}

where $\bar{X}_i$ is the average result from child $i$ , $n_i$ is how many times it’s been visited, $N$ is the parent’s total visit count, and $C$ tunes how much untried moves get favored. MCTS scales to enormous game trees (Go’s branching factor of roughly 250 defeats plain minimax) and is the search backbone behind AlphaGo and its successors, paired with a learned neural network evaluator instead of pure random rollouts.

Constraint Satisfaction as Backtracking Search

A large family of problems — Sudoku, scheduling, map coloring, resource allocation — aren’t framed as “reach a goal state” but as “assign a value to every variable without violating any constraint.” These are solved with a specialized search variant rather than generic tree search.

Backtracking search assigns variables one at a time, checking constraints as it goes, and backtracks (undoes the last assignment and tries a different value) the moment a constraint is violated — far more efficient than generating every full assignment and checking it at the end.
Forward checking looks ahead after each assignment, eliminating values from neighboring unassigned variables that would immediately violate a constraint, catching failures earlier than plain backtracking would.
Arc consistency (the AC-3 algorithm) goes further, propagating constraints between every pair of connected variables until no more values can be eliminated, which can shrink the search space dramatically before any guessing even starts.
Variable and value ordering heuristics — such as choosing the most constrained variable next, or trying the least constraining value first — dramatically affect practical performance even though they don’t change the worst-case complexity, mirroring the role a good heuristic plays in A*.
Sudoku is the most familiar consumer-facing example: each empty cell is a variable, the digits 1-9 form its domain, and the row, column, and 3x3-box rules are the constraints. Backtracking combined with forward checking solves the overwhelming majority of published puzzles in well under a second.
Constraint satisfaction search shares the same frontier/backtrack machinery as classical state-space search, just with a different notion of “state” (a partial variable assignment rather than a position in a maze or puzzle).

Local Search: Optimizing Without Tracking a Path

For problems where only the final state matters — not the path taken to reach it, the classic examples being N-queens or the traveling salesman problem — a different family applies. Local search operates on a single current state and moves to neighboring states, using far less memory than the frontier-based algorithms above because it never keeps a full frontier or explored set.

Hill climbing always moves to the best neighboring state, stopping when no neighbor improves on the current one. It’s simple and memory-light — $O(1)$ beyond the current state — but it gets stuck at local maxima, plateaus, and ridges, since any improvement requiring a temporary step backward is invisible to it.
Random-restart hill climbing reruns plain hill climbing from many different random starting states and keeps the best result found overall — a crude but often surprisingly effective way to dodge the local-optimum problem without any of simulated annealing’s schedule tuning.
Simulated annealing escapes local maxima by occasionally accepting a worse move, with the probability of accepting a bad move decreasing over time along a “temperature” schedule.
Local beam search keeps $k$ states in parallel instead of one, generating all their neighbors at each step and retaining only the best $k$ overall — useful information effectively passes between the parallel searches, since a promising region attracts more of the $k$ slots over time.
Genetic algorithms maintain a population of states, combine pairs through crossover, apply random mutation, and select survivors by fitness — a local search variant borrowing an explicit biological metaphor, well suited to search spaces too irregular for a clean heuristic to guide directly.
Tabu search augments hill climbing with a short-term memory of recently visited states, forbidding moves back into them for a fixed number of steps — a deterministic alternative to simulated annealing’s randomness for escaping local optima and avoiding cycles.
None of these algorithms track a path or guarantee completeness or optimality; they trade those classical guarantees for the ability to operate in enormous or continuous state spaces where maintaining an explicit frontier is simply infeasible.

The acceptance probability behind simulated annealing is what makes it more than “hill climbing plus noise.” For a move that worsens the objective by $\Delta E$ :

P(\text{accept}) = e^{-\Delta E / T}

where $T$ is the current temperature. Early on, with high $T$ , the search behaves almost randomly and explores broadly; as $T$ cools, it increasingly resembles hill climbing, exploiting the best region found so far.

Worked example — hill climbing vs. simulated annealing on N-queens: placing eight queens on a chessboard so none attack another has $92$ solutions out of roughly $4.4$ billion possible arrangements. Hill climbing, started from a random placement and minimizing the number of attacking pairs, converges fast but stalls on a plateau or local minimum in a large fraction of runs — for instance, seven queens correctly placed with the eighth stuck in a position that any single move only makes worse. Simulated annealing, started from the same random placement, occasionally accepts a move that temporarily increases the number of attacking pairs, which is exactly what lets it climb out of that eighth-queen trap and reach a true zero-conflict solution — the same underlying search problem, solved or not solved, purely as a function of whether the algorithm is allowed to move downhill on purpose.

Online Search and Incremental Replanning

Not every search happens once, offline, against a fully known environment — robots, real-time strategy games, and live traffic routing all need to keep re-planning as the world changes underneath them.

Online search interleaves computation and action: the agent takes a step, observes the actual outcome (which may differ from what the transition model predicted), and re-plans from its new position rather than computing one giant plan upfront and executing it blindly.
Incremental replanning algorithms like D* Lite and Lifelong Planning A* (LPA*) avoid recomputing an entire search from scratch after each change to the environment; instead they reuse most of the previous search tree and repair only the parts affected by new information, which is dramatically cheaper than a fresh A* run on every update.
This is precisely the technique the warehouse robot in the closing example relies on, and the same one a GPS app uses to reroute around a newly reported accident without freezing the screen for a full recomputation across the entire map.

Why It Matters

Foundational to the AI curriculum — search is typically the first topic in any AI course because nearly every later topic (planning, constraint satisfaction, game playing, even reinforcement learning) is a specialization or relaxation of the search framework.
Powers real-time navigation — every turn-by-turn GPS system computes shortest paths over a road-network graph using A*-family algorithms, updated continuously against live traffic data.
Underlies competitive game AI — Deep Blue’s chess victory over Kasparov ran on minimax with alpha-beta pruning and hand-tuned evaluation; MCTS plus deep networks later cracked Go, a game long considered too combinatorially vast for search alone.
Drives logistics and operations research — vehicle routing, warehouse robot dispatch, and airline crew scheduling are all large-scale search and optimization problems, often solved with heuristic search or its close cousins (branch-and-bound, beam search).
Sits inside network infrastructure — link-state routing protocols like OSPF compute shortest paths with Dijkstra’s algorithm (uninformed uniform-cost search) on every router, continuously, without anyone noticing.
Remains central to robotics motion planning — continuous-space planners (RRT, PRM) differ mechanically from discrete graph search but inherit the same frontier and explored-set logic, and the same completeness and optimality tradeoffs.
Gives AI systems provable guarantees — unlike many learned models, classical search algorithms come with mathematical guarantees (completeness, optimality, complexity bounds), which matters in safety-critical planning domains like aviation and surgical robotics.
Resurfaces inside modern LLM agents — tool-use planning, chain-of-thought branching, and multi-step reasoning pipelines are, structurally, search over a space of possible action or reasoning sequences, even when a neural network replaces the hand-coded heuristic.
Teaches the complexity intuition every engineer needs — branching factor, depth, and the exponential blowup of naive search are the same intuitions that explain why brute-forcing combinatorial problems (scheduling, SAT solving, cryptographic key spaces) fails at scale.
Trains the mental model behind constraint satisfaction — scheduling, resource allocation, and configuration problems are usually solved by backtracking search over partial assignments, a direct descendant of the same frontier and explored-set machinery.
Extends into large-scale optimization — simulated annealing and genetic algorithms, both local search variants, are workhorses in chip layout design, airline scheduling, and any optimization problem too large or irregular for exact methods to touch.
Underpins formal verification — SAT and SMT solving, a mature and heavily search-based technology, is what lets chip and safety-critical software vendors mathematically prove the absence of certain classes of bugs rather than merely testing for them.

Search Strategies Compared

Comparing algorithms requires four consistent yardsticks:

Completeness — is the algorithm guaranteed to find a solution if one exists?
Optimality — is the algorithm guaranteed to find the cheapest solution, not just any solution?
Time complexity — how many nodes get expanded in the worst case, usually expressed in terms of branching factor $b$ and depth $d$ or $m$ ?
Space complexity — how many nodes must be held in memory simultaneously?

Algorithm	Complete?	Optimal?	Time Complexity	Space Complexity	Typical Use
Breadth-first search	Yes (finite $b$ )	Yes, if uniform step cost	$O(b^d)$	$O(b^d)$	Shortest path in unweighted graphs, shallow solution depth
Depth-first search	No (infinite/cyclic spaces)	No	$O(b^m)$	$O(bm)$	Memory-constrained exploration, exhaustive enumeration
Uniform-cost search	Yes	Yes	$O(b^{1+\lfloor C^*/\epsilon\rfloor})$	Same as time	Weighted graphs with no heuristic available
Greedy best-first search	No	No	$O(b^m)$ worst case	$O(b^m)$	Fast approximate solutions when speed beats accuracy
A* search	Yes (admissible $h$ )	Yes (admissible/consistent $h$ )	Exponential worst case, near-linear with good $h$	$O(b^d)$	Route planning, puzzle solving, any problem with a decent heuristic
IDA* (iterative-deepening A*)	Yes (admissible $h$ )	Yes (admissible $h$ )	Similar to A* in practice, higher constant factor	$O(bd)$	Large puzzles where A*‘s memory use is prohibitive (15-puzzle, Rubik’s Cube)
Minimax (with alpha-beta)	Yes (finite tree)	Yes (optimal opponent)	$O(b^m)$ , $O(b^{m/2})$ with pruning	$O(bm)$	Two-player zero-sum games (chess, checkers)
Hill climbing	No (stops at local optima)	No	Problem-dependent, no formal bound	$O(1)$ beyond current state	Fast approximate solutions to large optimization problems
Simulated annealing	No in general (optimal in the limit with a slow-enough schedule)	Only guaranteed with an impractically slow cooling schedule	Problem-dependent, tunable via schedule	$O(1)$ beyond current state	Combinatorial optimization too large for exhaustive or exact methods
Monte Carlo Tree Search	No guarantee at finite iterations, converges in the limit	Converges to optimal in the limit	Anytime — quality improves with more simulations	$O(\text{tree size explored})$	Huge adversarial trees where minimax is infeasible (Go)

Note the recurring tradeoff: completeness and optimality cost memory and time, and every “cheap” strategy (DFS, greedy best-first) buys its speed by giving up one of those guarantees.

Worked Example: Nodes Explored at Increasing Depth

The exponential term $b^d$ is easy to state and easy to underestimate. For a modest branching factor of $b = 10$ , contrast blind search against A* with a heuristic informative enough to cut the effective branching factor to about 2:

Solution depth $d$	Uninformed BFS (worst case)	A* with a good heuristic (effective $b \approx 2$ )
2	100	4
4	10,000	16
6	1,000,000	64
8	100,000,000	256
10	10,000,000,000	1,024

A solution just eight moves deep can already mean a hundred million nodes for an uninformed search — which is precisely why real systems lean so heavily on heuristics, pruning, and bidirectional search rather than brute force. The gap between the two columns is the entire economic case for informed search.

Search Algorithms in the Age of LLM Agents

Classical search didn’t disappear when neural networks took over — it moved up a level of abstraction, with the LLM supplying what used to be hand-coded transition and heuristic functions. The vocabulary maps almost one-to-one:

Classical Search Concept	LLM Agent Equivalent
State	A partial reasoning trace, plan, or “thought”
Successor function	One LLM generation step producing candidate next thoughts or actions
Frontier	The set of candidate thoughts kept alive (a beam, in beam search terms)
Heuristic $h(n)$	A self-evaluation score, learned verifier, or reward model rating a partial trace
Goal test	A check that the task is complete or the answer is verified correct
Path cost	Tokens generated, tool calls made, or wall-clock latency spent so far

Tree-of-thought prompting is literally a search algorithm layered on a language model. Each “thought” is a state, the LLM’s generation step is the successor function, and a scoring pass (self-evaluation or a separate verifier) plays the role of $h(n)$ , ranking or pruning branches — usually implemented as a breadth-limited best-first search over partial reasoning chains.
ReAct-style tool-use agents perform an online, incremental search over action sequences. At each step the agent expands the frontier by picking an API call or tool invocation, observes the result (the transition model made concrete), and decides whether to continue or backtrack — a direct rediscovery of online search, with a very expensive node-expansion cost (an LLM call and a real side effect).
Monte Carlo Tree Search still shows up directly, not just as inspiration. Reasoning and code-generation agents pair an LLM’s token-level proposal distribution with MCTS-style rollouts and the same UCB1-based selection rule shown above — the exact algorithm that powers AlphaGo — to search over candidate solutions before committing to a final answer.
Beam search, the default decoding algorithm for many sequence models, is bounded breadth-first search. It keeps only the $k$ best-scoring partial sequences at each generation step, trading BFS’s completeness guarantee for tractable memory — precisely the same width-limiting trick used in real-time pathfinding on large maps.
Multi-agent orchestration is parallel best-first search with a merge step. When a framework spins up several sub-agents to attempt a task differently and then picks the best result, it is running multiple frontiers concurrently and applying a heuristic (a scoring or voting function) to select among the final states — the same shape as parallel branch-and-bound.
The heuristic itself has been outsourced to the model. Where classical A* needed a hand-designed $h(n)$ , LLM-based planners often use the model’s own confidence score, a learned reward model, or a self-consistency vote as the heuristic — powerful, but without the admissibility guarantee that made A*‘s optimality proof possible in the first place.
Speculative decoding, used to speed up LLM inference itself, runs a small draft model ahead to propose several future tokens, which the large model then verifies in parallel and accepts or rejects — structurally the same pattern as expanding multiple frontier nodes at once and pruning the ones that don’t check out, a decades-old search idea reappearing inside the inference engine rather than the reasoning layer.

Comparison

Search is often confused with neighboring techniques that also involve “exploring” a space, but the mechanisms differ sharply.

Concept	What It Explores	How It Decides Where to Go	Guarantees
Search Algorithms	Discrete states in an explicitly modeled graph	A fixed rule (BFS/DFS order) or a heuristic function	Completeness/optimality provable for the algorithm class
Reinforcement Learning	An environment whose model is initially unknown	A policy learned from trial-and-error reward signals	Convergence guarantees under specific conditions, not per-episode optimality
Gradient Descent	A continuous parameter space	The local gradient of a differentiable loss function	Converges to a local (not necessarily global) optimum
Expert Systems	A fixed knowledge base of rules	Forward or backward chaining over if-then rules	Correct within the rules given, but brittle outside them

The key distinction: search assumes you already know the state space and transition model and just need to explore it efficiently; reinforcement learning assumes you don’t know the model and must learn a policy from experience; gradient descent operates over continuous, differentiable spaces rather than discrete states; and expert systems replace exploration with deductive rule-chaining over an explicit knowledge base.

Search and reinforcement learning are sometimes combined directly: model-based RL learns a transition model from experience and then runs planning (search) over that learned model, and MCTS-based systems like AlphaZero interleave both — search for immediate decisions, learning for long-run policy and value improvement.
Search and gradient descent share the word “search” colloquially, but the mechanics don’t transfer — you cannot take a gradient of a discrete state space, and you cannot backtrack a continuous loss landscape the way DFS backtracks a graph.
Expert systems can be reframed as search once the rule base grows large enough that finding a valid chain of rule applications becomes its own combinatorial problem, which is exactly what automated theorem provers and SAT solvers do.
Deciding which paradigm fits a new problem usually comes down to one question: is the transition model known and cheap to evaluate (use search), unknown and only learnable from interaction (use reinforcement learning), or continuous and differentiable (use gradient-based optimization)?
Local search variants (hill climbing, simulated annealing) are the closest classical search comes to gradient descent’s territory: both move step-by-step through a landscape toward better values using only local information. The difference is representation — gradient descent follows a continuous derivative through differentiable parameter space, while hill climbing evaluates discrete neighboring states one at a time with no derivative available at all.
Automated planning (PDDL-style AI planning) is a close cousin rather than a synonym: planning problems are usually compiled down into a search problem, but they factor the state description into explicit predicates instead of opaque states, which is what enables powerful domain-independent heuristics — the planning literature and the search literature share most of their theory but differ in representation.

Real-World Use Cases

Turn-by-turn GPS navigation (Google Maps, Waze) computing shortest or fastest routes over road-network graphs with A*/Dijkstra variants, re-run continuously against live traffic weights.
Video game NPC pathfinding — game engines like Unity and Unreal bake a navigation mesh and run A* over it every time a non-player character needs to cross a level.
Chess and checkers engines (Stockfish and its predecessors) combining alpha-beta-pruned minimax with hand-tuned or learned evaluation functions to search millions of positions per second.
Go and general game-playing AI (AlphaGo, AlphaZero, MuZero) pairing Monte Carlo Tree Search with deep neural network policy and value estimates to tame branching factors too large for classical minimax.
Warehouse and delivery robotics — automated guided vehicles and last-mile delivery routing (systems like UPS’s ORION) solve constrained shortest-path and vehicle-routing problems built on search and optimization.
Network packet routing — OSPF and similar link-state protocols compute shortest paths between routers using Dijkstra’s algorithm on every network topology change.
Puzzle solvers — Rubik’s Cube solvers (using IDA*, iterative-deepening A*) and sliding-tile puzzle apps rely on admissible heuristics like pattern databases to find optimal solutions in enormous state spaces.
Automated planning in logistics and manufacturing — job-shop scheduling and supply-chain optimization tools frame resource allocation as a search over the space of valid schedules, often via backtracking-style constraint satisfaction.
Compiler and query optimizers — SQL query planners search over the space of possible execution plans (join orders, index choices) using cost-based heuristics resembling A*.
Chip and circuit board layout (EDA tools) — place-and-route software uses simulated annealing to minimize wire length and congestion across millions of components, a problem far too large for exact search.
Staff and vehicle scheduling — timetabling and fleet-scheduling software uses genetic algorithms and local search to satisfy overlapping constraints that exact backtracking would take too long to solve.
LLM agent frameworks — tool-use planners, tree-of-thought reasoning pipelines, and code-generation agents that sample and rank multiple candidate solutions before returning one.
Formal verification — SAT and SMT solvers used to verify hardware designs and safety-critical software search over the space of variable assignments or proof steps to find a satisfying assignment or prove none exists.
Drug discovery and molecular design — computational chemistry pipelines use local search and genetic algorithms to explore enormous combinatorial spaces of candidate molecular structures for desirable binding or stability properties.

Common Pitfalls

Forgetting cycle/visited-state checks. Without an explored set, graph search can revisit the same state indefinitely, turning a solvable problem into an infinite loop — this is the single most common bug in hand-rolled search code.
Using an inadmissible heuristic with A*. If $h(n)$ ever overestimates the true remaining cost, A*‘s optimality guarantee is void — it can return a suboptimal path while still looking like it’s “working.”
Treating greedy best-first search as if it were optimal. It isn’t, by design: greedy search follows the heuristic blindly and can be lured into long detours or dead ends that a cost-aware algorithm would avoid.
Running plain DFS on unbounded or cyclic state spaces. Without a depth limit or cycle detection, DFS can descend forever down one branch and never even try the others — iterative deepening exists specifically to fix this.
Ignoring the memory blowup of BFS and A*. Both retain the entire frontier in memory; on large branching-factor problems this exhausts RAM long before it exhausts time, which is why memory-bounded variants (IDA*, SMA*) exist.
Skipping alpha-beta pruning, or using bad move ordering, in game search. Minimax without pruning is often computationally infeasible past a shallow depth, and pruning without good move ordering delivers far less benefit than expected.
Conflating “heuristic” with “learned.” Classical heuristics are typically hand-designed (straight-line distance, misplaced tiles) — using a heuristic doesn’t imply any machine learning is involved, though learned heuristics are an active research area.
Mishandling tie-breaking. When multiple frontier nodes have equal cost or heuristic value, an unspecified tie-breaking rule can make the algorithm’s output nondeterministic, which is dangerous when reproducibility matters (testing, debugging, benchmarking).
Applying discrete graph search to continuous spaces without adaptation. Robotics motion planning in continuous coordinates needs sampling-based methods (RRT, PRM) or discretization, not a naive port of grid-based A*.
Over-trusting search depth as a proxy for intelligence in adversarial search. A deeper but poorly evaluated game tree can lose to a shallower search with a better evaluation function — raw search depth is not the whole story.
Letting hill climbing run without restarts or randomization. A single hill-climbing run gets permanently stuck at whatever local optimum it first reaches — random-restart hill climbing or simulated annealing’s controlled randomness exists specifically to fix this failure mode.
Underestimating pattern database memory costs. A pattern database built too fine-grained can consume gigabytes of memory before search even starts, defeating the entire point of building an admissible heuristic to save time.
Assuming admissibility alone is enough once an explored set is involved. Admissibility guarantees optimality for tree search; graph search additionally needs consistency, or explicit logic to re-open a previously expanded node when a cheaper path to it is later discovered — an easy detail to lose when porting a tree-search implementation to use an explored set.

Example

A delivery robot in a multi-floor warehouse needs to move a package from its charging dock to a shelf on the far side of the building, weaving around aisles, other robots, and a temporarily blocked corridor. The warehouse’s control system models the floor as a graph: each grid cell is a state, moves to adjacent cells are actions, and the shelf location is the goal test. Rather than exploring blindly, the system runs A* with a Manhattan-distance heuristic — an admissible estimate, since diagonal shortcuts aren’t allowed and the true remaining distance can never be less than the straight grid distance. The frontier, a priority queue ordered by $f(n) = g(n) + h(n)$ , expands the most promising cells first, so the robot’s planner finds the optimal route without ever expanding the entire warehouse graph.

Midway through the route, a sensor reports the blocked corridor, invalidating part of the previously computed path. Rather than restart from scratch, the system re-runs A* from the robot’s current position with the corridor’s edge cost set to infinity, effectively removing it from the graph. Because A* is optimal and the heuristic is still admissible, the new plan is guaranteed to be the best available route given the updated map, not just a patch on the old one. This same pattern — incremental replanning over a graph with a cost-based heuristic — is what underlies every real-time GPS reroute after a traffic incident, showing how a decades-old algorithm still does the heavy lifting inside systems that look, from the outside, entirely modern.

A second, smaller example shows the same idea at game-tree scale: a tic-tac-toe engine given the board after four moves runs minimax on the roughly 30 remaining leaf positions, backing up win/draw/loss values from the bottom using the recursive rule above, and picks the move that guarantees at least a draw against optimal play. The state space is small enough that no pruning or heuristic is even necessary — a reminder that the fancier techniques above (A*, alpha-beta, MCTS) exist to manage scale, not to change what “search” fundamentally means.

A third example closes the loop back to the LLM-agent connection above: a coding agent asked to fix a failing test doesn’t just generate one patch. It generates several candidate patches (expanding the frontier), runs the test suite against each one (the goal test), and if none pass, feeds the failure output back into the model to generate the next round of candidates (re-expansion from the most promising failed attempt, exactly as A* re-expands from the lowest-cost frontier node). The “heuristic” ranking which patch to try first is the model’s own confidence, or a static-analysis score, standing in for the hand-coded $h(n)$ that guided A* through a road network sixty years earlier — same search shape, a vastly different node-expansion mechanism underneath it.

Referenced by

Dig deeper

Spot an error in this note?