1 双向广搜
顾名思义就是从起点与终点同时bfs，直到会师就停止
可以将指数级别的时间复杂度降低为线性指数级别
1.字串变换
#include<bits/stdc++.h> using namespace std; const int N=6; int n; string a[N],b[N]; int extend(queue<string> &q,unordered_map<string,int> &da,unordered_map<string,int> &db,string a[],string b[]) { string t=q.front();//取出元素队头 q.pop(); for(int i=0;i<t.size();i++)//用该元素来进行更新新的状态 for(int j=0;j<n;j++)//n个更新规则 if(t.substr(i,a[j].size())==a[j])//假如可以更新 { string state=t.substr(0,i)+b[j]+t.substr(i+a[j].size());//新的状态 if(da.count(state)) continue;//假如之前已经更新过了 if(db.count(state)) return da[t]+1+db[state];//假如会师了，也就是b中有了他了，说明找到了，返回距离 da[state]=da[t]+1;//新的状态步数+1 q.push(state);//放进队列里头 } return 11;//反之找不到，返回大于10的数 } int bfs(string &A,string &B) { if(A==B) return 0; queue<string>qa,qb;//用来存储起点a,与终点b的bfs所用到的队列 unordered_map<string,int> da,db;//用来记录起点与终点到某个字符串的位置的距离 qa.push(A),qb.push(B); da[A]=0,db[B]=0; while(qa.size()&&qb.size())//假如有一方为空，说明起点与终点不连通 { int t; //第一个是从起点开始拓展，所以是qa,da,db,a,b说明a->b的规则 //第二个就是终点开始拓展，所以是qb,db,da,b,a说明b->a的规则 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;//假如返回的步数小于10，说明找到了 } return 11;//反之没结果，返回大于10的数 } int main() { string A,B; cin>>A>>B; while(cin>>a[n]>>b[n]) n++;//读入字串变换规则 int step=bfs(A,B);//求一下起点到终点的最小步数 if(step>10) puts("NO ANSWER!"); else cout<<step<<endl; return 0; }
2.八数码
#include<bits/stdc++.h> using namespace std; #define x first #define y second int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1}; string extend(queue<string> &q,unordered_map<string,int> &da,unordered_map<string,int> &db,unordered_map<string,pair<char,string>> &pre, char op[]) { string state=q.front(); q.pop(); int x,y; for(int i=0;i<state.size();i++)//找一下x的位置 if(state[i]=='x') { x=i/3,y=i%3; break; } string source=state; for(int i=0;i<4;i++)//进行四个方向的转移 { int a=x+dx[i],b=y+dy[i]; if(a<0||a>=3||b<0||b>=3) continue;//越界continue state=source; swap(state[x*3+y],state[a*3+b]);//交换一下位置，也即新的状态 if(da.count(state)) continue;//假如之前已经更新过了 da[state]=da[source]+1;//则更新一下最短距离 pre[state]={op[i],source};//记录由谁转化过来的和转换方式 q.push(state); if(db.count(state)) return state;//假如跟b会师了，返回会师时的状态 } return "0";//假如没找到 } string bfs(string &start) { string end="12345678x"; char op1[]="urdl",op2[]="dlur";//上左下右是个方向，一个是正的规则，一个是反着来的规则 unordered_map<string,int> da,db;//用来求距离 queue<string> qa,qb; unordered_map<string,pair<char,string>> prea,preb;//用来记录轨迹 da[start]=0,db[end]=0; qa.push(start),qb.push(end); string t; while(qa.size()&&qb.size()) { if(qa.size()<=qb.size()) t=extend(qa,da,db,prea,op1);//用元素少的进行拓展 else t=extend(qb,db,da,preb,op2); if(t!="0") break;//假如找到了，也就是会师，就跳出去 } string ans; string temp=t; while(start!=temp)//倒着记录轨迹 { ans+=prea[temp].x; temp=prea[temp].y; } reverse(ans.begin(),ans.end());//倒转一下即可 temp=t; while(temp!=end)//正着往回走 { ans+=preb[temp].x; temp=preb[temp].y; } return ans;//返回轨迹 } int main() { string start; char c; while(cin>>c) start+=c; int cnt=0; for(int i=0;i<9;i++)//求逆序对的个数 { if(start[i]=='x') continue; for(int j=i;j<9;j++) if(start[i]>start[j]) cnt++; } if(cnt&1) puts("unsolvable");//假如逆序对为奇数，则没答案 else cout<<bfs(start)<<endl;//反之bfs一遍 return 0; }
2 A*
A star算法基本很少用，但是也是bfs的一种优化
1.八数码
#include<bits/stdc++.h> using namespace std; #define x first #define y second typedef pair<int,string> pis; int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1}; int f(string a)//用来求估计函数，也就是这个点到终点的距离 { int dist=0; for(int i=0;i<a.size();i++)//用两点距离来求 if(a[i]!='x') { int t=a[i]-'1'; dist+=abs(i/3-t/3)+abs(i%3-t%3); } return dist; } string bfs(string start) { string end="12345678x"; char op[]="urdl";//上左下右是个方向 unordered_map<string,int> d;//用来求距离 unordered_map<string,pair<char,string>> pre;//用来记录轨迹 priority_queue<pis,vector<pis>,greater<pis>> heap;//用来存距离和点 d[start]=0; heap.push({f(start),start}); while(heap.size()) { auto t=heap.top(); heap.pop(); string state=t.y; if(state==end) break;//假如已经找到了，则直接跳出来 int x,y; for(int i=0;i<9;i++)//找一下x的位置 if(state[i]=='x') { x=i/3,y=i%3; break; } string source=state; for(int i=0;i<4;i++)//进行四个方向的转移 { int a=x+dx[i],b=y+dy[i]; if(a<0||a>=3||b<0||b>=3) continue;//越界continue state=source; swap(state[x*3+y],state[a*3+b]);//交换一下位置，也即新的状态 if(d.count(state)==0||d[state]>d[source]+1)//假如该状态还没更新过，或者有距离更短 { d[state]=d[source]+1;//则更新一下最短距离 pre[state]={op[i],source};//记录由谁转化过来的和转换方式 heap.push({f(state)+d[state],state}); } } } string ans; while(end!=start)//倒着记录轨迹 { ans+=pre[end].x; end=pre[end].y; } reverse(ans.begin(),ans.end());//倒转一下即可 return ans;//返回轨迹 } int main() { string start; char c; while(cin>>c) start+=c; int cnt=0; for(int i=0;i<9;i++)//求逆序对的个数 { if(start[i]=='x') continue; for(int j=i;j<9;j++) if(start[i]>start[j]) cnt++; } if(cnt&1) puts("unsolvable");//假如逆序对为奇数，则没答案 else cout<<bfs(start)<<endl;//反之bfs一遍 return 0; }
2.第K短路
#include<bits/stdc++.h> using namespace std; #define x first #define y second typedef pair<int,int> pii; typedef pair<int,pii> piii; const int N=1010,M=2e5+10; int n,m,S,T,K; int h[N],rh[N],e[M],w[M],ne[M],idx; int dist[N]; bool st[N]; int cnt[N]; void add(int h[],int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } void dijkstra()//用dijkstra来求估价函数f[i] { priority_queue<pii,vector<pii>,greater<pii>> heap; heap.push({0,T}); memset(dist,0x3f,sizeof dist); dist[T]=0; while(heap.size()) { auto t=heap.top(); heap.pop(); int ver=t.y; if(st[ver]) continue; st[ver]=true; for(int i=rh[ver];~i;i=ne[i]) { int j=e[i]; if(dist[j]>dist[ver]+w[i]) { dist[j]=dist[ver]+w[i]; heap.push({dist[j],j}); } } } } int astar() { priority_queue<piii,vector<piii>,greater<piii>>heap; heap.push({dist[S],{0,S}}); //谁的d[u]+f[u]更小 谁先出队列 while(heap.size()) { auto t=heap.top(); heap.pop(); int ver=t.y.y,distance=t.y.x; cnt[ver]++; if(cnt[T]==K) return distance; //如果终点已经被访问过k次了 则此时的ver就是终点T 返回答案 for(int i=h[ver];~i;i=ne[i]) { int j=e[i]; /* 如果走到一个中间点都cnt[j]>=K，则说明j已经出队k次了，且astar()并没有return distance, 说明从j出发找不到第k短路(让终点出队k次)， 即继续让j入队的话依然无解， 那么就没必要让j继续入队了 */ if(cnt[j]<K) { // 按 真实值+估计值 = d[j]+f[j] heap.push({distance+w[i]+dist[j],{distance+w[i],j}}); } } } // 终点没有被访问k次 return -1; } int main() { memset(h,-1,sizeof h); memset(rh,-1,sizeof rh); cin>>n>>m; while(m--) { int a,b,c; cin>>a>>b>>c; add(h,a,b,c); add(rh,b,a,c);//用来反向求距离 } cin>>S>>T>>K; if(S==T) K++; dijkstra(); cout<<astar()<<endl; return 0; }
