Beam search is a search heuristic that reduces the memory complexity of best-first search at the expense of optimality. Recall that best-first search visits all successor states to the current state, assigns them a score based on a global measure of optimality, and then proceeds from the highest-scoring state observed so far. Beam search constrains this process by pruning all branches but those leading to the highest-scoring