1.自然语言描述 当状态空间树很大很大时（时间复杂度很高）从起点到终点直接BFS仍会超时；可以考虑分别从起点和终点双向BFS，双向BFS会将原来的状态空间树极大地缩小。
双向BFS的扩展方式：既然是双向BFS，则起点开始和终点开始各需要一个活结点队列，最短路径的保存记录也需要两个——各自相对于起点和终点的最短路径记录。扩展时，优先扩展两个队列中活结点较少的那一侧。
2.代码描述 题目：Acwing 190.字串变换 题目链接
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <unordered_map> #include <queue> using namespace std; const int MAXN=22; string a[MAXN],b[MAXN]; int n,cnt; int extend(queue<string> &qa,unordered_map<string,int> &da,unordered_map<string,int> &db,string a[],string b[]) { string t=qa.front(); qa.pop(); for(int i=0;i<(int)t.size();i++) for(int j=0;j<n;j++) if(t.substr(i,(int)a[j].size())==a[j]){ string state=t.substr(0,i)+b[j]+t.substr(i+a[j].size());//拼起来 if(db.count(state)) return da[t]+1+db[state];//state被对侧广搜搜到了,也就是双端广搜在此碰头 //从本侧广搜起点到t的步数为da[t],对侧广搜起点到state的步数为db[state],t扩展到state距离为1 else{ da[state]=da[t]+1; qa.push(state); } } return 11;//没有相遇 } int bfs(string A,string B) { queue<string> qa,qb; unordered_map<string,int> da,db; qa.push(A),qb.push(B); da[A]=0; db[B]=0; while(!qa.empty()&&!qb.empty()){ 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; } return 11; } int main(void) { string A,B; cin>>A>>B; while(cin>>a[n]>>b[n]) n++; int cnt=bfs(A,B); if(cnt>10) cout<<"NO ANSWER!"<<endl; else cout<<cnt<<endl; return 0; }