各大网站博客怎么做推广,网站要服务器吗,关于房产的网站有哪些,企业广告视频拍摄双向广搜 算法思想算法特点适用场景实现方式例题字串变换题目描述输入格式输出格式程序代码 算法思想
传统的 BFS 算法是从起始节点开始#xff0c;逐层地访问图中的所有节点#xff0c;直到到达目标节点。BFS 的时间复杂度为 O ( b d ) O(b^d) O(bd)#xff0c;其中 b 是… 双向广搜 算法思想算法特点适用场景实现方式例题字串变换题目描述输入格式输出格式程序代码 算法思想
传统的 BFS 算法是从起始节点开始逐层地访问图中的所有节点直到到达目标节点。BFS 的时间复杂度为 O ( b d ) O(b^d) O(bd)其中 b 是每个节点的平均分支因子d 是目标节点的深度。
双向广搜是一种优化的 BFS 算法它同时从起始节点和目标节点开始搜索当两个搜索方向相遇时就找到了一条最短路径。双向搜索的时间复杂度是 O ( b d / 2 ) O(b^{d/2}) O(bd/2)
简单来说传统的 BFS 算法就好比恋爱的双方只有一方默默付出直到与另一方汇合。而双向广搜则是恋爱双方的双向奔赴他们最终会在奔赴的过程中汇合。
算法特点
与传统的 BFS 相比双向广搜可以减少搜索空间的大小因此比传统的 BFS 搜索速度更快。
同时双向广搜可以减少搜索队列的长度因此与传统的 BFS 相比更不容易爆内存。
适用场景
当起始节点和目标节点都已知时。
实现方式
起点和终点各自迈出一步【你付出我也付出但是不关注谁付出的多】起点和终点谁的搜索队列元素较少谁迈出去一步【谁付出的少谁付出】
例题
字串变换
题目描述 原题链接 已知有两个字串 A , B A,B A,B 及一组字串变换的规则至多 6 6 6 个规则形如 A 1 → B 1 A_1\to B_1 A1→B1。 A 2 → B 2 A_2\to B_2 A2→B2。
规则的含义为在 A A A 中的子串 A 1 A_1 A1 可以变换为 $ B_1 A_2$ 可以变换为 B 2 ⋯ B_2\cdots B2⋯。
例如 A abcd A\texttt{abcd} Aabcd B xyz B\texttt{xyz} Bxyz
变换规则为 abc → xu \texttt{abc}\rightarrow\texttt{xu} abc→xu ud → y \texttt{ud}\rightarrow\texttt{y} ud→y y → yz \texttt{y}\rightarrow\texttt{yz} y→yz。
则此时 A A A 可以经过一系列的变换变为 B B B其变换的过程为 abcd → xud → xy → xyz \texttt{abcd}\rightarrow\texttt{xud}\rightarrow\texttt{xy}\rightarrow\texttt{xyz} abcd→xud→xy→xyz。
共进行了 3 3 3 次变换使得 A A A 变换为 B B B。
输入格式
第一行有两个字符串 A , B A,B A,B。
接下来若干行每行有两个字符串 A i , B i A_i,B_i Ai,Bi表示一条变换规则。
输出格式
若在 10 10 10 步包含 10 10 10 步以内能将 A A A 变换为 B B B则输出最少的变换步数否则输出 NO ANSWER!。
程序代码
#include iostream
#include algorithm
#include cstring
#include string
#include queue
#include unordered_mapusing namespace std;const int N 10;
string A, B; // 起点和终点
string a[N], b[N]; // 匹配规则
int n;// 扩展函数
// start与起点的距离
// end与终点的距离
// src匹配源
// dst匹配目标
int extend(queuestring q, unordered_mapstring, int start, unordered_mapstring, 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;queuestring qa, qb; // 各自的搜索队列// 当前状态到起点终点的距离unordered_mapstring, 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;
}
