此算法是不完备算法，仅适用于随机数据或想不出其它更好的方法时骗分。
目录： 一、Beam Search算法简介例题 1
二、Beam Search算法框架 三、适用范围+例题例题 2
例题 3
四、算法小结一、Beam Search 算法简介
Beam Search 算法在OI界并不出名，但是在 IT 界是一个很重要的算法。
奥地利符号计算研究所（Research Institute for Symbolic Computation，简称RISC）的 Christoph Koutschan 博士曾经与其它计算机科学家一起投票选举出计算机科学中最重要的32个算法，其中便有这个 Beam Search 算法。
维基百科的解释如下：
Beam Search（集束搜索）是一种启发式图搜索算法，通常用在图的解空间比较大的情况下，为了减少搜索所占用的空间和时间，在每一步深度扩展的时候，剪掉一些质量比较差的结点，保留下一些质量较高的结点。这样减少了空间消耗，并提高了时间效率。
大意就是说 Beam Search 算法是一种基于贪心的启发式搜索，目的是寻找全局最优解。
Beam Search 算法的每一次扩展深度一般分为三部分：
-
路径搜索：是指在受限空间中检索出所有下一步可行路径。
-
路径评估：是指对某一条路径进行评估打分。
-
状态转移：将所有路径评估完成后，只选用较优的。
而 Beam Search 的关键就是贪心，即“选用较优的”。
对于每个 Beam Search 函数，都有一个配套的 Beam Width（集束宽度），这个宽度决定了每次状态转移时保留的较优状态个数，也决定了程序的正确性和运行效率，所以 Beam Search 算法没有固定的时间复杂度。
为了方便理解，来举一个例子（例子的原题是【HDU 6981】Rise in Price，我在别的博客写过该题的Beam Search题解）。
例题1:问：在下面两个正方形矩阵中，从左上角沿最短路线走到右下角，每个矩阵获得的收益和之积最大是多少？
1 6 7 5 3 1 7 4 1 begin{matrix} 1 & 6 & 7\ 5 & 3 & 1 \ 7 & 4 & 1 end{matrix} 157634711
1 5 1 4 2 6 7 3 1 begin{matrix} 1 & 5 & 1\ 4 & 2 & 6 \ 7 & 3 & 1 end{matrix} 147523161
先说正确答案：
路径为这样：
↓ × × ↓ × × → → → begin{matrix} ↓ & × & ×\ ↓ & × & × \ → & → & → end{matrix} ↓↓→××→××→
矩阵 1 1 1 的收益和为 1 + 5 + 7 + 4 + 1 = 18 1+5+7+4+1=18 1+5+7+4+1=18。
矩阵 2 2 2 的收益和为 1 + 4 + 7 + 3 + 1 = 16 1+4+7+3+1=16 1+4+7+3+1=16.
收益和的乘积为 18 × 16 = 288 18 times 16=288 18×16=288，可以证明这是最佳答案。
在说 Beam Search 正解之前，先尝试用纯爆搜和纯贪心做这个题。
纯爆搜：对于每一个点都有走下和走右两种情况（边界点除外），枚举所有路径的时间复杂度约为 O ( 2 n × n ) O(2^{n times n}) O(2n×n)，其中 n n n 为矩阵边长，题面已知 n ≤ 100 n leq 100 n≤100。这样做的话最坏情况要走的路径条数约为 2 10000 2^{10000} 210000条，肯定是会超时的。
纯贪心：贪心策略无非就两种，前一个矩阵或后一个每次走到当前点的右边和下边（假设有的话）值更大的那一个，然后另一个矩阵跟着走这一步，记录下两个矩阵中当前路径的收益和，最后相乘即为答案。这相当于是假设局部最优等于全局最优，这连样例都过不去，因为这样贪心的路径如下：
- 当在前一个矩阵贪心地走，路径如下：
→ → → × × ↓ × × ↓ begin{matrix} → & → & →\ × & × & ↓ \× & × & ↓ end{matrix} →××→××→↓↓
矩阵 1 1 1 的收益和为 1 + 6 + 7 + 1 + 1 = 16 1+6+7+1+1=16 1+6+7+1+1=16。
矩阵 2 2 2 的收益和为 1 + 5 + 1 + 6 + 1 = 14 1+5+1+6+1=14 1+5+1+6+1=14.
收益和的乘积为 16 × 14 = 224 16 times 14=224 16×14=224，显然不是正解。
- 当在后一个矩阵贪心地走，路径如下：
→ → × × ↓ × × → → begin{matrix} → & → & ×\ × & ↓ & × \× & → & → end{matrix} →××→↓→××→
矩阵 1 1 1 的收益和为 1 + 6 + 3 + 4 + 1 = 15 1+6+3+4+1=15 1+6+3+4+1=15。
矩阵 2 2 2 的收益和为 1 + 5 + 2 + 3 + 1 = 12 1+5+2+3+1=12 1+5+2+3+1=12.
收益和的乘积为 15 × 12 = 180 15 times 12=180 15×12=180，显然更不是正解。
综上，纯贪心和纯暴力都不可做此题。
此题正解其实是 dp，但也是一道很好的 Beam Search 题。
还记得维基百科里对 Beam Search 的介绍吗？综合爆搜和贪心，就是 Beam Search。
将此题矩阵的每个点 ( x , y ) (x,y) (x,y) 和 终点为 ( x , y ) (x,y) (x,y) 的一条路径的 a a a 矩阵收益和 S a Sa Sa， b b b 矩阵收益和 S b Sb Sb 设为一个状态,评估值即为 S a × S b Satimes Sb Sa×Sb。
每次转移时将当前这一步的评估值排序，取每个点的前 Beam Width 个评估值代表的路径状态，并加入到下一轮的预备状态集合中。
最后答案为每个 ( x , y ) (x,y) (x,y) 为右下角坐标的状态的评估值的最大值
状态设定很好理解，就是题面给的信息，评估值也很好理解，就是题目要求的值，问题是 Beam Width 该如何设定？定小了，答案错误；定大了，超出时间限制。
其实可以把这道题抽象成凸包问题，反正最后得到的结论是 Beam Width 的期望值在 50 50 50 左右，但平常情况下没必要推导出一个精确值，大多数情况下开 2 N 2sqrt N 2N 就足够了，具体情况具体调整，建议能取多大取多大。
二、Beam Search算法框架 初始化：状态设定：
struct STATE
{
//状态 （包括评估值）
};
vectorBEAM;//记录状态
宽度设定：
const int MAXB=所需宽度;
评估值排序：
bool operator < (STATE x,STATE y)
{
return x.评估值
函数内部（伪代码）
int Beam_Search()
{
BEAM.push_back(初始状态)//将题目给定的初始状态加入当前状态集合中
while(BEAM.size())//一直重复转移状态直到状态枚举完成
{
priority_queueq;//堆记录维护可到达状态的前MAXB大
for(当前BEAM的每一个状态)
{
如果当前状态为最终状态，将当前状态的评估值作为最终答案的备选，取其中最优解。
否则：
for(当前状态能到达的下一个状态)
q.push(下一个状态);
}
BEAM.clear()//当前状态用完，转而记录下一个状态
while(!q.empty()&&BEAM.size()<=MAXB)//限制宽度
{
BEAM.push_back(q.top());
q.pop();
}
}
返回最终答案最优解。
}
三、适用范围+例题
适用范围：
程序正确性与集束宽度的大小成正比，而集束宽度的大小也与程序运行效率成正比，所以集束宽度往往不能保证所有数据
100
%
100 %
100% 正确，但大概率是对的。
Beam Search 算法往往适用于数据范围小的题，以及数据随机的题，且题目需要求的是能够评估价值的东西，而不是求数量等不能评估价值的问题。
例题2：P3371 【模板】单源最短路径（弱化版）
题目思路：状态为节点编号，评估值为当前状态从源点开始到当前节点的路径长度，显然路径长度越小评估值越优，所以要用小根堆维护评估值。其余做法就是套算法框架。
Beam Search代码如下：
struct STATE
{
int x;
long long dis;
STATE(int x_,long long dis_){
x=x_;
dis=dis_;
}
};
bool operator > (STATE x,STATE y)
{
return x.dis>y.dis;
}
void BEAM_SEARCH(int u)
{
BEAM.clear();
BEAM.push_back(STATE(u,0));
while(BEAM.size()>0)
{
priority_queue,greater >q;
for(register int i=0;i
例题3：P1004 [NOIP2000 提高组] 方格取数
题目思路：跟最开始那道例题很像，不过这里不需要求积，却涉及到一个点的值只能加一次的问题。
此时的集束宽度需要限制的是对于每个点的每个估价值的路径状态个数，因为状态涉及到不同估价值和不同位置，所以用map离散化来维护。
之前走过的点可以用一个数组记录，因为数据范围小，所以每个状态都包含一个这样的数组记录已经取过的值。
本题需要跑两遍 Beam Search 算法，一次从
(
1
,
1
)
(1,1)
(1,1) 走到
(
n
,
n
)
(n,n)
(n,n)，保留下到
(
n
,
n
)
(n,n)
(n,n) 的方案，再从
(
n
,
n
)
(n,n)
(n,n) 走回
(
1
,
1
)
(1,1)
(1,1)。
两次Beam Search有一点小差别，具体差别见代码。
全代码如下：
#include
#include
#include
#include
