Difference between revisions of "Beam Search"
From Cohen Courses
Jump to navigationJump to search| Line 5: | Line 5: | ||
Start: CURRENT.STATES := initial.state | Start: CURRENT.STATES := initial.state | ||
| − | :while(not | + | :while(not ''CONTAINS_GOAL''(CURRENT.STATES)) do |
| − | ::CANDIDATE.STATES := NEXT | + | ::CANDIDATE.STATES := ''NEXT''(CURRENT.STATES) |
| + | ::''SCORE''(CANDIDATE.STATES) | ||
| + | ::CURRENT.STATES := ''PRUNE''(CANDIDATE.STATES) | ||
Revision as of 01:11, 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)
