浅谈玄学贪心搜索——Beam Search

观前提示:

此算法是不完备算法,仅适用于随机数据或想不出其它更好的方法时骗分。

目录:

一、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 n100。这样做的话最坏情况要走的路径条数约为 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 Sa\times Sb Sa×Sb

每次转移时将当前这一步的评估值排序,取每个点的前 Beam Width 个评估值代表的路径状态,并加入到下一轮的预备状态集合中。

最后答案为每个 ( x , y ) (x,y) (x,y) 为右下角坐标的状态的评估值的最大值

状态设定很好理解,就是题面给的信息,评估值也很好理解,就是题目要求的值,问题是 Beam Width 该如何设定?定小了,答案错误;定大了,超出时间限制。

其实可以把这道题抽象成凸包问题,反正最后得到的结论是 Beam Width 的期望值在 50 50 50 左右,但平常情况下没必要推导出一个精确值,大多数情况下 2 N 2\sqrt N 2N 就足够了,具体情况具体调整,建议能取多大取多大。

二、Beam Search算法框架

初始化:

状态设定:

struct STATE
{
	//状态 (包括评估值)
};
vector<STATE>BEAM;//记录状态

宽度设定:

const int MAXB=所需宽度; 

评估值排序:

bool operator < (STATE x,STATE y)
{
	return x.评估值<y.评估值;//这里的小于仅做参考
}

函数内部(伪代码)

int Beam_Search()
{
	BEAM.push_back(初始状态)//将题目给定的初始状态加入当前状态集合中
	while(BEAM.size())//一直重复转移状态直到状态枚举完成 
	{
		priority_queue<STATE>q;//堆记录维护可到达状态的前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<STATE,vector<STATE>,greater<STATE> >q;
		for(register int i=0;i<BEAM.size();++i)
		{
			int x=BEAM[i].x;
			long long dis=BEAM[i].dis;
			Min[x]=min(Min[x],dis);
			for(int i=elast[x];i;i=e[i].Next)
			{
				if(dis+e[i].Len<Min[e[i].y])
				q.push(STATE{e[i].y,dis+e[i].Len});
			}
		}
		int cnt=BEAM.size();
		BEAM.clear();
		while((!q.empty())&&BEAM.size()<=MAXB)
		{
				BEAM.push_back(q.top());
				q.pop();
		}
	}
}

例题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 <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN=10,MAXB=50;
int N;
struct STATE
{
	int x,y,val;
	bool Use[MAXN][MAXN];
	STATE(int x_,int y_,int val_,bool Use_[MAXN][MAXN]){
		x=x_;
		y=y_;
		val=val_;
		for(int i=1;i<=N;i++)
		{
			for(int j=1;j<=N;j++)
			{
				Use[i][j]=Use_[i][j];
			}
		}
		Use[x][y]=true;
	}
};
bool operator < (STATE x,STATE y)
{
	return x.val<y.val;
}

vector<STATE>BEAM;
int a[MAXN][MAXN];
int hash_table[MAXN*MAXN];
int BEAM_SEARCH(int step)
{
	map<int,int>Mp[MAXN][MAXN];
	if(step==1)
	{
		bool Use[MAXN][MAXN];
		memset(Use,0,sizeof(Use));
		Use[1][1]=true;	//初始化 
		BEAM.push_back(STATE(1,1,a[1][1],Use));
	}
	int Max=0;
	while(BEAM.size()>0)
	{
		priority_queue<STATE>q;
		bool flag=false;
		for(register int i=0;i<BEAM.size();++i)
		{
			int x=BEAM[i].x,y=BEAM[i].y;	
			if(x==1&&y==1&&step==2)
			{
				Max=max(Max,BEAM[i].val);
				continue;
			}
			if((x!=N||y!=N)&&step==1)//当状态全是(N,N)时说明已经跑完一次Beam Search算法了 
			{
				flag=true;
			}
			//搜索下一步能到的点 
			if(step==1)
			{
				if(y+1<=N&&Mp[x][y+1][BEAM[i].val+a[x][y+1]]<=MAXB)//限制状态数量,下同 
				{
					q.push(STATE(x,y+1,BEAM[i].val+a[x][y+1],BEAM[i].Use));
					Mp[x][y+1][BEAM[i].val+a[x][y+1]]++;
				}
				if(x+1<=N&&Mp[x+1][y][BEAM[i].val+a[x+1][y]]<+MAXB)
				{
					q.push(STATE(x+1,y,BEAM[i].val+a[x+1][y],BEAM[i].Use));
					Mp[x+1][y][BEAM[i].val+a[x+1][y]]++;
				}	
			}
			if(step==2)
			{
				if(y-1>=1&&Mp[x][y-1][BEAM[i].val+(BEAM[i].Use[x][y-1]==true?0:a[x][y-1])]<=MAXB)
				{
					q.push(STATE(x,y-1,BEAM[i].val+(BEAM[i].Use[x][y-1]==true?0:a[x][y-1]),BEAM[i].Use));//三元运算符处理当下一步节点被取过的情况,下同 
					Mp[x][y-1][BEAM[i].val+(BEAM[i].Use[x][y-1]==true?0:a[x][y-1])]++;
				}
				if(x-1>=1&&Mp[x-1][y][BEAM[i].val+(BEAM[i].Use[x-1][y]==true?0:a[x-1][y])]<=MAXB)
				{
					q.push(STATE(x-1,y,BEAM[i].val+(BEAM[i].Use[x-1][y]==true?0:a[x-1][y]),BEAM[i].Use));
					Mp[x-1][y][BEAM[i].val+(BEAM[i].Use[x-1][y]==true?0:a[x-1][y])]++;
				}
			}
		}
		if(flag==false&&step==1)
			return 0;
		BEAM.clear();
		while((!q.empty())&&BEAM.size()<MAXB*MAXB)//状态数限制为MAXB个,而每一个状态的个数也有MAXB个,所以BEAM的大小要小于MAXB*MAXB个 
		{
			BEAM.push_back(q.top());
			q.pop();
		}
	}
	return Max;
}

int main()
{
	cin>>N;
	while(true)
	{
		int x,y,z;
		cin>>x>>y>>z;
		if(x==0&&y==0&&z==0)
		break;
		a[x][y]=z;
	}
	BEAM_SEARCH(1);
	cout<<BEAM_SEARCH(2);
}

四、算法小结

综上来看,Beam Search 算法是一个替补算法,它不足够优秀导致没有题会专门考查它。

但是它却也足够优秀,因为它简单,好想,跑得也不慢。

在现实生活中很多求最优解的问题没有固定的算法,却都能用差不多 Beam Search 尽可能找出最优解。

比如百度百科中写道:“1976 年 Lowerre 在其称为 HARPY 的语音识别系统中第一次使用了集束搜索方法。他的目标是并行地搜索几个潜在的最优决策路径以减少回溯,并快速地获得一个解”,有时快往往比最优更有用。

如果在一场考试里有些题的正解思维难度太高,不妨尝试用Beam Search做做(假如能做),也许能得到比暴力分高得多的分。如果想保险,还可以再打一个暴力,根据数据点的梯度来分开使用者两种方法,这样只会赚不会亏。

最后如果文中有哪里写错了欢迎评论指出。

感谢阅读!!!

热门文章

暂无图片
编程学习 ·

exe4j详细使用教程(附下载安装链接)

一、exe4j介绍 ​ exe4j是一个帮助你集成Java应用程序到Windows操作环境的java可执行文件生成工具&#xff0c;无论这些应用是用于服务器&#xff0c;还是图形用户界面&#xff08;GUI&#xff09;或命令行的应用程序。如果你想在任务管理器中及Windows XP分组的用户友好任务栏…
暂无图片
编程学习 ·

AUTOSAR从入门到精通100讲(126)-浅谈车载充电系统通信方案

01 引言 本文深入研究车载充电系统策略,设计出一套基于电动汽车电池管理系统与车载充电机的CAN通信协议,可供电动汽车设计人员参考借鉴。 02 电动汽车充电系统通讯网络 电动汽车整车控制系统中采用的是CAN总线通信方式,由一个整车内部高速CAN网络、内部低速CAN网络和一个充电…
暂无图片
编程学习 ·

CMake(九):生成器表达式

当运行CMake时&#xff0c;开发人员倾向于认为它是一个简单的步骤&#xff0c;需要读取项目的CMakeLists.txt文件&#xff0c;并生成相关的特定于生成器的项目文件集(例如Visual Studio解决方案和项目文件&#xff0c;Xcode项目&#xff0c;Unix Makefiles或Ninja输入文件)。然…
暂无图片
编程学习 ·

47.第十章 网络协议和管理配置 -- 网络配置(八)

4.3.3 route 命令 路由表管理命令 路由表主要构成: Destination: 目标网络ID,表示可以到达的目标网络ID,0.0.0.0/0 表示所有未知网络,又称为默认路由,优先级最低Genmask:目标网络对应的netmaskIface: 到达对应网络,应该从当前主机哪个网卡发送出来Gateway: 到达非直连的网络,…
暂无图片
编程学习 ·

元宇宙技术基础

请看图&#xff1a; 1、通过AR、VR等交互技术提升游戏的沉浸感 回顾游戏的发展历程&#xff0c;沉浸感的提升一直是技术突破的主要方向。从《愤怒的小鸟》到CSGO,游戏建模方式从2D到3D的提升使游戏中的物体呈现立体感。玩家在游戏中可以只有切换视角&#xff0c;进而提升沉浸…
暂无图片
编程学习 ·

flink的伪分布式搭建

一 flink的伪分布式搭建 1.1 执行架构图 1.Flink程序需要提交给 Job Client2.Job Client将作业提交给 Job Manager3.Job Manager负责协调资源分配和作业执行。 资源分配完成后&#xff0c;任务将提交给相应的 Task Manage。4.Task Manager启动一个线程以开始执行。Task Manage…
暂无图片
编程学习 ·

十进制正整数与二进制字符串的转换(C++)

Function one&#xff1a; //十进制数字转成二进制字符串 string Binary(int x) {string s "";while(x){if(x % 2 0) s 0 s;else s 1 s;x / 2;}return s; } Function two&#xff1a; //二进制字符串变为十进制数字 int Decimal(string s) {int num 0, …
暂无图片
编程学习 ·

[含lw+源码等]微信小程序校园辩论管理平台+后台管理系统[包运行成功]Java毕业设计计算机毕设

项目功能简介: 《微信小程序校园辩论管理平台后台管理系统》该项目含有源码、论文等资料、配套开发软件、软件安装教程、项目发布教程等 本系统包含微信小程序做的辩论管理前台和Java做的后台管理系统&#xff1a; 微信小程序——辩论管理前台涉及技术&#xff1a;WXML 和 WXS…
暂无图片
编程学习 ·

树莓派驱动DHT11温湿度传感器

1&#xff0c;直接使用python库 代码如下 import RPi.GPIO as GPIO import dht11 import time import datetimeGPIO.setwarnings(True) GPIO.setmode(GPIO.BCM)instance dht11.DHT11(pin14)try:while True:result instance.read()if result.is_valid():print(ok)print(&quo…
暂无图片
编程学习 ·

ELK简介

ELK简介 ELK是三个开源软件的缩写&#xff0c;Elasticsearch、Logstash、Kibana。它们都是开源软件。不过现在还新增了一个 Beats&#xff0c;它是一个轻量级的日志收集处理工具(Agent)&#xff0c;Beats 占用资源少&#xff0c;适合于在各个服务器上搜集日志后传输给 Logstas…
暂无图片
编程学习 ·

Linux 基础

通常大数据框架都部署在 Linux 服务器上&#xff0c;所以需要具备一定的 Linux 知识。Linux 书籍当中比较著名的是 《鸟哥私房菜》系列&#xff0c;这个系列很全面也很经典。但如果你希望能够快速地入门&#xff0c;这里推荐《Linux 就该这么学》&#xff0c;其网站上有免费的电…
暂无图片
编程学习 ·

Windows2022 无线网卡装不上驱动

想来 Windows2022 和 windows10/11 的驱动应该差不多通用的&#xff0c;但是死活装不上呢&#xff1f; 搜一下&#xff0c;有人提到 “默认安装时‘无线LAN服务’是关闭的&#xff0c;如果需要开启&#xff0c;只需要在“添加角色和功能”中&#xff0c;选择开启“无线LAN服务…
暂无图片
编程学习 ·

【嵌入式面试宝典】版本控制工具Git常用命令总结

目录 创建仓库 查看信息 版本回退 版本检出 远程库 Git 创建仓库 git initgit add <file> 可反复多次使用&#xff0c;添加多个文件git commit -m <message> 查看信息 git status 仓库当前的状态git diff 差异对比git log 历史记录&#xff0c;提交日志--pret…
暂无图片
编程学习 ·

用Postman生成测试报告

newman newman是一款基于nodejs开发的可以运行postman脚本的工具&#xff0c;使用Newman&#xff0c;可以直接从命令运行和测试postman集合。 安装nodejs 下载地址&#xff1a;https://nodejs.org/en/download/ 选择自己系统相对应的版本内容进行下载&#xff0c;然后傻瓜式安…
暂无图片
编程学习 ·

Java面向对象之多态、向上转型和向下转型

文章目录前言一、多态二、引用类型之间的转换Ⅰ.向上转型Ⅱ.向下转型总结前言 今天继续Java面向对象的学习&#xff0c;学习面向对象的第三大特征&#xff1a;多态&#xff0c;了解多态的意义&#xff0c;以及两种引用类型之间的转换&#xff1a;向上转型、向下转型。  希望能…