POJ 2449 - A*初步+ K短路

原以为A*会很难懂~~~结果狐狸大大一口气就给我讲懂了A*和K短路的求法.....

所谓A*就是启发是搜索..说白了就是给BFS搜索一个顺序使得搜索更加合理减少无谓的搜索..如何来确定搜索的顺序？..也就是用一个值来表示这个值为f[x]..每次搜索取f[x]最小的拓展...那么这个f[x]=h[x]+g[x]其中这个h[x]就是当前搜索时的代价..如求K段路这个就是前一个点的h[x']+边的长度...而g[x]是一个估价函数..估价函数要小于是对当前点到目标的代价的估计..这个估计必须小于等于实际值~~否则会出错...A*的关键也就是构造g[x]..

而这里要说的求K短路一种方法..就是用BFS+A*来搜索的过程...g[x]的设定为到这个点到目标点的最短路径...显然其实小于等于实际值的...h[x]就是搜索到这个点的代价..用一个优先队列来做..每次取出h[x]+g[x]最小的点来拓展...拓展也就是通过这点来更新其能直接经过一条边到达的点..这里做好一个新点就丢进优先队列里去..反正总会从对首弹出h[x]+g[x]最小的点..可以想一下...如果当前取出的优先队列头是一个点e并且是第一次取出h..那么就找到了一条从源点到h的最短路径..这里其实很djikstra的感觉差不多..如果第二次在对头取出了e..则是找到了一条从源点到h的第二短路径..依次类推..第几次从对头弹出e..则找到了从源点到e的第几短路径..

那要是本身就不存在K短路呢？？那就是e拓展不到K但是其他点很有可能一直打圈圈无限下去...这里就要用个条件来判断一下...首先在找某个点作为优先队列头出现了几次就用了一个计数器times[]..所求的点times[e]==k就代表得到了解..如果当前想拓展的点times[]>k就没必要拓展了..因为这个点已经是求到k+1短路了..从这个点继续往下搜肯定得到的是大于等于k+1短路的路径...就像1->2有3条路..2->3有2条路..那1->3有6条路的概念差不多..没必要对其进行拓展了..

还有一点要特别注意的就是题目要求必须要走..也就是s==e时..k++....

补充说一下STL的priority_queue 也就是STL就已经有一个优先队列了..像sort一样的可以直接使用..

声明 #include<queue>

定义 priority_queue<类型> 变量名

但注意的是若是对结构体用..则需要在结构体中对 < 进行重载...如这道题的struct就应该写成这样:

struct node
{
     int p,g,h;
     bool operator < (node a) const
     { 
          return a.g+a.h<g+h;
     }     
}; 

这样用priority_queue就能按需求来进行优先级了...插入时用push..取队首用top..再弹出pop...判空empty...啥啥的..和一般的queue一样...很好使...

Program:

#include<iostream>
#include<queue>
#define MAXN 1001
using namespace std;
struct node
{
     int p,g,h;
     bool operator < (node a) const
     { 
          return a.g+a.h<g+h;
     }     
};
struct node1
{
     int x,y,w,next;      
}line[MAXN*100],line1[MAXN*100];
int n,m,i,link[MAXN],link1[MAXN],g[MAXN],s,e,k;
bool used[MAXN];
priority_queue<node> myqueue; 
void djikstra()
{ 
     int i,k,p;
     memset(used,0,sizeof(used));
     memset(g,0x7F,sizeof(g)); 
     g[e]=0;
     for (p=1;p<=n;p++)
     {
          k=0;
          for (i=1;i<=n;i++) 
            if (!used[i] && (!k || g[i]<g[k]))
              k=i;
          used[k]=true;
          k=link1[k];
          while (k)
          {
               if (g[line1[k].y]>g[line1[k].x]+line1[k].w)
                   g[line1[k].y]=g[line1[k].x]+line1[k].w;
               k=line1[k].next;               
          }
     }
     return ;    
}
int Astar()
{
     int t,times[MAXN];
     node h,temp;
     while (!myqueue.empty()) myqueue.pop();
     memset(times,0,sizeof(times)); 
     h.p=s; h.g=0; h.h=0; myqueue.push(h);
     while (!myqueue.empty())
     {
           h=myqueue.top();
           myqueue.pop();
           times[h.p]++; 
           if (times[h.p]==k && h.p==e) return h.h+h.g;   
           if (times[h.p]>k) continue;     
           t=link[h.p];
           while (t)
           { 
                 temp.h=h.h+line[t].w;
                 temp.g=g[line[t].y];
                 temp.p=line[t].y;
                 myqueue.push(temp);
                 t=line[t].next;
           } 
     }
     return -1;   
}
int main()
{ 
     scanf("%d%d",&n,&m);
     memset(link,0,sizeof(link)); 
     memset(link1,0,sizeof(link1));
     for (i=1;i<=m;i++)
     {         
          scanf("%d%d%d",&line[i].x,&line[i].y,&line[i].w);
          line[i].next=link[line[i].x]; link[line[i].x]=i;   
          line1[i].x=line[i].y; line1[i].y=line[i].x; line1[i].w=line[i].w;
          line1[i].next=link1[line1[i].x]; link1[line1[i].x]=i;    
     }
     scanf("%d%d%d",&s,&e,&k);
     if (s==e) k++;
     djikstra();
     printf("%d\n",Astar()); 
     return 0;   
}