Beam search is an informed, non-exhaustive search technique that expands promising nodes while retaining only a fixed number of states. Its beam width w controls how many candidates survive at each level, reducing memory compared with breadth-first search but allowing promising routes to be discarded. section 4.1 section 4.3.2
At each iteration, beam search:
- Generates neighboring states for every route in the current beam. section 4.3.2
- Combines those children with the current candidates, ranks them using a heuristic or cost, and keeps the best w states. section 4.3.2
- Repeats until the beam stops changing or reaches a goal, optionally using a beam threshold to avoid expensive sorting. section 4.3.2
- Trades completeness and possible optimality for lower memory use; wider beams explore more alternatives but require more computation. section 4.3.2 section 4.4.2
Routing from S to G
On a small weighted graph, a beam width of w = 2 keeps two states after each expansion and can produce the route S-A-C-E-G. A larger beam or more generated children increases the chance of finding a near-optimal route, while smaller settings improve processing time. section 4.3.2 section 4.4.2
Algorithm 4.3 The beam search algorithm
Inputs: A source node, a destination node, and beam width w Output: A route from source to destination Initialize Seen ← nil Initialize beam ← random w routes from source to destination Add beam to seen Initialize pool ← children of routes in the beam with consideration of seen + beam Initialize last_beam ← nil While beam is not last_beam do Update last_beam ← beam Update beam ← the best w routes from pool If last_beam == beam then break Add beam to seen Update pool ← children of routes in the beam + beam Return optimal route in beam
Use the pseudocode to trace initialization, child generation, candidate selection, duplicate tracking, and termination. section 4.3.2
