Issues in Search Techniques: How Search Fails

Combinatorial explosion, cycles and redundant paths, local maxima, plateaux and ridges, inadmissible and inconsistent heuristics, and the four classic design questions — with a diagnostic table for telling which failure you are actually looking at.

Every algorithm on these pages is a page of pseudocode that works perfectly on the example. What nobody writes down is the list of ways it fails on your problem — and those failures look alike from the outside. Your search hangs. Was it a cycle, an explosion, or a plateau? Your search returns an answer that’s worse than one you found by hand. Was the heuristic inadmissible, or did you stop at the wrong moment?

This page is that list. Each failure gets its cause, its symptom, and its fix.

The failure map

1. Combinatorial explosion

The base failure, and the one you can’t engineer around — only avoid.

A search tree with branching factor $b$ and depth $d$ has $O(b^d)$ nodes. Adding one level multiplies the work by $b$ . That’s not a constant factor you can win back with better code.

Problem	$b$	Depth for a hard instance	Nodes
8-puzzle	~2.7	31	10¹³ without pruning
15-puzzle	~3	80	10³⁸
Chess	~35	80 plies	10¹²³
Go	~250	150	10³⁶⁰
TSP, 20 cities	—	—	6 × 10¹⁶ tours

The only real responses, in order of how much they buy you:

Change the representation. Going from “choose 8 of 64 squares” to “a permutation” cut N-queens by 110,000× before a single line of search ran. Always try this first — it’s free.
Add a heuristic. Manhattan distance on the 8-puzzle cuts a depth-24 search from 127,931 nodes to 1,660, a factor of 77.
Prune provably. Alpha-beta on tic-tac-toe cuts 549,946 nodes to 18,297 with an identical answer. Branch-and-bound does the same for TSP.
Give up on optimality. Nearest-neighbour + 2-opt gets within ~5% of the best TSP tour in $O(n^2)$ . Five percent today beats optimal in two years.

The diagnostic: print your frontier size every 1,000 expansions. If it is growing roughly geometrically, you have an explosion and no amount of micro-optimisation will save you — you need one of the four above.

2. Cycles and redundant paths

Two different problems that people lump together.

A cycle is a path that returns to a state it already contains: A → B → A. Without a check, DFS follows one forever. This is what makes the search never terminate.

A redundant path is a different route to the same state: A → B → D and A → C → D. It terminates, but you do the work below D twice — and that subtree is where all the nodes are.

The fix for both is the explored set from graph search — but the cost differs, and so does what you can get away with:

Situation	Minimum you need
The space is a genuine tree (no repeats possible)	nothing
Cycles exist, memory is tight	check only the current path (what iterative deepening does)
Cycles exist, memory is fine	a full `visited` set
Costs vary (UCS, A*)	`best_g[state]` — a plain set is wrong, see below

The classic mistake. In BFS, mark a state visited when you push it, not when you pop it. Marking on pop lets the same state be queued dozens of times before its first expansion, and your memory blows up for no reason. In A*, the opposite: you must let a state back in if you reach it more cheaply.

3. The local search failures: maxima, plateaux and ridges

Hill climbing keeps only the current state and moves to a better neighbour. It uses no memory and scales to a million variables — and it fails in three distinct ways, which look identical from inside the loop.

Local maximum

Every neighbour is worse, but you’re not at the global best. Hill climbing halts and reports success. This is the failure people mean when they say hill climbing “gets stuck”.

Fixes: random-restart hill climbing (run it 20 times from random starts, keep the best); simulated annealing (accept a worse move with probability $e^{-\Delta/T}$ , cooling $T$ over time); beam search (keep the best $k$ states rather than one).

Plateau

A flat region: every neighbour scores the same. There’s no gradient to follow, so the search has no information about which way to go. A shoulder is a plateau with an uphill exit somewhere along it; a flat local maximum has none.

Fix: allow sideways moves — accept equal-scoring neighbours — but cap them, or you’ll loop on a flat maximum forever. Measured over 2,000 random 8-queens starts:

Sideways moves allowed	Solved	Mean steps
0	13.8%	4.2
up to 100	94.0%	23.0

Seven times the success rate for five times the steps — an outstanding trade.

But it only works with random tie-breaking. If you always take the first best-scoring neighbour, sideways moves just oscillate between two equal states until the cap trips, and the success rate lands at about 32% instead of 94%. The fix is one line: collect every neighbour tied for the best score and random.choice among them. This is the sort of detail that silently costs you two-thirds of an algorithm’s value.

Ridge

The nastiest. The landscape rises along a diagonal, but your operators only move along the axes. Every single-axis move steps off the ridge and downhill, so you oscillate from side to side making almost no upward progress.

Fix: this is an operator problem, not a search problem. Add compound moves that change two variables at once, or use a method that estimates a direction (gradient methods, or 2-opt style paired swaps in TSP).

import random, math

def hill_climb(initial, neighbours, score, max_sideways=100):
    """Returns (state, why_it_stopped). `score` is to be MAXIMISED."""
    current, sideways = initial, 0
    while True:
        cands = list(neighbours(current))
        if not cands:
            return current, 'no neighbours'
        best_score = max(score(c) for c in cands)
        # random tie-breaking is NOT optional — see the note above
        best = random.choice([c for c in cands if score(c) == best_score])

        if best_score < score(current):
            return current, 'local maximum'
        if best_score == score(current):
            sideways += 1
            if sideways > max_sideways:
                return current, 'plateau (sideways limit hit)'
        else:
            sideways = 0
        current = best


def simulated_annealing(initial, neighbours, score, T0=1.0, cooling=0.997):
    """Escapes local maxima by sometimes accepting a worse state."""
    current, best, T = initial, initial, T0
    while T > 1e-4:
        nxt = random.choice(list(neighbours(current)))
        delta = score(nxt) - score(current)
        if delta > 0 or random.random() < math.exp(delta / T):
            current = nxt
            if score(current) > score(best):
                best = current
        T *= cooling
    return best

Why annealing works. At high $T$ , $e^{-\Delta/T} \approx 1$ and you accept almost anything — a random walk that explores freely. As $T \to 0$ you accept only improvements — pure hill climbing. The schedule anneals from one to the other. With a slow enough cooling schedule it provably finds the global optimum; “slow enough” is usually slower than you can afford, which is why annealing is a good heuristic rather than a guarantee.

4. Heuristic failures

A heuristic can be wrong in two specific ways, and they have different symptoms.

Inadmissible: overestimates, so A* returns a suboptimal path

$h(n)$ is admissible if it never exceeds the true remaining cost. Break that and A* can pop a goal while a cheaper path is still in the frontier — because that cheaper path’s inflated $f$ pushed it behind.

Symptom: A* returns a path, it looks plausible, and it’s quietly worse than the best one. Nothing crashes.

The diagnostic — run this once on small instances:

def check_admissible(states, h, true_cost):
    """true_cost(s) = exact optimal cost from s (get it from BFS/UCS)."""
    bad = [(s, h(s), true_cost(s)) for s in states if h(s) > true_cost(s)]
    for s, hv, tv in bad[:10]:
        print(f'INADMISSIBLE at {s}: h={hv} > true={tv}')
    return not bad

The reliable way to get admissibility: derive $h$ by relaxing the problem — remove a constraint, solve the easier version exactly, use that cost. Relaxation provably yields an admissible heuristic. Manhattan distance is “let tiles pass through each other”; the MST bound for TSP is “you need to connect the remaining cities somehow”. Guessed heuristics are where inadmissibility creeps in.

Inconsistent: valid answer, wasted work

$h$ is consistent (monotonic) if $h(n) \le c(n, n') + h(n')$ for every edge. Consistency implies admissibility but is stronger.

With an inconsistent-but-admissible heuristic, A* still returns the optimal path — but it may re-expand nodes it already closed, because a cheaper route to them shows up later. In the worst case that’s exponential re-expansion.

Property	Guarantees	Violating it costs you
Admissible	optimal solution	correctness
Consistent	no node is re-expanded	time

If you use a plain closed set (never revisiting), an inconsistent heuristic costs you correctness too. That’s the trap in the note on graph search.

And the third heuristic failure: it’s admissible but useless

$h(n) = 0$ is perfectly admissible. It’s also just Dijkstra. A heuristic that always returns a tiny number is safe and does nothing.

The measure worth tracking is the effective branching factor $b^*$ — the branching factor a uniform tree would need to hold $N$ generated nodes at depth $d$ :

$N = 1 + b^* + (b^*)^2 + \dots + (b^*)^d$

Measured on the 8-puzzle (12 random boards at each of depths 12, 16, 20, 24):

Heuristic	$b^*$	Reading
none (uninformed)	~2.7	the raw branching factor
misplaced tiles, h₁	1.43	real pruning
Manhattan, h₂	1.25	near-perfect

A $b^*$ close to 1 means the search walks nearly straight to the goal; close to $b$ means the heuristic is doing nothing. The gap between 1.43 and 1.25 looks small and isn’t — it compounds over depth, which is exactly the 77× runtime difference at depth 24.

This is also the number that tells you a heuristic is worth improving. If $b^*$ is already 1.05, spend your time elsewhere.

5. Stopping at the wrong moment

A short section for a bug that produces confident wrong answers.

# WRONG for uniform-cost search and A*
for child in expand(node):
    if goal_test(child.state):
        return child            # <-- a cheaper goal may still be in the frontier
    frontier.push(child)

# RIGHT
node = frontier.pop()
if goal_test(node.state):       # <-- pop order guarantees minimum f
    return node

Testing on generation is correct for BFS with uniform step costs — the first goal you generate is at the shallowest depth. It is wrong the moment costs vary, because a goal generated early can be expensive while a cheaper one sits in the frontier waiting.

The general rule: a node’s value is only proven when you pop it. Everything in the frontier is still a guess.

6. The four design questions

Beyond the failure modes, four choices shape any search program. These are the classic “issues in the design of search programs”.

Which direction do you search?

Direction	When it wins
Forward (start → goal)	Few start states, many goal states; goals are described by a predicate
Backward (goal → start)	One explicit goal, many possible starts; you can compute predecessors
Bidirectional	One of each, reversible operators, and memory to spare

The rule of thumb is to search in the direction with the lower branching factor. Medical diagnosis runs backward (few diseases, many symptom combinations); a maze runs forward. Backward search needs $\text{PREDECESSORS}(s)$ , and for many problems — block world, most planning — that’s much harder to compute than successors.

How do you pick which rule to apply?

With six production rules you loop over all of them. With ten thousand, matching becomes the bottleneck, and you need indexing — the RETE algorithm was invented precisely for this and still runs production-rule engines today. The other half of the question is conflict resolution: when several rules match, which fires? By specificity, by recency, by an explicit priority?

How do you represent a node?

The trade-off is memory versus recomputation. Store the full state (fast comparisons, lots of memory) or store a delta from the parent (tiny, but you replay to reconstruct). Chess engines store an incremental Zobrist hash rather than the board. And whatever you choose, it must be hashable if you want an explored set — which is why every state on this site is a tuple or a frozenset, never a list.

What do you do at a dead end?

Chronological backtracking (undo the most recent choice) is simple and often wasteful — the real culprit may be twelve decisions back. Backjumping and conflict-directed backjumping jump straight to the decision that caused the failure. On constraint problems this is frequently an order-of-magnitude win, and it’s the idea that grew into clause learning in modern SAT solvers.

The diagnostic checklist

When a search misbehaves, work down this list in order — it’s roughly sorted by how often each one is the actual cause:

Is the goal test a predicate or an equality? If the real goal is partial, state == goal never fires.
Are states hashable and compared by value? A list, or a class without __eq__/__hash__, makes every visited-set lookup miss.
Are you marking visited on push or on pop? Push for BFS; best_g for A*.
Are the preconditions on your operators complete? A missing bounds check generates states that look plausible and aren’t reachable.
Is the heuristic admissible? Test it against exact costs on small instances.
Are you testing the goal on pop, for anything cost-based?
Is the frontier growing geometrically? Then it’s explosion, not a bug.
Does a solution exist at all? 4 missionaries and 4 cannibals with a two-seat boat has none; so does 3 gallons from a 4- and 6-gallon jug. Handle the “searched everything, found nothing” case explicitly instead of assuming a path exists.

Point 8 is worth dwelling on. A search that exhausts its frontier and returns None is not necessarily broken — it may be correctly telling you the problem is unsolvable. Where you can settle that question analytically, do it before searching: one gcd call decides every water-jug instance, and one parity check decides every 8-puzzle.

Where to go next

State Space Search — the formal machinery these failures break
Problem Solving with AI — the gentler introduction
The 8-Puzzle — admissibility and heuristic strength, measured
4-Queens and 8-Queens — local search and min-conflicts in practice
Travelling Salesman — combinatorial explosion, and living with it