简介
Beam Search（集束搜索）是一种启发式图搜索算法，通常用在图的解空间比较大的情况下，为了减少搜索所占用的空间和时间，在每一步深度扩展的时候，剪掉一些质量比较差的结点，保留下一些质量较高的结点。这样减少了空间消耗，并提高了时间效率，但缺点就是有可能存在潜在的最佳方案被丢弃，因此，Beam Search算法是不完全的，一般用于解空间较大的系统中。
该算法常用的场景如：机器翻译，语音识别，当系统的数据集比较大，计算资源受限，而且没有唯一最优解时，该算法能够较快的找到接近最正确的解。
背景知识
广度优先搜索算法(Breadth First Search)，又称为"宽度优先搜索"或"横向优先搜索"，简称BFS，它是一种先生成的节点先扩展的搜索策略，其具体的搜索过程：从初始节点S开始逐层向下扩展，在第n层节点还没有完全搜索完之前，不会进入第n+1层节点进行搜索。
流程如下图：
第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 ∞;//没能找到路径
