简介

双向BFS就是在一直当前状态和期望状态时,从当前和期望两个状态同时出发,直到某个状态同时被访问到两次,那么当前状态->被访问两次的状态->目标状态就是当前状态到目标状态的解。那具体会有多块呢?加入每一次搜索都有n个新的状态(比如迷宫问题就是上下左右四个状态),从起点到目标路径长为m,那就要搜索$n+n^{2}+n^{3}+……+n^{m}$个状态,状态数就是$n^{m+1}$数量级的,若是双向广搜呢?在路径中点就能相遇,状态数是$2*n^{m/2+1}$数量级的,比起朴素的BFS,枚举状态数少了很多,所以对于从起始状态和目标状态已知的情况,我们可以使用双向BFS来优化程序的时间复杂度。下面通过一个例子来看看优化的效果。

Q1八数码难题

原题传送门->洛谷P1379
搜先看一下朴素的单搜

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<iostream>
#include<vector>
#include<climits>
#include<string>
#include<queue>
#include<functional>
#include<set>
#include<algorithm>
#include<map>
using namespace std;
#define il inline
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define MAX ((int)1e9)
struct node {
int map[3][3];
int x, y, val;
node(int ma[3][3], int x, int y, int val) :x(x), y(y), val(val)
{
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
map[i][j] = ma[i][j];
}
};
int dr[][2]{ 1,0,0,1,-1,0,0,-1 };
int ans[3][3]{ 1,2,3,8,0,4,7,6,5 };
il bool check(const int map[3][3])
{
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (map[i][j] != ans[i][j])
return false;
return true;
}
il int get(int map[3][3])
{
int ans = 0, bs = 1;
for (int i = 2; i >= 0; i--)
for (int j = 2; j >= 0; j--)
{
ans += bs * map[i][j];
bs *= 10;
}
return ans;
}
map<int,bool> vis;
int main()
{
int mapp[3][3];
int g; cin >> g;
int x, y;
for (int i = 2; i >= 0; i--)
for (int j = 2; j >= 0; j--)
{
mapp[i][j] = g % 10;
g /= 10;
if (mapp[i][j] == 0)
x = i, y = j;
}
queue<node> Q;
Q.push({ mapp,x,y,0 });
while (!Q.empty())
{
node noww = Q.front(); Q.pop();
if (vis[get(noww.map)])continue;
vis[get(noww.map)] = true;
if (check(noww.map))
{
cout << noww.val;
return 0;
}
for (int k = 0; k < 4; k++)
{
node now = noww;
x = now.x + dr[k][0], y = now.y + dr[k][1];
if (x >= 0 && x <= 2 && y >= 0 && y <= 2)
{
int t = now.map[x][y];
now.map[now.x][now.y] = t;
now.map[x][y] = 0;
now.x = x, now.y = y;
now.val++;
if (!vis[get(now.map)])
Q.push(now);
}
}
}
return 0;
}

就是很朴素的模拟,然后暴力搜索。判重用并查集会快,可是蒟蒻当时不会
时间:8802ms
内存:9.61MB
虽然AC了数据太水 ,但是我们看看双向BFS的表现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<iostream>
#include<vector>
#include<climits>
#include<string>
#include<queue>
#include<functional>
#include<set>
#include<algorithm>
#include<map>
using namespace std;
#define il inline
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define MAX ((int)1e9)
int ans = 123804765;
int dr[][2] = { 0,1,0,-1,1,0,-1,0 };
il int getInt(int map[3][3])
{
int ans = 0, bs = 1;
for (int i = 2; i >= 0; i--)
for (int j = 2; j >= 0; j--)
{
ans += bs * map[i][j];
bs *= 10;
}
return ans;
}
queue<int> Q1, Q2;
map<int, int> cc;
map<int, int> res;
int main()
{
int mapp[3][3];
int g; cin >> g;
int x, y;
if (ans == g)
{
cout << 0;
return 0;
}
Q1.push(g); cc[g] = 1; res[g] = 0;//两个队列,一个向前,一个向后
Q2.push(ans); cc[ans] = 2; res[ans] = 0;
bool is;
while (!Q1.empty()||!Q2.empty())
{
int now, x, y;
if (Q1.size() < Q2.size() || Q1.size() > Q2.size() && Q2.empty())
{//那个队列状态数少就拓展那个,让总状态数更少
now = Q1.front(); Q1.pop(); is = true;
}
else
{
now = Q2.front(); Q2.pop(); is = false;
}
for (int i = 2, g = now; i >= 0; i--)
for (int j = 2; j >= 0; j--)
{
mapp[i][j] = g % 10;
g /= 10;
if (mapp[i][j] == 0)
x = i, y = j;
}
for (int k = 0; k < 4; k++)
{
int x_ = x + dr[k][0], y_ = y + dr[k][1];
if (x_ >= 0 && x_ < 3 && y_ >= 0 && y_ < 3)
{
swap(mapp[x][y], mapp[x_][y_]);
int temp = getInt(mapp);
if (cc[temp] == cc[now])
{
swap(mapp[x][y], mapp[x_][y_]);
continue;
}
if (cc[now] + cc[temp] == 3)
{
cout << res[now] + 1 + res[temp];
return 0;
}
res[temp] = res[now] + 1;
cc[temp] = cc[now];
if(is)Q1.push(temp);
else Q2.push(temp);
swap(mapp[x][y], mapp[x_][y_]);
}
}
}
return 0;
}

时间:379ms
内存:1.2MB
效率++++有木有,内存只用了八分之一,时间更是只用了二十分之一还快。但是不是什么时候都能用。比如若果题目要求输出最短方案中字典序最小的移动方案之类的,依据单向BFS的访问顺序可以从步骤A开始顺序执行,得到字典序最小的,但是双向的话虽然先相遇的是最短的,但不一定是字典序最小的。