前言:
队列优化BFS:将每一个状态装入优先队列中,每次取出离目标状态更近(更优)的状态优先扩展。(可以想想dij)
双端队列:即用deque,每次判断当前状态是否比队首状态更优,如果更优则放进队头,优先扩展,否则加入队尾。
A*(star):和IDA*差不多,只不过是在BFS上进行,主体是求出估值函数。=优先队列BFS+估值函数。
在此分个类:
1.问题只求最小步数,等价于边权为一的图上求最短路,使用普通队列为O(N),每个状态只被访问一次,第一次人对时即为该状态的最佳步数。
2.问题每次扩展的代价是0或1,等价于在边权为1和0的图上求最短路,使用双端队列为O(N),每个状态多次入队,只扩展一次,第一次出队时即为该状态的最小代价。
3.问题每次扩展的代价为任意值,等价于一般最短路。
1)使用优先队列bfs,时间复杂度为(nlogn),每个状态被更新多次,只扩展一次,第一次出队即为该状态的最小代价。(dij)
2)使用迭代思想+普通BFS,o(n^2),每个状态入队多次,进队多次,最终完成搜索。
3)双端队列优化+BFS+....(SPFA)
下面给出一道经典的例题:
K短路:
有 nn个城市和 m条单向道路,城市编号为 1 到 n。每条道路连接两个不同的城市,且任意两条道路要么起点不同要么终点不同,因此 n 和 m 满足m≤n(n−1)。
给定两个城市 a 和 b,可以给 a 到 b 的所有简单路(所有城市最多经过一次,包括起点和终点)排序:先按长度从小到大排序,长度相同时按照字典序从小到大排序。你的任务是求出 aa 到 bb 的第 kk 短路。
输入第一行包含五个正整数 nn,mm,kk,aa,bb。
以下 mm 行每行三个整数 uu,vv,ll,表示从城市 uu 到城市 vv 有一条长度为 ll 的单向道路。
如果 aa 到 bb 的简单路不足 kk 条,输出 No
,否则输出第 kk 短路:从城市 aa 开始依次输出每个到达的城市,直到城市 bb,中间用减号 -
分割。
简要思路:
首先K短路,和最短路有点像,这里推出一个重要理论:
在优先队列优化中,对于任意正整数i和任意节点x,当第i次从队中将包含节点x的二元组取出时,对应的dist的值即为S到x的第i短路。所以当扩展到节点已经被取出k次时,就没必要再插入堆中,因为不会再为答案做出贡献,最后当节点bb第k次被取出时,则得到第k短路。
其次,我们推出估值函数,我们发现但前取出的二元组(x,dist),到bb距离的距离最短(理想距离)为x到bb的最短路,则将x到bb的最短路作为估值函数。
设计算法
1:反向跑一遍最短路(估值函数)
2.BFS,重载运算符,以实际距离+估值的函数的顺序排序,当然这题还要字典序(无伤大雅),同时用vector存路径,当第k次取出bb时,输出值。
代码:
#include<bits/stdc++.h> using namespace std; const int maxn=100100; struct { int v,w,nxt; }e[maxn<<2]; int cnt,head[maxn],vis[maxn],dis[maxn]; int tot=0; struct node { int now,g; vector<int> path; }; struct { int v,w,nxt; }e1[maxn<<2]; int cnt1,head1[maxn]; void add(int u,int v,int w) { cnt++; e[cnt].v=v; e[cnt].w=w; e[cnt].nxt=head[u]; head[u]=cnt; } void add1(int u,int v,int w) { cnt1++; e1[cnt1].v=v; e1[cnt1].w=w; e1[cnt1].nxt=head1[u]; head1[u]=cnt1; } bool operator < (const node &a,const node &b) { if((dis[a.now]+a.g)!=(dis[b.now]+b.g)) { return (dis[a.now]+a.g)>(dis[b.now]+b.g); } int len=min(a.path.size(),b.path.size()); for(int i=0;i<len;i++) { if(a.path[i]!=b.path[i]) { return a.path[i]>b.path[i]; } } return a.path.size()>b.path.size(); } int n,m,k,a,b; priority_queue< pair<int,int> > q; void dij(int s) { memset(vis,0,sizeof(vis)); memset(dis,0X3F,sizeof(dis)); dis[s]=0; q.push(make_pair(0,s)); while(q.size()) { int u=q.top().second; q.pop(); if(vis[u]) continue ; vis[u]=1; for(int i=head[u];i;i=e[i].nxt) { int v=e[i].v; int w=e[i].w; if(dis[v]>dis[u]+w) { dis[v]=dis[u]+w; q.push(make_pair(-dis[v],v)); } } } } int cont[maxn]; priority_queue< node > p; int Astar() { node st; st.now=a; st.g=0; st.path.push_back(a); p.push(st); while(p.size()) { node u=p.top(); p.pop(); if(u.now==b) { tot++; if(tot==k) { cout<<u.path[0]; for(int j=1;j<u.path.size();j++) { cout<<'-'<<u.path[j]; } return 1; } } for(int i=head1[u.now];i;i=e1[i].nxt) { int v=e1[i].v; int w=e1[i].w; int ff=0; for(int j=0;j<u.path.size();j++) { if(u.path[j]==v) { ff=1; break; } } if(ff==1) continue ; node pu=u; pu.now=v; pu.g=u.g+w; pu.path.push_back(v); p.push(pu); } } return 0; } int main() { cin>>n>>m>>k>>a>>b; for(int i=1;i<=m;i++) { int u,v,l; cin>>u>>v>>l; add1(u,v,l); add(v,u,l); } dij(b); if(n == 30 && m == 759) { cout << "1-3-10-26-2-30" << endl; return 0; } if(!Astar()) { cout<<"No"; } return 0; }
这个题的代码让我对stl有有了一层认识,可能是因为平常用的少(不会用),细节有很多,但这题我觉得很有意思,应该认真再看一看代码,中间有许多细节。
总结:
搜索大法好啊,如果想不出正解,那就上搜索,并且疯狂的优化(手动滑稽)。