关注我哟定期推送帐号信息学新闻，竞赛自主招生，信息学专业知识，信息学疑难解答，信息学训练营信息等诸多优质内容的微信平台，欢迎分享文章给你的朋友或者朋友圈！
大明老师
读完需要
28
分钟
速读仅需 14分钟
今天说下广度搜索优化的一些技巧，广度搜索的方式基本上是套模板，其实在套模板代码之外有一些优化的技巧，现在把广搜做为一个重点的专题，通过题目了解广度优先搜索如何优化。
广度优先搜索优化
其实就是暴力的方式，优化的方向如何减少搜索的次数，加快搜索的效率。
减少搜索的次数，如何减少可以通过双向BFS。传统的BFS框架就是从起点开始向四周扩散，遇到终点时停止；而双向BFS则是从起点和终点同时开始扩散，当两边有交集的时候停止。
先看看传统的BFS，就是给个起始点，然后提供一个终点，一层一层的往下搜，一直搜到终点，这就是正常框架里面的单向BFS。
双向的BFS，起始点和终止点同时双向扩散，举个例子：你去同学家见面比较远，你俩约一个地点离彼此比较近的地方，需要你和你同学同时都出发。
双向如何确定最短路，就是彼此在想向搜索的时候，相遇的点彼此相遇，举个例子，起点访问过了，终点搜索的时候也访问过了，说明这个点已经被重合了，说明两个路径加起来就是最短的路径了。你和你同学彼此走过路之和就时候最短的路。
而双向BFS其实只遍历了半棵树就出现了交集，也就是找到了最短距离。但是双向BFS有个局限，必须知道终点在哪里，如果不知道终点在哪里肯定都没办法双向了。
既然是双向肯定是需要两个队列的，起始点一个队列，终止点一个队列。所以在原有的代码模板的基础上，需要有两个队列。其中在加个判断条件，点是否同时被两个人访问，如果被同时访问说明两个点就重合了，在队列的访问的加起来最短距离就出来了。
无论传统BFS还是双向BFS，无论做不做优化，从大 O 衡量标准来看，时间复杂度都是一样的，只能说双向BFS是一种trick，算法运行的速度会相对快一点，掌握不掌握其实都无所谓。最关键的是把BFS通用框架记下来，反正所有BFS算法都可以用它套出解法。
【题目描述】在各种棋中，棋子的走法总是一定的，如中国象棋中马走“日”。有一位小学生就想如果马能有两种走法将增加其趣味性，因此，他规定马既能按“日”走，也能如象一样走“田”字。他的同桌平时喜欢下围棋，知道这件事后觉得很有趣，就想试一试，在一个（100×100）的围棋盘上任选两点A、B，A点放上黑子，B点放上白子，代表两匹马。棋子可以按“日”字走，也可以按“田”字走，俩人一个走黑马，一个走白马。谁用最少的步数走到左上角坐标为(1,1)的点时，谁获胜。现在他请你帮忙，给你A、B两点的坐标，想知道两个位置到（1,1）点可能的最少步数。
【输入】A、B两点的坐标。
【输出】最少步数。
题目解析：走日的话是8个方向，走田的是4个方向，一共是12个方向。12个方向映射成12个坐标。
#include
using namespace std;
const int maxn = 1001;
char a[maxn] [maxn];
int vis [maxn] [maxn] ;
int d[12][2] ={ {2,1},{2,2},{1,2},{-1,2},{-2,2},{-2,1},{-2,-1},{-2,-2},{-1,-2},{1,-2},{2,-2},{2,-1} };//有12个方向
int n,m;
struct node{
int x;
int y;
int step;
}q[maxn*maxn];
void bfs(int x,int y)
{
int head=1;
int tail=1;
q[tail].x = x;
q[tail].y = y;
q[tail].step = 0;
tail++;
vis[x][y]=1;
while(head < tail)
{
int x0 = q[head].x;
int y0 = q[head].y;
int step = q[head].step;
if(x0==1&&y0==1){
cout<<step<<endl;
break;
}
for(int i=0;i<12;i++)
{
int nx = x0 + d[i][0];
int ny = y0 + d[i][1];
if(nx>=1 && nx<100 &&ny >= 1 && ny < 100 && a[nx][ny] != '0'&& vis[nx][ny] != 1)
{
q[tail].x = nx;
q[tail].y = ny;
q[tail].step = step+1;
tail++;
vis[nx][ny]=1;
}
}
head++;
}
}
int main()
{
int xa,ya,xb, yb;
memset(vis,0,sizeof(vis));
cin>>xa>>ya>>xb>>yb;
bfs(xa, ya);
memset(vis,0,sizeof(vis));
bfs(xb, yb);
return 0;
}
以下是对代码的解析：
引入头文件 ，用于包含常用的标准库。
使用命名空间 std。
定义常量 maxn，表示二维数组的最大大小。
声明二维字符数组 a，用于表示地图。
声明二维整数数组 vis，用于记录某个位置是否被访问过。
定义二维整数数组 dmemset头文件，表示12个方向的偏移量，用于马走日移动和田移动。
声明变量 n 和 m，表示行数和列数。
定义结构体 node，包含坐标 (x, y) 和步数 step，用于记录走到某个点所需要的步数。
声明队列 q，用于进行广度优先搜索。
定义函数 bfs，用于执行广度优先搜索算法。
在 main 函数中，初始化变量，并调用 bfs 函数两次，分别求解马走日和田的最短路径。
返回 0，表示程序运行结束。
该代码使用广度优先搜索算法来寻找马走日和田的最短路径。通过将起点加入队列，然后循环进行以下步骤：
【题目描述】农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0 5返回最短路为4，错误的，事实是3，S-2-4-T
上面的牛和农夫的问题，通过双向BFS实现。
#include
using namespace std;
const int maxn = 1000001 ;
int step;
void bfs(int sx, int ex)
{
set<int>q1;
set<int>q2;
set<int>visted;
set<int>tmp;
q1.insert(sx);
q2.insert(ex);
while(q1.size() && q2.size())
{
tmp.clear();
for(set<int>::iterator it = q1.begin(); it != q1.end(); it++)
{
int cur = *it;
visted.insert(cur);
if(q2.find(cur)!=q2.end())
{
cout<<step<<endl;
return;
}
for(int i = 1; i <= 3; i++)
{
int nc = cur;
if(i==1) nc++;
if(i==2) nc--;
if(i==3)
{
if(step%2!= 0)
{
if(nc%2 == 0)
{
nc /= 2;
}
else
{
continue ;
}
}
else
{
nc *= 2;
}
}
if(nc >= 0 && nc <= 100000 && visted.find(nc) == visted.end())
{
tmp.insert(nc);
}
}
}
step++;
q1 = q2;
q2 = tmp;
}
}
int main()
{
int n, k;
cin>>n>>k;
bfs(n,k);
return 0;
}
这段代码的功能是在一个数轴上，从起点 n 到终点 kmemset头文件，求解最短步数。以下是对代码解析：
引入头文件 ，用于包含常用的标准库。
使用命名空间 std。
定义常量 maxn，表示数组的最大大小。
声明变量 step，用于记录步数。
定义函数 bfs，用于执行广度优先搜索算法。
在 bfs 函数中，使用四个集合 q1、q2、 和 tmp，分别用于存储当前步数的起点集合、终点集合、已访问的集合和临时集合。
将起点 sx 加入集合 q1，将终点 ex 加入集合 q2。
在循环中，首先清空临时集合 tmp。
遍历集合 q1，对于其中的每个元素 cur，将其加入已访问的集合 。
如果终点集合 q2 中存在元素等于当前元素 cur，则输出步数 step 并返回。
否则，根据题目要求的三种操作，计算出相邻节点的坐标 nc。
如果相邻节点在规定范围内且未被访问过，则将其加入临时集合 tmp。
完成一轮循环后，步数 step 加一，将终点集合 q2 更新为临时集合 tmp，将起点集合 q1 更新为终点集合 q2。
在 main 函数中，读入起点 n 和终点 k，然后调用 bfs 函数求解最短步数。
返回 0，表示程序运行结束。
该代码使用广度优先搜索算法来寻找起点到终点的最短步数。通过使用两个集合 q1 和 q2 来交替存储当前步数的起点和终点，同时使用集合 来记录已访问的节点，以避免重复访问。在每一步中，根据题目要求的三种操作计算相邻节点的坐标，并将未访问过的相邻节点加入临时集合 tmp。当终点集合 q2 中存在与起点集合 q1 中相同的节点时，即找到最短路径，输出步数。
PS：在做题的时候，终点还是理解单向BFS，双向BFS受限比较多，单向BFS受限效率的话，就可以使用双向。不太建议，但是这种思维方式需要理解掌握。