# Artificial Intelligence/Search/Heuristic search/Beam search

## Definition

Beam search is a restricted, or modified, version of either a breadth-first search or a best-first search. It is restricted in the sense that the amount of memory available for storing the set of alternative search nodes is limited, and in the sense that non-promising nodes can be pruned at any step in the search (Zhang, 1999). The pruning of non-promising nodes is determined by problem-specific heuristics (Zhang, 1999). The set of most promising, or best alternative, search nodes is called the “beam” (Xu and Fern, 2007). Essentially, beam search is a forward-pruning, heuristic search.

## Search Components and Algorithm

A beam search takes three components as its input: a problem to be solved, a set of heuristic rules for pruning, and a memory with a limited available capacity (Zhang, 1999). The problem is the problem to be solved, usually represented as a graph, and contains a set of nodes in which one or more of the nodes represents a goal. The set of heuristic rules are rules specific to the problem domain and prune unfavourable nodes from the memory in respect to the problem domain. The memory is where the “beam” is stored, where when memory is full and a node is to be added to the beam, the most costly node will be deleted, such that the memory limit is not exceeded.

The following algorithm for a beam search, as a modified best-first search, is adapted from Zhang’s 1999:

``````beamSearch(problemSet, ruleSet, memorySize)
openMemory = new memory of size memorySize
nodeList = problemSet.listOfNodes
node = root or initial search node
while (node is not a goal node)
Delete node from openMemory;
Expand node and obtain its children, evaluate those children;
If a child node is pruned according to a rule in ruleSet, delete it;
Place remaining, non-pruned children into openMemory;
If memory is full and has no room for new nodes, remove the worst
node, determined by ruleSet, in openMemory;
node = the least costly node in openMemory;
```
```