人工智能/搜索/启发式搜索/束搜索
束搜索是 广度优先搜索 或 最佳优先搜索 的一个限制性或修改版本。它之所以受限，是因为可用于存储一组备选搜索节点的可用内存量有限，以及因为在搜索的任何步骤中都可以修剪掉无希望的节点（Zhang，1999）。对无希望节点的修剪由特定于问题的启发式方法确定（Zhang，1999）。最有可能或最佳备选搜索节点的集合被称为“束”（Xu and Fern，2007）。本质上，束搜索是一种前向修剪的启发式搜索。
束搜索以三个组件作为其输入：要解决的问题，一组用于修剪的启发式规则，以及具有有限可用容量的内存（Zhang，1999）。该问题是要解决的问题，通常表示为一个图，并且包含一组节点，其中一个或多个节点代表一个目标。启发式规则集是特定于问题域的规则，并且根据问题域从内存中修剪掉不利的节点。内存是“束”存储的地方，当内存已满并且要将节点添加到束中时，将删除成本最高的节点，以确保内存限制不会被超过。
以下作为修改后的最佳优先搜索的束搜索算法改编自 Zhang 的 1999 年研究
beamSearch(problemSet, ruleSet, memorySize)
openMemory = new memory of size memorySize
nodeList = problemSet.listOfNodes
node = root or initial search node
Add node to openMemory;
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;
束搜索具有可能减少搜索的计算量，从而减少搜索时间的优势（Xu and Fern，2007）。此外，搜索的内存消耗远小于其底层搜索方法（Furcy and Koenig）。这种潜在优势取决于用于修剪的启发式规则的准确性和有效性，并且由于需要对问题域的专业知识，因此获取此类规则可能有点困难（Zhang，1999）。束搜索的主要缺点是搜索可能不会产生最佳目标，甚至可能根本无法到达目标。事实上，束搜索算法在两种情况下终止：达到所需的目標节点，或者没有达到目标节点并且没有其他节点可供探索（Zhang，1999）。束搜索有可能是不完整的。尽管存在这些缺点，束搜索在语音识别、视觉、规划和机器学习等实际领域取得了成功（Zhang，1999）。
- Zhang, W. (1999). State-space search: Algorithms, complexity, extensions, and applications. Springer: New York.
- Xu, Y., Fern, A. (2007). On learning linear ranking functions for beam search. Retrieved on March 8, 2009, from http://www.machinelearning.org/proceedings/icml2007/papers/168.pdf
- Furcy, D., Koenig, S. Limited discrepancy beam search. Retrieved on March 8, 2009, from http://www.ijcai.org/papers/0596.pdf