简介

Beam Search（集束搜索）是一种启发式图搜索算法，通常用在图的解空间比较大的情况下，为了减少搜索所占用的空间和时间，在每一步深度扩展的时候，剪掉一些质量比较差的结点，保留下一些质量较高的结点。这样减少了空间消耗，并提高了时间效率，但缺点就是有可能存在潜在的最佳方案被丢弃，因此，Beam Search算法是不完全的，一般用于解空间较大的系统中。

该算法常用的场景如：机器翻译，语音识别，当系统的数据集比较大，计算资源受限，而且没有唯一最优解时，该算法能够较快的找到接近最正确的解。

背景知识

广度优先搜索算法(Breadth First Search)，又称为"宽度优先搜索"或"横向优先搜索"，简称BFS，它是一种先生成的节点先扩展的搜索策略，其具体的搜索过程：从初始节点S开始逐层向下扩展，在第n层节点还没有完全搜索完之前，不会进入第n+1层节点进行搜索。

流程如下图：

图1、BFS算法流程

第1步：访问A。

第2步：依次访问C,D,F。

在访问了A之后，接下来访问A的邻接点。前面已经说过，在本文实现中，顶点ABCDEFG按照顺序存储的，C在"D和F"的前面，因此，先访问C。再访问完C之后，再依次访问D,F。

第3步：依次访问B,G。

在第2步访问完C,D,F之后，再依次访问它们的邻接点。首先访问C的邻接点B，再访问F的邻接点G。

第4步：访问E。

在第3步访问完B,G之后，再依次访问它们的邻接点。只有G有邻接点E，因此访问G的邻接点E。

因此访问顺序是：A -> C -> D -> F -> B -> G -> E

流程

beam search可以看做是做了约束优化的广度优先搜索，首先使用广度优先策略建立搜索树，树的每层，按照启发代价对节点进行排序，然后仅留下预先确定的个数（Beam width-集束宽度）的节点，仅这些节点在下一层次继续扩展，其他节点被剪切掉。

1、将初始节点插入到list中，

2、将给节点出堆，如果该节点是目标节点，则算法结束；

3、否则扩展该节点，取集束宽度的节点入堆。然后到第二步继续循环。

4、算法结束的条件是找到最优解或者堆为空。

在使用上，集束宽度可以是预先约定的，也可以是变化的，具体可以根据实际场景调整设定。

算法实现

/*初始化 */

g = 0;//步数

hash_table = { start };//hash表，用于标记所有已经访问过的节点。类似于close表

BEAM = { start };//BEAM 一个容量受限的open表，也就是在初始化时，需要指定open表的容量

while(BEAM ≠ ∅){// 循环直到BEAM为空，也就是没有需要考察的节点了

SET = ∅;// 设置集合为空

for(each state in BEAM){ //对于BEAM中的每个状态state

for(each successor of state){ // 对于state的每个后继successor

if(successor == goal) return g + 1;// 如果后继就是目标节点，那么找到了一个路径。

SET = SET ∪ { successor }; // 否则，后继加入到集合中

}

}//for

BEAM = ∅; // 因为open表中的内容已经处理完毕，清空open表

g = g + 1; // 又访问了一层

/* fill the BEAM for the next loop */

while((SET ≠ ∅) AND (B > |BEAM|)){ // 集合不空并且open表没有满 BEAM是容量为B的open表

state = successor in SET with smallest h value; //从集合中选出最好的点 h参考备注1

SET = SET \ { state }; // 从集合中删除该节点

if(state ∉ hash_table){ // 该状态还没有考察过 则state不在hash_table中

if(hash_table is full) return ∞; // hash表满了 算法已经没法执行下去 当然没能找到路径

hash_table = hash_table ∪ { state }; //state已经考虑过 添加到hash_table中

BEAM = BEAM ∪ { state }; //state添加到BEAM中等待判断

}//if

}//while

// 注意 有可能集合不空 但是BEAM已经满了

// 根据算法 集合会被清空 集合中的点将不再考虑

// 因此该算法不是完备的

// 也就是说 有可能原问题有解，但是由于这里舍弃了一些中间过程

// 导致最终无法获得解

}//while

// goal was not found, and BEAM is empty - Beam Search failed to find the goal

return ∞;//没能找到路径