存爱至死不渝 | 双向奔赴的 BFS 算法

存爱至死不渝 | 双向奔赴的 BFS 算法 — 双向广搜

本文主要是介绍存爱至死不渝 | 双向奔赴的 BFS 算法 — 双向广搜，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

双向广搜

- 算法思想
- 算法特点
- 适用场景
- 实现方式
- 例题
- - 字串变换
  - - 题目描述
    - 输入格式
    - 输出格式
    - 程序代码

算法思想

传统的 BFS 算法是从起始节点开始，逐层地访问图中的所有节点，直到到达目标节点。BFS 的时间复杂度为 $O(b^d)$ ，其中 b 是每个节点的平均分支因子，d 是目标节点的深度。

双向广搜是一种优化的 BFS 算法，它同时从起始节点和目标节点开始搜索，当两个搜索方向相遇时，就找到了一条最短路径。双向搜索的时间复杂度是 $O(b^{d/2})$

简单来说，传统的 BFS 算法就好比恋爱的双方，只有一方默默付出，直到与另一方汇合。而双向广搜则是恋爱双方的双向奔赴，他们最终会在奔赴的过程中汇合。

算法特点

与传统的 BFS 相比，双向广搜可以减少搜索空间的大小，因此比传统的 BFS 搜索速度更快。

同时，双向广搜可以减少搜索队列的长度，因此与传统的 BFS 相比，更不容易爆内存。

适用场景

当起始节点和目标节点都已知时。

实现方式

起点和终点，各自迈出一步【你付出，我也付出，但是不关注谁付出的多】
起点和终点，谁的搜索队列元素较少，谁迈出去一步【谁付出的少，谁付出】

例题

字串变换

题目描述

原题链接

已知有两个字串 $A, B$ 及一组字串变换的规则（至多 $6$ 个规则），形如：

$A_1\to B_1$ 。
$A_2\to B_2$ 。

规则的含义为：在 $A$ 中的子串 $A_1$ 可以变换为 $ B_1 $，$ A_2$ 可以变换为 $B_2\cdots$ 。

例如： $A=\texttt{abcd}$ ， $B＝\texttt{xyz}$ ，

变换规则为：

$\texttt{abc}\rightarrow\texttt{xu}$ ， $\texttt{ud}\rightarrow\texttt{y}$ ， $\texttt{y}\rightarrow\texttt{yz}$ 。

则此时， $A$ 可以经过一系列的变换变为 $B$ ，其变换的过程为：

$\texttt{abcd}\rightarrow\texttt{xud}\rightarrow\texttt{xy}\rightarrow\texttt{xyz}$ 。

共进行了 $3$ 次变换，使得 $A$ 变换为 $B$ 。

输入格式

第一行有两个字符串 $A, B$ 。

接下来若干行，每行有两个字符串 $A_i,B_i$ ，表示一条变换规则。

输出格式

若在 $10$ 步（包含 $10$ 步）以内能将 $A$ 变换为 $B$ ，则输出最少的变换步数；否则输出 NO ANSWER!。

程序代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <unordered_map>using namespace std;const int N = 10;
string A, B;  // 起点和终点
string a[N], b[N];  // 匹配规则
int n;// 扩展函数
// start：与起点的距离
// end：与终点的距离
// src：匹配源
// dst：匹配目标
int extend(queue<string>& q, unordered_map<string, int>& start, unordered_map<string, int>& end, string src[N], string dst[N]) {int d = start[q.front()];// 扩展一整层while(q.size() && start[q.front()] == d) {// 当前状态auto t = q.front();q.pop();for(int i = 0; i < n; i++) {// 找当前状态的匹配开始点for(int j = 0; j < t.size(); j++) {// 匹配成功if( t.substr(j, src[i].size()) == src[i] ) {// 替换后的结果string res = t.substr(0, j) + dst[i] + t.substr(j + src[i].size());// 汇合了if( end.count(res) )  return start[t] + end[res] + 1;if( start.count(res) )  continue;start[res] = start[t] + 1;q.push(res);}                }}}// 这一轮没汇合return 11;
}// 双向广搜：返回值为所需步数
int bfs()
{if( A == B )  return 0;queue<string> qa, qb;  // 各自的搜索队列// 当前状态到起点（终点）的距离unordered_map<string, int> da, db;qa.push(A);qb.push(B);da[A] = db[B] = 0;  // 初始化int step = 0;  // 已经进行步数// 由于是无向图，若其中一个搜索队列没有值，说明双方是不连通的while( qa.size() && qb.size() ) {int t;  // 记录最小步数// 从A扩展，匹配规则是a到bif( qa.size() <= qb.size() )  t = extend(qa, da, db, a, b);// 从B扩展，匹配规则是b到aelse  t = extend(qb, db, da, b, a);if( t <= 10 )  return t;if( ++step == 10 )  return -1;}// 不连通或步数大于10return -1;
}int main()
{cin >> A >> B;while( cin >> a[n] >> b[n] )  n++;// 双向广搜计算步数int step = bfs();if( step == -1 )  cout << "NO ANSWER!" << endl;else  cout << step << endl;return 0;
}