定义 Beam Search

Beam search 是一种启发式搜索算法，通过扩展一组有限的、最乐观的节点来探索图。Beam search 是 最佳优先搜索 的一种优化，它减少了内存需求。

Best-first search 是一种图搜索算法，它根据某种启发式方法对所有部分解进行排序。但在 Beam search 中，只保留预先确定的数量的最佳部分解作为候选。因此，它是一种 贪婪 算法。

Beam search 使用 广度优先搜索 来构建其搜索树。在树的每一层，它都会生成当前层所有状态的后继，并按启发式成本递增的顺序对它们进行排序。然而，它只存储每层预先确定的数量 (β) 的最佳状态，称为 束宽 (beamwidth)。只有这些状态会被进一步扩展。

束宽越大，剪枝的状态就越少。束宽为无穷大时，不会剪枝，Beam search 就等同于广度优先搜索。束宽限制了执行搜索所需的内存。由于目标节点可能被剪枝，Beam search 会牺牲完备性（保证算法在存在解的情况下能够终止并找到解）。Beam search 不是最优的，这意味着不能保证它会找到最佳解。

通常，Beam search 返回找到的第一个解。一旦达到配置的最大搜索深度（即翻译长度），算法将评估在不同深度搜索过程中找到的解，并返回概率最高的最佳解。

束宽可以是 固定的 或 可变的。一种使用可变束宽的方法是从最小宽度开始。如果没有找到解，则会拓宽束宽，然后重复该过程。

Beam Search 的组成部分

Beam search 接受三个组件作为输入：

1. 一个待解决的问题，
2. 一组用于剪枝的启发式规则，
3. 以及一个可用容量有限的内存。

问题是待解决的问题，通常表示为图，包含一组节点，其中一个或多个节点代表目标。启发式规则集是特定于问题域的规则，用于从内存中剪除与问题域相关的不利节点。

内存是存储 “束 (beam)” 的地方。当内存已满且要将一个节点添加到束中时，成本最高的节点将被删除，以确保不超过内存限制。

Beam Search 算法

以下 Beam Search 算法，作为一种修改后的最佳优先搜索，改编自张（1999）的研究。

Beam Search 的用途

Beam search 最常用于在内存不足以存储整个搜索树的大型系统中保持可处理性。例如，

• 它已被用于许多机器翻译系统。
• 每个部分都会被处理以选择最佳翻译，并且会出现许多不同的翻译方式。
• 根据它们的句子结构，会保留最佳的几个翻译，其余的会被丢弃。然后，翻译器会根据给定的标准评估翻译，选择最能达到目标的翻译。
• Beam search 的首次使用是在 Harpy Speech Recognition System，CMU 1976。

Beam Search 的缺点

以下是 Beam Search 的一个缺点及其示例：

• 总的来说，Beam Search 算法不是 完备的。尽管存在这些缺点，Beam search 在 语音识别、视觉、规划 和 机器学习 等实际领域取得了成功。
• Beam search 的主要缺点是搜索可能无法得到最优解，甚至可能在给定无限时间和内存的情况下，在存在从起始节点到目标节点的路径时也无法达到目标。
• Beam search 算法在两种情况下终止：达到所需的目标节点，或者未达到目标节点且没有剩余节点可供探索。
• 更准确的启发式函数和更大的束宽可以提高 Beam Search 找到目标节点的几率。

例如，我们取下面树图的 ß = 2。然后按照以下步骤找到目标节点：

步骤 1： OPEN= {A}

步骤 2： OPEN= {B, C}

步骤 3： OPEN= {D, E}

步骤 4： OPEN= {E}

步骤 5： OPEN= { }

开放集变为空，而没有找到目标节点。

注意：但当 ß = 3 时，算法成功找到了目标节点。

Beam Search 的最优性

Beam Search 算法在某些情况下不是完备的。因此，也不能保证其最优性。这可能是由于以下原因：

• 束宽和不准确的启发式函数可能导致算法错过最短路径的扩展。
• 更精确的启发式函数和更大的束宽可以使 Beam Search 更有可能找到通往目标的最佳路径。

例如，我们有一个具有启发式值的树，如下所示：

请按照以下步骤找到目标节点的路径：

步骤 1： OPEN= {A}

步骤 2： OPEN= {B, C}

步骤 3： OPEN= {C, E}

步骤 4： OPEN= {F, E}

步骤 5： OPEN= {G, E}

步骤 6： 找到目标节点 {G}，停止。

路径： A-> C-> F-> G

但 最优路径 是 A-> D-> G

Beam Search 的时间复杂度

Beam Search 算法的时间复杂度取决于以下因素：

• 启发式函数的准确性。
• 在最坏的情况下，启发式函数会将 Beam Search 引向搜索树的最深层。
• 最坏情况时间 = O(B*m)

B 是束宽，m 是搜索树中任何路径的最大深度。

Beam Search 的空间复杂度

Beam Search 算法的空间复杂度取决于以下因素：

• Beam Search 的内存消耗是其最吸引人的特性。
• 因为该算法在搜索树的每一层只存储 B 个节点。
• 最坏情况空间复杂度 = O(B*m)

B 是束宽，m 是搜索树中任何路径的最大深度。

• 这种线性的内存消耗使得 Beam Search 能够深入探测大型搜索空间，并可能找到其他算法无法达到的解。

Beam Search 的变体

通过将其与 深度优先搜索 相结合，Beam search 已变得完备，从而产生了 beam stack search 和 depth-first beam search。通过有限差异搜索，beam search 产生了有限差异回溯 (BULB)。

生成的搜索算法是任何时间算法（anytime algorithms），它们能快速找到合理的但可能不是最优的解，然后回溯并继续寻找改进的解，直到收敛到最优解。

在局部搜索的上下文中，我们将 局部束搜索 (local beam search) 称为一种特定算法，它从选择 β 个生成的开始状态。然后，对于搜索树的每一层，它总是从当前状态的所有可能后继中考虑 β 个新状态，直到达到目标。

由于局部束搜索经常陷入局部最优，一种标准的解决方案是以随机方式选择接下来的 β 个状态，其概率取决于状态的启发式评估。这种搜索称为 随机束搜索 (stochastic beam search)。

其他变体包括 灵活束搜索 (flexible beam search) 和恢复束搜索 (recovery beam search)。