Informed search

Beam Search

Keep only the best k options at each level and race ahead.

Interactive demo coming soon — read the theory below

The idea

Beam Search is a greedy, memory-thrifty cousin of best-first search. Instead of tracking every possible path, it expands the frontier one level at a time, scores all the new nodes with a heuristic (a smart guess of how close each is to the goal), then keeps only the best k of them and throws everything else away. That fixed number k is called the beam width. Because it never carries more than k nodes forward, it is fast and uses little memory, but that same aggressive pruning is why it can miss the goal entirely and rarely finds the cheapest path.

How it works

Start with the start node in your beam (the beam is your OPEN list of at most k nodes to explore next).
Expand every node currently in the beam: generate all of their neighbouring nodes for the next level.
Score each of these new nodes with the heuristic h(n), your estimate of how far each node is from the goal.
If any of them is the goal, stop and report success with the path that reached it.
Sort all the newly generated nodes by their score, best first.
Keep only the top k nodes; discard all the rest permanently (this is the pruning step, and the discarded nodes are gone for good).
Move the kept nodes into the CLOSED list as visited, and make them the new beam.
Repeat from step 2 until the goal is found, the beam becomes empty, or you hit a depth limit.

OPEN, CLOSED & the data structures

A beam: a list of at most k nodes to expand next (this plays the role of the OPEN list, but capped at size k). A CLOSED/visited set so you do not re-expand nodes and loop forever. A heuristic function h(n) that scores each node. A parent pointer or stored path per node so you can reconstruct the route once the goal is reached. The single tuning knob is k, the beam width.

Pseudocode

function BeamSearch(start, goal, k):
    beam = [start]                 # OPEN list, capped at k
    closed = {start}               # visited nodes
    while beam is not empty:
        candidates = []
        for node in beam:          # expand this whole level
            for child in neighbours(node):
                if child == goal:
                    return path_to(child)   # success
                if child not in closed:
                    candidates.add(child)
                    closed.add(child)
        sort candidates by h(child)  ascending   # best (closest) first
        beam = first k of candidates             # keep k, discard the rest
    return failure                  # beam emptied, goal never found

At a glance

Complete?No, incomplete. Even when a solution exists, pruning to k nodes can permanently discard the only branch that led to the goal, so the search can dead-end with an empty beam and report failure.

Optimal?No, not optimal. It follows heuristic scores greedily and keeps only k candidates, so it has no mechanism to guarantee the cheapest or shortest path; it returns the first goal it stumbles into, if any.

TimeO(b * k * d) roughly, where b is the branching factor, k the beam width, and d the depth of the solution. Each level expands at most k nodes into about b*k candidates, and there are d levels, so it is fast and grows linearly with depth rather than exploding.

SpaceO(k) for the beam (plus O(k*d) if you store the full path to each node). Only a fixed number of nodes are ever held in memory, which is the whole selling point over full best-first search.

👍 When to use it

The search space is huge and full best-first search or A* would run out of memory.
You need a good-enough answer fast and can accept that it might not be the best one.
You have a decent heuristic that reliably points toward promising nodes.
Machine translation and speech recognition decoding, where beam search picks the top-k most likely sentences at each word.
Any setting where memory is tight and you would rather risk missing the optimum than store everything.

⚠️ Watch out for

Pruning is permanent: once a node is dropped from the beam it is never reconsidered, so the path to the goal can be thrown away.
It is neither complete nor optimal, so never rely on it when you must find a solution or the best one.
Beam width k is a trade-off: small k is fast but misses more; large k is safer but uses more memory and edges toward ordinary best-first search (k = infinity behaves like full best-first).
It only compares nodes at the same level against each other, so a slightly worse node now that leads to a great path later gets pruned.
Answer quality depends heavily on the heuristic; a misleading heuristic makes the pruning throw away exactly the wrong nodes.