网站建设怎么,wordpress采集微信公众文章,网站空间支持什么程序,wordpress谷歌地图插件怎么用第五十二章 BFS进阶#xff08;二#xff09;——双向广搜一、双向广搜1、优越之处2、实现逻辑3、复杂度分析二、例题1、问题2、分析3、代码一、双向广搜
1、优越之处
双向广搜是指我们从终点和起点同时开始搜索#xff0c;当二者到达同一个中间状态的时候#xff0c;即相…
第五十二章 BFS进阶二——双向广搜一、双向广搜1、优越之处2、实现逻辑3、复杂度分析二、例题1、问题2、分析3、代码一、双向广搜
1、优越之处
双向广搜是指我们从终点和起点同时开始搜索当二者到达同一个中间状态的时候即相遇。
那么这么搜有什么好处呢
我们知道在很多题目中我们使用BFS的时间复杂度是指数级别的。
也就是说如果讲BFS的进行次数画成一个函数的话就会画成下面这个图。 如果我们采取从两端出发到中间某点相遇的做法。
那么示意图可以画成下面的样子
可能原来我们需要进行A次搜索但是双向广搜的话我们就只需要进行B次搜索。上图仅仅表示一个大概意思目的仅仅为了突出双向广搜进行了很大的优化请勿追究细节
除了上面这种大致的表示方法外我们还可以画成一个搜索树的形式来看。 红色绿色线交叉的部分组成的菱形是双向广搜过程中所需搜索的状态数量。
上面的两个图仅仅是感性的分析了一下双向广搜的优越之处。
我们还需要量化计算一下到底优化了多少具体的时间复杂度是多少在分析复杂度之前我们需要先看一下双向广搜大体的实现逻辑。
2、实现逻辑
我们创建两个队列。
一个队列从起点开始广搜一个队列从终点开始广搜。
而在BFS中我们的执行次数和队列中的元素是相关的。我们队列中的元素越多BFS需要扩展的就越多。所以我们可以通过队列中的元素个数来代表一个BFS扩展时的复杂程度。
因此我们可以比较两个BFS的队列中的元素谁队列中元素少就对哪个BFS进行拓展。
3、复杂度分析
根据上面的算法实现我们可以知道基本上就是从终点开始的BFS和从起点开始的BFS轮流进行。
我们可以认为二者进行的次数是一样的。
假设二者一共扩展了KKK次那么各自可以认为进行了k/2k/2k/2次。
这里的拓展是只刚才搜索树中的层。假设每次扩展是多两个状态入队那么总共的状态就是12122....2k/2−11 2^1 2^2 ....2^{k/2-1}12122....2k/2−1求和以后约等于2k/22^{k/2}2k/2那么两个BFS加起来就是2k/212^{k/21}2k/21。
如果单向广搜的话按照刚才的求和公式对kkk层的状态求和大概是2k2^{k}2k
那么我们就发现优化了大约2k/22^{k/2}2k/2倍。
二、例题
1、问题 2、分析
过程很简单就是从起点开始枚举每一个可能的变化直到最后变成了B。
由于我们已经知道了终点过程所以可以同时从B到A开始变化。一直到二者中间状态重合。
3、代码
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int N 6;
int n;
string A, B;
string a[N], b[N];
int extend(queuestring q, unordered_mapstring, int da,unordered_mapstring, intdb,string a[N], string b[N])
{int d da[q.front()];while(q.size() da[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, a[i].size()) a[i]){string r t.substr(0, j) b[i] t.substr(j a[i].size());if(db.count(r))return da[t] db[r] 1;if(da.count(r))continue;da[r] da[t] 1;q.push(r);}}}}return 11;
}
int bfs()
{if(A B)return 0;queuestringqa, 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;if(qa.size() qb.size()){t extend(qa, da, db, a, b);}else{t extend(qb, db, da, b, a);}if(t 10)return t;if(step 10)return -1;}return -1;
}void solve()
{cin A B;while(cin a[n] b[n])n ;int t bfs();if(t -1)cout NO ANSWER!\n;else cout t \n;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);solve();
}
