人工智慧/搜尋/啟發式搜尋/束搜尋
束搜尋是 廣度優先搜尋 或 最佳優先搜尋 的一個限制性或修改版本。它之所以受限，是因為可用於儲存一組備選搜尋節點的可用記憶體量有限，以及因為在搜尋的任何步驟中都可以修剪掉無希望的節點（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