K短絡——A*アルゴリズム

A*
概要:

A∗A∗(Astar)は、啓発的な検索であり、bfs b f sの特例でもある.正確にはbfs bfsは盲目的な探索である.

では、A

は、実際には、終点から始点までの最短回路を前処理し、始点から終点までのK番目の短絡を判断する.

これは非常に実用的なK番目の短絡問題を解決するアルゴリズムである.

従来の動作:-終点から始点(逆図)までの最短回路(SPFA,Dijs)-を先に処理してから、始点から終点までの経路を優先キューでK番目の短絡と判断する
Code(テンプレート):

int S,T,K;

struct edge{
    int to,cost;
};
vectorE[N],G[N];

int dis[N];
bool vis[N];
queue<int>Q;

void SPFA(){//   T->S 
    while(!Q.empty())Q.pop();
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f3f3f3f,sizeof(dis));

    Q.push(T);
    vis[T]=1;
    dis[T]=0;

    while(!Q.empty()){
        int x=Q.front();Q.pop();
        vis[x]=0;
        for(int i=0;iint)G[x].size();++i){
            int y=G[x][i].to;
            if(dis[y]>dis[x]+G[x][i].cost){
                dis[y]=dis[x]+G[x][i].cost;
                if(!vis[y]){
                    vis[y]=1;
                    Q.push(y);
                }
            }
        } 
    }
}

struct Anode{
    int to,d,all;
    bool operatorconst Anode &_)const{
        return all==_.all?d>_.d:all>_.all;
    }
};
priority_queueStar;

int Astar(){//S->T
    if(dis[S]==0x3f3f3f3f)return -1;
    if(S==T)K++;
    int cnt=0;

    while(!Star.empty())Star.pop();

    Star.push((Anode){S,0,dis[S]});

    while(!Star.empty()){
        Anode now=Star.top();Star.pop();
        int x=now.to;
        if(x==T){
            cnt++;
            if(cnt==K)return now.d;
        }
        for(int i=0;iint)E[x].size();i++){
            int y=E[x][i].to;
            Star.push((Anode){y,now.d+E[x][i].cost,now.d+E[x][i].cost+dis[y]});
        }
    }
    return-1;
}

Summary:

AΘ(nm) Θ ( n m ) .

大きなデータに対しては、やはり左偏樹が並んで解決できる...しかし、書き方は非常に便利です.

例題:POJ 2449 Remmarguts’Date
Description:
n個の点、m本の辺の有向図、sからtの第k短絡を求めます.
Solution:

A*アルゴリズムは第k短絡裸問題を解決する.

Code:

#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define REP(i,f,t)for(int i=(f),i##_end_=(t);i<=i##_end_;i++)
#define SREP(i,f,t)for(int i=(f),i##_end_=(t);i
#define DREP(i,f,t)for(int i=(f),i##_end_=(t);i>=i##_end_;i--)
#define db double
#define LL long long 
#define INF 0x3f3f3f3f
#define MINF 0xc0c0c0c0
#define inf 0x3f3f3f3f3f3f3f
#define Sz(a)sizeof(a)
#define mcl(a,b)memset(a,b,Sz(a))
#define mcp(a,b)memcpy(a,b,Sz(b))
#define pb push_back
#define fi first
#define se second
template<class T>inline bool chkmin(T&x,T y){return y1:0;}
template<class T>inline bool chkmax(T&x,T y){return x1:0;}
inline LL Max(LL x,LL y){return x>y?x:y;}
inline LL Min(LL x,LL y){return xtypedef pair<int,int>PII;

#define N 1002
#define M 500002

int n,m;
int S,T,K;

int qwq1,qwq2,head1[N],head2[N];
struct edge{
    int to,next,cost;
}E[M],G[M];
void addedge(int x,int y,int z){
    E[qwq1]=(edge){y,head1[x],z};head1[x]=qwq1++;
    G[qwq2]=(edge){x,head2[y],z};head2[y]=qwq2++;
}

int dis[N];
bool vis[N]; 
queue<int>Q;

struct Anode{
    int to,d,all;
    bool operatorconst Anode &_)const{
        return all==_.all?d>_.d:all>_.all;
    }
};
priority_queueStar;

void SPFA(){
    while(!Q.empty())Q.pop();
    mcl(dis,INF);
    mcl(vis,0);

    Q.push(T);
    dis[T]=0;
    vis[T]=1;

    while(!Q.empty()){
        int x=Q.front();Q.pop();
        vis[x]=0;
        for(int i=head2[x];~i;i=G[i].next){
            int y=G[i].to;
            if(chkmin(dis[y],dis[x]+G[i].cost)){
                if(!vis[y]){
                    vis[y]=1;
                    Q.push(y);
                }
            }
        }
    }
}

int Astar(){
    int cnt=0;
    if(S==T)K++;
    if(dis[S]==INF)return-1;

    while(!Star.empty())Star.pop();

    Star.push((Anode){S,0,dis[S]});

    while(!Star.empty()){
        Anode now=Star.top();Star.pop();
        int x=now.to;
        if(x==T){
            cnt++;
            if(cnt==K)return now.d;
        }
        for(int i=head1[x];~i;i=E[i].next){
            int y=E[i].to;
            Star.push((Anode){y,now.d+E[i].cost,now.d+E[i].cost+dis[y]});
        }
    }
    return-1;
}
void Clear(){
    qwq1=qwq2=0;
    mcl(head1,-1);
    mcl(head2,-1);
}

int main(){
//  printf("sz=%d
",(Sz(E)*2+Sz(dis)*2+Sz(Star)+Sz(Star))/1024/1024);
    while(~scanf("%d%d",&n,&m)){

        Clear();

        REP(i,1,m){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            addedge(a,b,c);
        }
        scanf("%d%d%d",&S,&T,&K);
        SPFA();
        printf("%d
",Astar());
    }
    return 0;
}