Difference between revisions of "Beam Search"
From Cohen Courses
Jump to navigationJump to search| Line 3: | Line 3: | ||
== Algorithm == | == Algorithm == | ||
The pseudocode for beam search is: | The pseudocode for beam search is: | ||
| + | |||
Start: CURRENT.STATES := initial.state | 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. | ||
Revision as of 01:18, 2 November 2011
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.
