Beam Search

Beam a heuristic search method. It used for decoding in many areas including in Machine Translation and speech recognition.

Basic Algorithm

The pseudocode for beam search is:

Start: CURRENT.STATES := initial.state

while(not CONTAINS_GOAL(CURRENT.STATES)) do

CANDIDATE.STATES := NEXT(CURRENT.STATES)

SCORE(CANDIDATE.STATES)

CURRENT.STATES := PRUNE(CANDIDATE.STATES)

CONTAINS_GOAL is a function that determines whether the goal state has been reached. SCORE uses a heuristic function to score states. PRUNE selects the best states to keep.

Stack-Based Beam Search

The candidate states are often organized into stacks. (This is a poor use of the word "stack", it is really just a list.) The pseudocode for this varient of beam search is:

Start: CURRENT.STATES := initial.state, STACKS := empty

while(not CONTAINS_GOAL(CURRENT.STATES)) do

EXPAND_STATES(CURRENT.STATES, STACKS)

CANDIDATE.STATES := NEXT(CURRENT.STATES)

SCORE(CANDIDATE.STATES)

CURRENT.STATES := PRUNE(CANDIDATE.STATES)

When NEXT is called, .