Yukang's Page

A*算法与K-shortest path问题

2010-08-02


那天师兄给面试,面到一道图算法题目,求图中两个点的前K短路径。当时觉得用Dijkstra+heap应该可以,不过也没想清楚。以前看到过这个,那时还没怎么仔细看图算法所以丢一边了, 今天好好看了一下。简单一点的解法是用Dijkstra+Astar。典型的题目就是POJ 2449

A* 算法

再谈A算法。A算法中的评估函数为f(N)=cost(N)+h(N)。其中cost(N)为从源点到N点的距离,h(N)为N点到终点的的一个评估路径长度,设h(N)为实际N点到终点的路径长度。只要满足条件: h(N)<=h(N),那么用这个评估函数找到最短路径。具体证明看这篇论文A Formal Basis for the Heuristic Determination of Minimum Cost Paths。 其优势在于在选择每个路径 上的点的时候给予了h(N)这个启发,在搜索空间中尽量选择可能最有可能产生最优解的下一个状态,使得搜索的时间都相应地减少。A算法的思想也是贪心 的,Dijkstra是A的一个特例,当h(N)=0时,A*就退化成了Dijkstra算法,那么就是盲目的扩展当前最短路径了。

来个例子,下面这是一个城市的公路图网,一共有18263个点,23874条边,视为无向图。我们知道起点和终点的坐标,现在我们要求某两点之间的最短路径。


1. 用Dijkstra算法来,其中白色的点表示搜索过程中访问了的点。可以看出Dijkstra算法有点像BFS向周围扩展,做了很多无用的搜索。当然这与图的形状也有一定关系。

[Dijkstra 访问18191个点]


2. 用A算法,设S为起点,T为终点,启发函数为F(N)=Path_Dist(S->N)+Dist(N->T)。在搜索过程中Path_Dist一直维持着S->N的路径长度,Disk(N->T)的计算可以有多钟选择,这里我选择 Dist(N->T)=sqrt(|Xn-Xt||Xn-Xt|+|Yn-Yt||Yn-Yt|),这个为两点之间的理论最短路径,肯定是满足条件h(N) <= h(N)的,那么能得到最优解。可以看到搜索偏向于目标点的方向。

[A* 两点之间距离为评估函数 访问4398个点]


3. 另外(x+y)/2 <= sqrt(x^2+y^2),所以也可以选择(|Xn-Xt|+|Yn-Yt|)/2作为启发函数。但为了节省这个sqrt的操作,代价就是访问了更多的点。

[A* (x+y)/2作为启发函数 访问14374个点]


4. 可以做得更好,修改启发函数。Dist(N->T)=|Xn-Xt|+|Yn-Yt|,这为曼哈顿函数,这样就不满足条件h*(N)<=h(N)了。所以得不到最优解,但是速度上会快很多,搜索的点也会减少很多。

[A* 曼哈顿距离作为启发函数 访问296个点]


大概能得到一个规律,搜索效率依赖于h(N)的启发作用,当h(N) <= h(N)时候,我们能得到最优解,用第二种启发函数能也满足最优解的条件,但是因为启发用少了所以访问了更多的点。当h(N)>h(N)时,得到的可能是比较优的解(非最短路径),可以认为因为得到的启发更多(多到超出了得到最优解的条件限制),所以能取得更快的效率。这又是一个普遍的问题,在速度、精确度两者之间经常会只能二选一,对于不同的应用从中作出折中。上面那篇论文证明了,对于刚才举例的这个问题,用两点之间的直线距离最为启发函数的A算法是所有能得到最优解的算法中访问点最少的。启发函数对于特定的问题有特定的取法,那么A*作为一个搜索的算法框架用处还是挺多的。

Dijkstra+A* 求k短路径


当然这个算法不是我想出来的,这里只是说一下看后自己的理解。在A算法中,优先队列出来的点如果扩展到了终点,那么 就得到了最短路径。如果能得到实际的评估函数(也就是h(N)),那么第二次 从优先队列里面弹出来的就是第2段的路径,依次直到k短。如何得到h(N),就是图中各个点到T的实际最短路径距离,可以从图的反向图以T为源点进行 Dijkstra算法,最后Dist[N]就可以作为h(N)。然后以cnt[N]表示N点从优先队列里面弹出来的次数。K-shortest问题还有更快的解法,不过还没看,这里有大把论文。这里还分结果路径中是否可以有环,像现实中公路网肯定是要求无环的k-shortest path。下面这个算法是可以有环的。


完整代码如下:

//7040K 282MS
#include <iostream>
#include <queue>
#include <vector>
#include <stdio.h>
#include <cstring>
using namespace std;
const int MAXN=1001;
const int INF=(1<<20);
int N,M; //N个点 M条边
int S,T,K; //起点和终点
typedef struct _Edge
{
int v;//边顶点
int len;//边长度
}Edge;
int dist[MAXN];
int cnt[MAXN];
bool mark[MAXN];
struct Node{
int v,len;
Node() {};
Node(int a,int b):v(a),len(b) {}
};
bool operator < (const Node& a,const Node& b)
{
return (a.len+dist[a.v]>b.len+dist[b.v]);
}
vector<Edge> Adj[MAXN];//图的邻接表表示
vector<Edge> Rev[MAXN];//图的逆图
void Init_graph()
{
int u,v,l;
Edge edge;
scanf("%d%d",&N,&M);
for(int i=0;i<M;i++)
{
scanf("%d%d%d",&u,&v,&l);
edge.v=v;
edge.len=l;
Adj[u].push_back(edge);
edge.v=u;
Rev[v].push_back(edge);
}
scanf("%d%d%d",&S,&T,&K);//计算S到T的第K短路径
if(S==T) K++;
}
//Dijkstra 算法 找出各个点到T的最短距离
void Dijkstra()
{
memset(mark,false,sizeof(mark));
for(int i=1;i<=N;i++)
dist[i]=INF;
dist[T]=0;
int u,v,min;
while(1)
{
u=-1,min=INF;
for(int i=1;i<=N;i++)
if(!mark[i] && dist[i]<min)
{
min=dist[i];
u=i;
}
if(u==-1) break;
mark[u]=true;
for(int k=0;k<Rev[u].size();k++)
{
v=Rev[u][k].v;
if(!mark[v] && dist[v]>dist[u]+Rev[u][k].len)
dist[v]=dist[u]+Rev[u][k].len;
}
}
}
int Astar()
{
if(dist[S]==INF) return -1;
memset(cnt,0,sizeof(cnt));
priority_queue<Node> Q;
Q.push(Node(S,0));
while(!Q.empty())
{
int len=Q.top().len;
int v=Q.top().v;
Q.pop();
cnt[v]++;
if(cnt[T]==K)
return len;
if(cnt[v]>K)
continue;
for(int i=0;i<Adj[v].size();i++)
Q.push(Node(Adj[v][i].v,len+Adj[v][i].len));
}
return -1;
}
int main()
{
Init_graph();
Dijkstra();
int ans=Astar();
printf("%d\n",ans);
return 0;
}
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章