学步园

很久以前便想做做K短路了。只是无奈鄙人这苦逼的小菜啊~。

首先讲讲A*算法吧。众所周知，A*算法就是启发式搜索，基本形式就是这样:f(x)=g(x)+h(x);其中f(x)代表在x点所需要的总代价，而g(x)代表：从源点到x点已经耗费的实际代价，h(x)代表从x到终点需要的估计代价，这个函数是一个估计值.而从x到终点真正需要的代价为h*(x)，在整个启发式搜索中我们必须保证h(x)<=h*(x);不然的话会由于对当前的估价值过高，则会引起答案的错误。构建A*的关键在于准确的规划一个h(x)函数，使得接近h*(x),这样的搜索会使得答案又快又准。可以想象h(x)过小会使得解空间过大，这样搜索出来的结果会很准确但是速度太慢，而对h(x)的过高估计，即估计代价太大会使得结果不准确。

这样我们可以理解了BFS的搜索过程，BFS的搜索过程中没有考虑到h(x)的估计代价，也就是说h(x)=0,只考虑g(x)的实际代价。这样根据实际代价来进行搜索，虽然可以说是很恶心的A*,同样地我们可以知道，BFS的解空间确实很大。

第一次写A*,目前只会应用在K短路上。不过也有点感觉了，关键在于h(x)的设计！

谈具体的实现：

首先我们在解空间取出的就是f(x)最小的，这样我们就要运用到优先队列了。这里提供一个使用C++系统优先队列的方法：

C++的STL中自带了优先队列，通过重载运算法"<",可以实现我们需要的对f(x)的自动维护。

描述一下怎样用启发式搜索来解决K短路。

首先我们知道A*的基础公式：f(x)=g(x)+h(x);对h(x)进行设计，根据定义h(x)为当前的x点到目标点t所需要的实际距离。也就是说x->t距离，由于有很多的节点都是到t的距离，为了计算这个估计值，当然必须先算出x->t的最短路径长度。显然x的值很多而t的值只有一个，对每个x去求单源点最短路径当然不划算！于是反过来做，从t点出发到其他点的单源点最短路径，这样吧估价函数h(x)都求出来，注意这样求出来的h(x)=h*(x);

然后就可以对构造完的h(x)开始启发式搜索了。

首先的点当然就是定义头结点了，头结点的已消耗代价为0,估计代价为h[s],下一个点为v;进入队列，开始for循环。每次取出队头的f(x)最小的节点对其他节点进行拓展。对当前节点的拓展次数++，若当前节点的拓展次数超过K,显然不符合要求，则不进行拓展。若对t节点的拓展次数恰好为K,则找到了所需要的。对当前节点的拓展次数即为到当前节点的第几短路。找到需要节点的K短路后，返回g(t)即可，也就是通过K次拓展的实际消耗的长度。

在for循环中的入队情况：当前节点的可拓展所有边，的所有状态都入队，当前节点到拓展节点的实际代价为当前节点的实际代价+两节点之间的边长。下个节点就是拓展节点，估计函数的值则为拓展节点到目标节点的距离h(x);

下面是解决的Code:

#include<iostream><br /> #include<cstdio><br /> #include<queue><br /> #define MAXN 1005<br /> #define MAXM 200100<br /> using namespace std;</p> <p>struct Node{<br /> int v,c,nxt;<br /> }Edge[MAXM];</p> <p>int head[MAXN];<br /> int tail[MAXN];<br /> int h[MAXN];</p> <p>struct Statement<br /> {<br /> int v,d,h;<br /> bool operator <( Statement a )const<br /> { return a.d+a.h<d+h; }<br /> };</p> <p>void addEdge( int u,int v,int c,int e )<br /> {<br /> Edge[e<<1].v=v;<br /> Edge[e<<1].c=c;<br /> Edge[e<<1].nxt=head[u];<br /> head[u]=e<<1;</p> <p> Edge[e<<1|1].v=u;<br /> Edge[e<<1|1].c=c;<br /> Edge[e<<1|1].nxt=tail[v];<br /> tail[v]=e<<1|1;<br /> return ;<br /> }</p> <p>void Dijstra( int n,int s,int t )<br /> {<br /> bool vis[MAXN];<br /> memset( vis,0,sizeof(vis) );<br /> memset( h,0x7F,sizeof(h) );<br /> h[t]=0;<br /> for( int i=1;i<=n;i++ )<br /> {<br /> int min=0x7FFF;<br /> int k=-1;<br /> for( int j=1;j<=n;j++ )<br /> {<br /> if( vis[j]==false && min>h[j] )<br /> min=h[j],k=j;<br /> }<br /> if( k==-1 )break;<br /> vis[k]=true;<br /> for( int temp=tail[k];temp!=-1;temp=Edge[temp].nxt )<br /> {<br /> int v=Edge[temp].v;<br /> if( h[v]>h[k]+Edge[temp].c )<br /> h[v]=h[k]+Edge[temp].c;<br /> }<br /> }<br /> }</p> <p>int Astar_Kth( int n,int s,int t,int K )<br /> {<br /> Statement cur,nxt;<br /> //priority_queue<Q>q;<br /> priority_queue<Statement>FstQ;</p> <p> int cnt[MAXN];<br /> memset( cnt,0,sizeof(cnt) );<br /> cur.v=s;<br /> cur.d=0;<br /> cur.h=h[s];</p> <p> FstQ.push(cur);</p> <p> while( !FstQ.empty() )<br /> {<br /> cur=FstQ.top();<br /> FstQ.pop();</p> <p> cnt[cur.v]++;<br /> if( cnt[cur.v]>K ) continue;<br /> if( cnt[t]==K )return cur.d;</p> <p> for( int temp=head[cur.v];temp!=-1;temp=Edge[temp].nxt )<br /> {<br /> int v=Edge[temp].v;<br /> nxt.d=cur.d+Edge[temp].c;<br /> nxt.v=v;<br /> nxt.h=h[v];<br /> FstQ.push(nxt);<br /> }<br /> }<br /> return -1;<br /> }</p> <p>int main()<br /> {<br /> int n,m;<br /> while( scanf( "%d %d",&n,&m )!=EOF )<br /> {<br /> int u,v,c;<br /> memset( head,0xFF,sizeof(head) );<br /> memset( tail,0xFF,sizeof(tail) );</p> <p> for( int i=0;i<m;i++ )<br /> {<br /> scanf( "%d %d %d",&u,&v,&c );<br /> addEdge( u,v,c,i );<br /> }<br /> int s,t,k;<br /> scanf( "%d %d %d",&s,&t,&k );<br /> if( s==t ) k++;<br /> Dijstra( n,s,t );<br /> printf( "%d\n",Astar_Kth( n,s,t,k ) );<br /> }<br /> return 0;<br /> }<br />
A完这题后

1.学会了用数组来定义链表，

2.使用STL的优先队列

3.A*搜索的初步理解

4.K短路的一种求解方法。

：）