双向搜索

  |  

摘要: 从起点和终点同时一层一层地搜索。

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


在一些从起点向终点搜索的问题中,如果采用 BFS 的方式一层一层搜的话,层数越多,则每一层要搜索的就越多。

假如起点到终点距离为 $d$,BFS 需要搜索 $d$ 层才能到达终点。如果图很稠密的话,在后半段每层的节点会非常多。

如果终点也同时参与搜索,每一步起点和终点各往前推进一层,这样起点和终点都只需要走 $\frac{d}{2}$ 层就可以相遇了。自然减少了很多无效节点的搜索。

本文我们通过两个题看一下双向 BFS 和双向迭代加深分别是怎么做的。


$1 双向搜索的思想

在一些问题中,初态和终态都是确定的,并且从初态向终态搜索,并且两个方向的搜索是等效的,和从终态向初态搜索都可以覆盖整个搜索空间,相当于搜索路径可逆。此时可以采用双向搜索。

在搜索过程中对状态染色,一共有三种:

  • 未访问过
  • 属于初态搜索树
  • 属于终态搜索树

当属于初态的搜索树和属于终态的搜索树在某个状态相遇了,则搜索到了答案,此时根据需求整合答案就可以返回了。

当状态图的边比较稠密的时候,一层的状态数随着层数加深增长很快,此时双向搜索带来的深度减半的收益很大。

如果边比较稀疏,则效果不明显。

双向搜索有两种,一种是双向BFS,另一种是双向迭代加深。


$2 双向BFS

单词接龙是非常经典的双向 BFS,参考文章 【搜索难题】力扣127-双向BFS【搜索难题】力扣126-两次搜索,搜索路径

下面的 752. 打开转盘锁 是非常经典的双向 BFS 的问题,从 BFS 改为双向 BFS 后,收益很明显。搜索的思路见前面分析,下面直接给出代码。

752. 打开转盘锁

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字: ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转:例如把 ‘9’ 变为 ‘0’,’0’ 变为 ‘9’ 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 ‘0000’ ,一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字,一旦拨轮的数字和列表里的任何一个元素相同,这个锁将会被永久锁定,无法再被旋转。

字符串 target 代表可以解锁的数字,你需要给出解锁需要的最小旋转次数,如果无论如何不能解锁,返回 -1 。

提示:

1
2
3
4
5
1 <= deadends.length <= 500
deadends[i].length == 4
target.length == 4
target 不在 deadends 之中
target 和 deadends[i] 仅由若干位数字组成

示例 1:
输入:deadends = [“0201”,”0101”,”0102”,”1212”,”2002”], target = “0202”
输出:6
解释:
可能的移动序列为 “0000” -> “1000” -> “1100” -> “1200” -> “1201” -> “1202” -> “0202”。
注意 “0000” -> “0001” -> “0002” -> “0102” -> “0202” 这样的序列是不能解锁的,
因为当拨动到 “0102” 时这个锁就会被锁定。

示例 2:
输入: deadends = [“8888”], target = “0009”
输出:1
解释:把最后一位反向旋转一次即可 “0000” -> “0009”。

示例 3:
输入: deadends = [“8887”,”8889”,”8878”,”8898”,”8788”,”8988”,”7888”,”9888”], target = “8888”
输出:-1
解释:无法旋转到目标数字且不被锁定。

基础 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
class Solution {
public:
int openLock(vector<string>& deadends, string target) {
unordered_set<int> setting;
for(const string& num_str: deadends)
{
int num;
stringstream ss;
ss << num_str;
ss >> num;
setting.insert(num);
}
int start = 0;
int end;
stringstream ss;
ss << target;
ss >> end;
return bfs(start, end, setting);
}

private:
const int N = 10000;

vector<int> _get_next(int num)
{
// num 为 4 位数
vector<int> result;
int iter = num;
for(int i = 0; i < 4; ++i)
{
int digit = iter % 10;
iter /= 10;
int new_num = num - digit * pow(10, i);
int new_digit1 = (digit - 1 + 10) % 10;
int new_digit2 = (digit + 1 + 10) % 10;
result.push_back(new_num + new_digit1 * pow(10, i));
result.push_back(new_num + new_digit2 * pow(10, i));
}
return result;
}

int bfs(int start, int end, const unordered_set<int>& setting)
{
if(setting.find(start) != setting.end()) return -1;
vector<bool> visited(N, false);
queue<int> q;
q.push(start);
visited[start] = true;
int d = 0;
vector<int> level_nodes;
while(!q.empty())
{
level_nodes.clear();
while(!q.empty())
{
level_nodes.push_back(q.front());
q.pop();
}
++d;
for(int node: level_nodes)
{
for(int son: _get_next(node))
{
if(son == end)
return d;
if(setting.find(son) != setting.end()) continue;
if(visited[son]) continue;
visited[son] = true;
q.push(son);
}
}
}
return -1;
}
};

双向 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
90
91
92
93
94
95
96
97
class Solution {
public:
int openLock(vector<string>& deadends, string target) {
unordered_set<int> setting;
for(const string& num_str: deadends)
{
int num;
stringstream ss;
ss << num_str;
ss >> num;
setting.insert(num);
}
int start = 0;
int end;
stringstream ss;
ss << target;
ss >> end;
return bfs(start, end, setting);
}

private:
const int N = 10000;

vector<int> _get_next(int num)
{
// num 为 4 位数
vector<int> result;
int iter = num;
for(int i = 0; i < 4; ++i)
{
int digit = iter % 10;
iter /= 10;
int new_num = num - digit * pow(10, i);
int new_digit1 = (digit - 1 + 10) % 10;
int new_digit2 = (digit + 1 + 10) % 10;
result.push_back(new_num + new_digit1 * pow(10, i));
result.push_back(new_num + new_digit2 * pow(10, i));
}
return result;
}

int bfs(int start, int end, const unordered_set<int>& setting)
{
if(setting.find(start) != setting.end()) return -1;
queue<int> q1;
q1.push(start);
queue<int> q2;
q2.push(end);
vector<int> visited(N, 0);
visited[start] = 1;
visited[end] = -1;
int d = 0;
vector<int> level_nodes;
while(!q1.empty() && !q2.empty())
{
level_nodes.clear();
while(!q1.empty())
{
level_nodes.push_back(q1.front());
q1.pop();
}
++d;
for(int node: level_nodes)
{
for(int son: _get_next(node))
{
if(setting.find(son) != setting.end()) continue;
if(visited[son] == 1) continue;
if(visited[son] == -1)
return d;
visited[son] = 1;
q1.push(son);
}
}
level_nodes.clear();
while(!q2.empty())
{
level_nodes.push_back(q2.front());
q2.pop();
}
++d;
for(int node: level_nodes)
{
for(int son: _get_next(node))
{
if(setting.find(son) != setting.end()) continue;
if(visited[son] == -1) continue;
if(visited[son] == 1)
return d;
visited[son] = -1;
q2.push(son);
}
}
}
return -1;
}
};

$3 双向迭代加深

迭代加深的原理和代码可以参考文章 迭代加深

双向迭代加深也可以称为双向固定深度 DFS

题目:171. 送礼物

达达帮翰翰给女生送礼物,翰翰一共准备了 N 个礼物,其中第 i 个礼物的重量是 G[i]。

达达的力气很大,他一次可以搬动重量之和不超过 W 的任意多个物品。

达达希望一次搬掉尽量重的一些物品,请你告诉达达在他的力气范围内一次性能搬动的最大重量是多少。

1
2
3
4
5
6
7
8
9
10
输入格式
第一行两个整数,分别代表 W 和 N。
以后 N 行,每行一个正整数表示 G[i]。

输出格式
仅一个整数,表示达达在他的力气范围内一次性能搬动的最大重量。

数据范围
1<=N<=46,
1<=W,G[i]<=2^31−1

输入样例:
20 5
7
5
4
18
1
输出样例:
19

算法:DFS

这是大体积背包问题,DFS 的状态是指数型枚举的,每个物品有选和不选,再加上剪枝,就形成了 DFS 搜索的基本框架。

物品最多有 46 个,因此状态个数为 $2^{46}$,将物品分为两堆。

剪枝

可行性剪枝:

1
2
if((ll)w + A[pos] > W)
不搜索该分支

代码 (C++)

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
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

using ll = long long;

void dfs(const vector<int>& A, const int W, int w, int pos, int& ans)
{
int N = A.size();
if(pos == N)
{
ans = max(ans, w);
return;
}
dfs(A, W, w, pos + 1, ans);
if((ll)w + A[pos] <= W)
dfs(A, W, w + A[pos], pos + 1, ans);
}

int solve(const vector<int>& A, const int W)
{
int ans = 0;
dfs(A, W, 0, 0, ans);
return ans;
}

int main()
{
int W, N;
cin >> W >> N;
vector<int> A(N);
for(int i = 0; i < N; ++i)
cin >> A[i];
int ans = solve(A, W);
cout << ans << endl;
}

双向搜索(双向固定深度DFS)

将 A 分成两半。

第一次搜索用基础 DFS 搜索前一半,将所有在 [0, W] 取到的结果存在 tmp 中,对 tmp 排序,去重。

第二次搜索用基础 DFS 搜索后一半,对每个在 [0, W] 取到的 w,在 tmp 中找一个 x 使得 0 <= x + t <= W 找到最大的 x,则找到一个候选答案 ans = max(ans, w + x);

搜索顺序

将物品按重量从到大到小排序后再搜索(从大向小搜)。

1
sort(A.begin(), A.end(), greater<int>());

代码 (C++)

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
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

using ll = long long;

void dfs1(const vector<int>& A, const int W, int w, int pos, const int t, vector<int>& tmp)
{
if(pos == t)
{
tmp.push_back(w);
return;
}
dfs1(A, W, w, pos + 1, t, tmp);
if((ll)w + A[pos] <= W)
dfs1(A, W, w + A[pos], pos + 1, t, tmp);
}

void dfs2(const vector<int>& A, const int W, int w, int pos, const int t, int& ans, vector<int>& tmp)
{
if(pos == t)
{
// 找 w + x <= W 的最大 x, t <= W - w 的最大 x
auto it = upper_bound(tmp.begin(), tmp.end(), W - w);
if(it != tmp.begin())
{
int x = *(--it);
ans = max(ans, w + x);
return;
}
}
dfs2(A, W, w, pos + 1, t, ans, tmp);
if(w + A[pos] <= W)
dfs2(A, W, w + A[pos], pos + 1, t, ans, tmp);
}

int solve(const vector<int>& A, const int W)
{
int N = A.size();
vector<int> tmp;
dfs1(A, W, 0, 0, N / 2, tmp);
sort(tmp.begin(), tmp.end());
tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
int ans = 0;
dfs2(A, W, 0, N / 2 + 1, N - 1, ans, tmp);
return ans;
}

int main()
{
int W, N;
cin >> W >> N;
vector<int> A(N);
for(int i = 0; i < N; ++i)
cin >> A[i];
int ans = solve(A, W);
cout << ans << endl;
}

Share