A* & IDA*搜索-白红宇

A* & IDA*搜索

阅读量：3953 次

发布时间：2019-05-24

本文共 1968 字，大约阅读时间需要 6 分钟。

$f (n) = g (n) + h (n)$

不但考虑前向代价，而且考虑后向代价。由于后向代价不可知，因而需要使用估价函数。

题目

求次短路，先反向SPFA准确求出

h (n)

准确的后向代价，再用A*搜索，第几次去到终点就是第几短路。

#include
   
    using namespace std;using ll=long long;const int maxn=1e5+10;struct Edge{
       int to;    ll len;    Edge(int a=0,ll b=0ll):to(a),len(b) {
   }    bool operator< (const Edge& e) const {
           return len > e.len;    }};struct Path{
       int u;    ll g,h;    Path(int a,ll b,ll c):u(a),g(b),h(c) {
   }    bool operator< (const Path& p) const {
           return g+h > p.g+p.h;    }};struct E{
       int to,next;    ll len;}e[2*maxn];int n,m,head[maxn];ll h[maxn];bool vis[maxn];int cnt=0;void add(int v,int u,ll len){
       e[cnt]={
   u,head[v],len};    head[v]=cnt++;    e[cnt]={
   v,head[u],len};    head[u]=cnt++;}void spfa(){
       queue
    
      Q;    Q.emplace(n);    memset(vis,0,sizeof vis);    memset(h,0x7f,sizeof h);    h[n]=0;    while(!Q.empty()){
           int now=Q.front();        Q.pop();vis[now]=false;        for(int i=head[now];~i;i=e[i].next){
               if(e[i].len+h[now]>h[e[i].to])continue;            h[e[i].to]=e[i].len+h[now];            if(vis[e[i].to])continue;            vis[e[i].to]=true;            Q.emplace(e[i].to);        }    }}ll Astar(){
       priority_queue
     
       Q;    Q.emplace(1,0,h[1]);    int cnt=0;    while(!Q.empty()){
           Path now=Q.top();        Q.pop();        if(now.u==n && ++cnt==2)return now.g+now.h;  //次短路为2，若k短路改为++cnt==k        for(int i=head[now.u];~i;i=e[i].next){
               ll before=now.g+e[i].len,after=h[e[i].to];            Q.emplace(e[i].to,before,after);        }    }    return 0;}int main(){
       int T;    cin>>T;    while(T--){
           cin>>n>>m;        int u,v;        for(int i=1;i<=n;++i)            head[i]=-1;        cnt=0;        ll len;        while(m--){
               cin>>u>>v>>len;            add(u,v,len);        }        spfa();        cout<
      
       <