学步园

1. Introduction

Beam search is a heuristic search algorithm that is an optimization of best-first search that reduces its memory requirement. Best-first search is a graph search which orders all partial solutions (states) according to some heuristic which attempts to predict how close a partial solution is to a complete solution (goal state). In beam search, only a predetermined number of best partial solutions are kept as candidates.

2. Example

  A basic form of local search

  currentState = initial state<br /> while currentState does not satisfiy goal test and time<br /> limit is not exceedd<br /> {<br /> successors = the successors of the currentState<br /> currentState = the number of successor with the highest promise(i.e. its heuristic<br /> value is lowest)<br /> }<br /> if currentState satisfies goal test<br /> {<br /> return path of actions that led to the currentState<br /> }<br /> else<br /> { return failure<br /> }</p> <p>

  Hill-climbing algorithm is another example of local beam search

3. Conclusion

Reference:http://en.wikipedia.org/wiki/Beam_search