beam search

An optimisation of the best first search graph search

algorithm where only a predetermined number of paths are

kept as candidates. The number of paths is the "width of the

beam". If more paths than this are generated, the worst paths

are discarded. This reduces the space requirements of best

first search.