poj2449 Remmarguts' Date【A*算法】

转载请注明出处，谢谢：http://www.cnblogs.com/KirisameMarisa/p/4303855.html ---by 墨染之樱花

【题目描述】：给出图，求从起点到终点的第K短路

【思路】：求第K短的算法基于BFS搜索，当终点出队K次时，所走的总距离就是第K短路，不过这样那些不该走的路会被反复的走，造成许多空间时间浪费，这时候就要用到启发式的A*搜索。关于此算法的详细内容请自行查阅资料，这里简单的提一下。A*算法利用一个估价函数f(n)=g(n)+h(n)，其中g(n)表示起点s到点n所耗费的实际代价，h(n)表示n到终点t所估计的代价，也就是说理想情况下从n到t还要耗费的代价，h(n)越接近真实值算法速度越快（实际上BFS就是h(n)始终为0的A*特例）。在网格图中h(n)可以为欧几里得距离或者是曼哈顿距离，在此题中，我们将从n到t的最短路作为h(n)。完成估价函数以后，我们以估价函数为优先级进行搜索（可以用优先队列实现，f(n)小的先搜索），这样就能大致保证搜索路径始终朝着我们想要的方向走，从而加快搜索速度。

 #include <iostream>

 #include <ios>

 #include <iomanip>

 #include <functional>

 #include <algorithm>

 #include <vector>

 #include <sstream>

 #include <list>

 #include <queue>

 #include <deque>

 #include <stack>

 #include <string>

 #include <set>

 #include <map>

 #include <cstdio>

 #include <cstdlib>

 #include <cctype>

 #include <cmath>

 #include <cstring>

 #include <climits>

 using namespace std;

 #define XINF INT_MAX

 #define INF 1<<30

 #define MAXN 1000+10

 #define eps 1e-10

 #define zero(a) fabs(a)<eps

 #define sqr(a) ((a)*(a))

 #define MP(X,Y) make_pair(X,Y)

 #define PB(X) push_back(X)

 #define PF(X) push_front(X)

 #define REP(X,N) for(int X=0;X<N;X++)

 #define REP2(X,L,R) for(int X=L;X<=R;X++)

 #define DEP(X,R,L) for(int X=R;X>=L;X--)

 #define CLR(A,X) memset(A,X,sizeof(A))

 #define IT iterator

 #define PI  acos(-1.0)

 #define test puts("OK");

 #define _ ios_base::sync_with_stdio(0);cin.tie(0);

 typedef long long ll;

 typedef pair<int,int> PII;

 typedef priority_queue<int,vector<int>,greater<int> > PQI;

 typedef vector<PII> VII;

 typedef vector<int> VI;

 #define X first

 #define Y second

 int V,E,S,T,K;

 int d[MAXN];

 VII G[MAXN];

 VII rG[MAXN];   //对反图dijkstra，求出每个点到终点的最短路，作为预计代价h(n)

 int cnt[MAXN]={};   //记录出队次数 

 void dijkstra(int s)

 {

     priority_queue<PII,VII,greater<PII> > Q;

     fill(d,d+V,INF);

     d[s]=;

     Q.push(MP(d[s],s));

     while(!Q.empty())

     {

         PII p=Q.top();Q.pop();

         int v=p.Y;

         if(d[v]<p.X)

             continue;

         REP(i,rG[v].size())

         {

             PII e=rG[v][i];

             if(d[e.X]>d[v]+e.Y)

             {

                 d[e.X]=d[v]+e.Y;

                 Q.push(MP(d[e.X],e.X));

             }

         }

     }

 }

 struct node    //A*搜索用节点

 {

     int num,g,h;

     bool operator<(const node &b)const

     {

         return g+h!=b.g+b.h?g+h>b.g+b.h:g>b.g;   //以f=g+h为第一关键字，g为第二关键字

     }

     node(int _num=,int _g=,int _h=){num=_num;g=_g;h=_h;}

 };

 int astar(int s,int t)

 {

     priority_queue<node> Q;

     node st(s,,d[s]);

     Q.push(st);

     while(!Q.empty())

     {

         node temp=Q.top();Q.pop();

         int u=temp.num,ug=temp.g,uh=temp.h;

         cnt[u]++;

         if(u==t && cnt[t]==K)

             return ug;

         if(cnt[u]>K)

             continue;

         REP(i,G[u].size())

         {

             int v=G[u][i].X,cost=G[u][i].Y;

             node next(v,ug+cost,d[v]);

             Q.push(next);

         }

     }

     return -;

 }

 int main()

 {_

     scanf("%d%d",&V,&E);

     REP(i,E)

     {

         int x,y,c;

         scanf("%d%d%d",&x,&y,&c);

         x--;y--;

         G[x].PB(MP(y,c));

         rG[y].PB(MP(x,c));

     }

     scanf("%d%d%d",&S,&T,&K);

     S--;T--;

     if(S==T)   //起点与终点相同时，最短路显然是0，不过不能算 ，所以k++

         K++;

     dijkstra(T);   //反向dijkstra，求出每个点到T的最短路，作为h(i)

     printf("%d\n",astar(S,T));

     return ;

 }

秒客网

poj2449 Remmarguts' Date【A*算法】

相关文章