Local search

Local Beam Search

Search with a team of k explorers who share their best leads.

Interactive demo coming soon — read the theory below

The idea

Local Beam Search keeps track of k candidate solutions at once instead of just one. Each round, it generates every neighbor (successor) of all k candidates, pools them together, and keeps only the best k to carry into the next round. The trick is that the survivors are chosen from the whole pool, so a candidate sitting near a promising area can "recruit" search effort away from weaker candidates.

How it works

Start by creating k states (candidate solutions), usually chosen at random.
Generate all successors (neighboring states) of all k current states, pooling them into one big set.
If any successor is a goal or good enough, stop and return it.
Score every successor in the pool with an evaluation (heuristic) function.
Select the best k successors from the entire pool, no matter which parent they came from.
Make those best k the new current states, discarding everything else.
Repeat from step 2 until you reach a goal, stop improving, or hit a time/step limit.

OPEN, CLOSED & the data structures

A set of k current states (the \"beam\"), and each round a temporary pool holding all successors of those k states together with their evaluation-function scores. No path history or frontier of unexpanded nodes is kept — only the current k states carry over, so memory stays small and fixed.

Pseudocode

function LocalBeamSearch(k):
    current ← k randomly generated states
    loop:
        pool ← empty list
        for each state s in current:
            add all successors of s to pool
        if any state g in pool is a goal:
            return g
        sort pool by evaluation score (best first)
        current ← the best k states in pool
        if current has not improved over last round:
            return best state in current   // stuck

At a glance

Complete?Not complete. Like other local search, it explores neighbors without keeping a full frontier, so it can get stuck at a local peak and never find a solution that exists elsewhere.

Optimal?Not optimal (not guaranteed to find the global best). Keeping k states and pooling successors makes it more robust than a single-state search, but it still climbs toward whatever high ground is nearby and can settle for a local optimum.

TimeDepends on how many rounds run and the branching factor b: each round evaluates about k*b successors, so cost is roughly O(rounds * k * b). No general bound on rounds.

SpaceO(k * b) — you only hold k current states plus their pooled successors for one round. Memory is small and does not grow over time.

👍 When to use it

You want more robustness than a single-state hill climb but still need low, fixed memory
Evaluating states is cheap and you can afford to expand k of them each round
A single search too often gets trapped, and you want good candidates to reinforce each other
The problem is a big optimization/search where any good-enough state is acceptable, not the provably best one

⚠️ Watch out for

It is NOT the same as k random restarts: there the k searches run independently, but here the shared selection lets good states pull effort toward them.
Loss of diversity: the k states can drift toward the same region and clump together, effectively wasting k on one spot.
When clumping happens it behaves almost like a single expensive hill climb, losing the benefit of running k searches.
Still gets stuck at local optima — bigger k helps but gives no guarantee.
Stochastic beam search (picking successors with probability weighted by score, not strictly the top k) is a common fix for the diversity problem.