Beam search

From Wikipedia, the free encyclopedia

You have new messages (last change).

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.

Comp Sci logo This computer science-related article is a stub. You can help Wikipedia by expanding it.
Retrieved from "http://en.wikipedia.org../../../b/e/a/Beam_search.html"