算法搜索

双向搜索

字数统计: 2.5k字   |   阅读时长: 11分
, ,

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

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的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