Beam search
From Wikipedia, the free encyclopedia
Beam search is a heuristic search algorithm that is an optimization of best-first search. Like best-first search, it uses a heuristic function to estimate the promise of each node it examines. Beam search, however, only unfolds the first m most promising nodes at each depth, where m is a fixed number, the "beam width."
While beam search is space-bounded as a function of m, it is neither optimal nor complete while m is finite. As m increases, beam search approaches the functionality of best-first search.
Initially m random states are chosen. The successors of these m states are all calculated. If the Goal Node is reached, the algorithm halts. Else the best m states of these successors are taken and the steps repeated.
