双向 BFS

1 从两端搜索

广度优先搜索(BFS):从迷宫到最少步数 从起点逐层扩展,第一次发现终点时得到最少步数。若每个状态平均产生 bb 个新状态,答案深度为 dd,搜索树的规模可能达到 bdb^d 量级。

当终点已知,而且能够枚举一个状态的前驱时,可以从起点、终点分别搜索,在中间连接两条路径。

下面的有向图中,从 SS 到 TT 最少需要 33 步。图上的箭头始终表示原图方向。

双向搜索从 S、T 出发,在中间层相遇

正向先发现 {A,B}\{A,B\},反向先发现 {C,D}\{C,D\}。再扩展正向的一层,就能在 CC 或 DD 连接两侧:

S→A→C→T,2+1=3. S\to A\to C\to T,\qquad 2+1=3.

在分支较均衡、重复状态较少的搜索树中,两侧各搜索约 d/2d/2 层,状态量约为 2bd/22b^{d/2}。这是常见的加速原因,不是任意图上的复杂度保证。

2 反向搜索

设两侧距离为:

  • ds[u]d_s[u]:从起点 SS 到 uu 的最少步数。
  • dt[u]d_t[u]:从 uu 到终点 TT 的最少步数。

反向 BFS 要沿反图扩展。原图有边 u→vu\to v,反图就有边 v→uv\to u。这样从 TT 搜到 uu 的距离,才等于原图中 uu 到 TT 的距离。无向图的两个方向可以使用同一张邻接表。

两侧都发现状态 uu 时,得到一条长度为 ds[u]+dt[u]d_s[u]+d_t[u] 的路径。

3 按层相遇

每次选择当前待扩展节点较少的一侧,扩展完整的一层。这一层产生的所有相遇候选取最小值,随后结束搜索。选择较小的一层只影响效率,不改变最优性。

证明如下。假设扩展前,两侧已经分别发现距离不超过 a,ba,b 的全部状态,而且尚未相遇。

若存在长度不超过 a+ba+b 的路径,它必然有一个节点同时落在这两个距离范围内,与尚未相遇矛盾。因此,最短路长度至少为 a+b+1a+b+1。

现在正向完整扩展一层,新相遇点给出的路径长度至多为 (a+1)+b(a+1)+b,恰好达到上述下界。反向扩展时同理。若这一层没有相遇,就继续下一轮。

这个结论依赖三个条件:单位边权、正确的反向转移、按整层扩展。不要把代码改成每次只取一个节点、重新选择方向后立即返回第一次相遇。

4 代码实现

输入 n m s t,随后输入 mm 条有向边;节点编号为 1∼n1\sim n,n≤2×105n\le 2\times10^5。输出最少步数,不可达时输出 -1。

expand 开始时记录队尾,保证这一轮只处理原有的一层,新加入的节点留到下一轮。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 200000 + 5;
vector<int> g[2][maxn];  // 0:原图;1:反图
int dis[2][maxn], q[2][maxn];
int head[2], tail[2];

// 队列中尚未处理的节点恰好是一层;只扩展这一层。
int expand(int side) {
    int end = tail[side], answer = INT_MAX;
    while (head[side] < end) {
        int u = q[side][head[side]++];
        for (int v : g[side][u]) {
            if (dis[side][v] != -1) continue;
            dis[side][v] = dis[side][u] + 1;
            q[side][tail[side]++] = v;
            if (dis[side ^ 1][v] != -1) {
                answer = min(answer, dis[side][v] + dis[side ^ 1][v]);
            }
        }
    }
    return answer;
}

int bfs(int s, int t) {
    memset(dis, -1, sizeof(dis));
    head[0] = head[1] = tail[0] = tail[1] = 0;
    dis[0][s] = dis[1][t] = 0;
    q[0][tail[0]++] = s;
    q[1][tail[1]++] = t;
    if (s == t) return 0;

    while (head[0] < tail[0] && head[1] < tail[1]) {
        // 选择较小的整层,不能只取一个节点就重新选择方向。
        int side = (tail[0] - head[0] <= tail[1] - head[1]) ? 0 : 1;
        int answer = expand(side);
        if (answer != INT_MAX) return answer;
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, s, t;
    cin >> n >> m >> s >> t;
    while (m--) {
        int u, v;
        cin >> u >> v;
        g[0][u].push_back(v);
        g[1][v].push_back(u);  // 原图 u -> v,反图 v -> u
    }
    cout << bfs(s, t) << '\n';
    return 0;
}

在显式图上,每个方向至多访问每个节点、每条边一次,时间和空间复杂度均为 O(n+m)O(n+m)。若某侧队列为空且仍未相遇,就不存在从起点到终点的路径。

5 字串变换

题目:luogu P1032: [NOIP 2002 提高组] 字串变换(疑似错题)。

给定起始串 AA、目标串 BB 和不超过 66 条替换规则。每步选择一条规则,把当前串中匹配的一处子串替换掉,求 1010 步以内的最少变换次数。

把整个字符串看作一个节点,一次替换看作一条有向边。反向搜索时,必须把每条规则的左右两端交换:

正向规则 反向规则
ab → x x → ab
x → yz yz → x

例如正向路径是 cab → cx → cyz,反向就从 cyz 经 cx 回到 cab。从目标串继续使用原规则,得到的不是前驱状态。

5.1 状态生成

对每条规则,枚举左串在当前串中的所有出现位置,每次只替换一处。出现位置可以重叠:规则 aa → b 作用于 aaa,能够产生 ba 和 ab。

字符串状态用哈希表记录最短距离,入队时判重。输入串长度不超过 2020,不代表中间串也不超过 2020,不能据此截断搜索。

5.2 搜索边界

初始时两侧半径之和为 00。每轮只扩展一侧的一层,半径之和增加 11。因此,最多扩展 1010 轮,就能判断是否存在不超过 1010 步的路径。

若 A=BA=B,直接输出 00;否则在首个相遇层取得最少步数。两侧半径不必各为 55,代码会根据前沿大小选择方向。

完整代码
#include <bits/stdc++.h>
using namespace std;

pair<string, string> rule[2][10];
int rule_count;
queue<string> q[2];
unordered_map<string, int> dis[2];  // 字符串状态无法直接用整数数组下标

int expand(int side) {
    int count = q[side].size(), answer = INT_MAX;
    while (count--) {  // 新入队的下一层留到下一轮处理
        string s = q[side].front();
        q[side].pop();
        int step = dis[side].at(s);
        for (int i = 0; i < rule_count; ++i) {
            const auto &[from, to] = rule[side][i];
            // 从 pos + 1 继续查找,保留重叠的出现位置。
            for (size_t pos = s.find(from); pos != string::npos;
                 pos = s.find(from, pos + 1)) {
                string next = s.substr(0, pos) + to + s.substr(pos + from.size());
                if (!dis[side].emplace(next, step + 1).second) continue;
                q[side].push(next);
                auto it = dis[side ^ 1].find(next);
                if (it != dis[side ^ 1].end()) {
                    answer = min(answer, step + 1 + it->second);
                }
            }
        }
    }
    return answer;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string start, goal, from, to;
    cin >> start >> goal;
    while (cin >> from >> to) {
        rule[0][rule_count] = {from, to};
        rule[1][rule_count++] = {to, from};  // 反向搜索必须交换规则两端
    }
    if (start == goal) {
        cout << 0 << '\n';
        return 0;
    }

    q[0].push(start);
    q[1].push(goal);
    dis[0][start] = dis[1][goal] = 0;
    // 每轮只让一侧的搜索半径增加 1;总半径最多增加到 10。
    for (int round = 0; round < 10 && !q[0].empty() && !q[1].empty(); ++round) {
        int side = (q[0].size() <= q[1].size()) ? 0 : 1;
        int answer = expand(side);
        if (answer != INT_MAX) {
            cout << answer << '\n';
            return 0;
        }
    }
    cout << "NO ANSWER!\n";
    return 0;
}

设两侧共发现 VV 个状态,规则数为 RR,搜索中的串长上界为 LL。按字符串查找、构造和哈希的通常代价估计,时间为 O(VRL2)O(VRL^2),空间为 O(VL)O(VL)。状态数仍可能随深度指数增长;双向搜索不保证消除所有大分支。

完整题解:pcs2:字串变换。

6 相关题解

暂无相关题解