beam search


beam search

An optimisation of the best first search graph searchalgorithm where only a predetermined number of paths arekept as candidates. The number of paths is the "width of thebeam". If more paths than this are generated, the worst pathsare discarded. This reduces the space requirements of bestfirst search.