Beam Search
From Cohen Courses
Beam a heuristic search method. It used for decoding in many areas including in Machine Translation and speech recognition.
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 tells whether the goal state has been reached. SCORE uses a heuristic function to score states. PRUNE selects the best states to keep.
