我之前写过一篇图文并茂的文章来介绍这个算法,有好几次有朋友反馈说对自己有帮助,深感荣幸。这次再次写这个也是因为帮忙于一个朋友解决这类问题,这里再成一篇,稍显罗嗦。
问题描述
无向图 G,需要求出 S->T 点的前 k 短路径,要求路径中没有环。(所有的边的权值不为负)
A*算法求解 kth-shortest 问题
A*
算法已经被广泛运用于路径规划问题中,同时A*
算法作为一种启发式算法的框架,可用于多种搜索问题,还是先回顾一下A*
的基本符号:
f(s)=g(s)+h(s)
,其中h(s)<=h*(s)
,h*(s)
是某点到终点的真实代价,h(s)
是估计代价,
并且对 s 的任意后继 t 有:h(t)+w(s,t)>=h(s)
,其中w(s,t)
是从 s 转移到 t 的代价,符合这条件的评估函数f(s)
可以得到正确的最短路径。
而这里评估函数f(s)
是A*
算法的关键,其效率都取决于此,退化的A*
算法就是宽度搜索 (即启发函数 h(s) 为常数)。另外A*
算法的最优性证明在这篇论文里有阐述。
所以如果能确切的计算出来h*(s)
,那么评估函数 f(s) 将是 s 点的最短路径,这可算是一个最优的启发函数。可以利用 Dijkstra 算法来求解出各个点到 T 点的最短路径,假设第 i 个节点到 T 的最短路径计为Dist_T(i)
,Dist_T(i)
作为A*
函数中的启发函数h(s)
,从 S 开始搜索,因此算法描述如下:
int Astar(){
if(dist[S]==INF) return -1;
priority_queue<Node> Q; //极小堆,定点为 f(s)=g(s)+h(s) 最小的节点
Q.push(Node(S,0)); //源点 S 加入堆,估计代价为 0
while(!Q.empty()){
int len=Q.top().len;
int u=Q.top().v;
Q.pop();
cnt[u]++; //节点 u 访问一次
if(cnt[T]==K)
return len; //第 K 次从队列弹出的值为 kth-shortest 的值
if(cnt[u]>K)
continue;
for(int i=0;i<Adj[u].size();i++) {
//取 v 节点的临接节点计算评估函数并加入优先队列
int v = Adj[u][i].v;
int eval = len + Dist(u,v) + Dist_T(v);
Q.push(Node(v, eval));
}
}
return -1;
}
因为没有标识哪些节点访问过哪些节点没有访问过,所以这种方法计算出来的结果路径可能含有环,即可能出现 1->2->3->2->5,为了避免这样的情况可以在每个扩张 Node 里面增加当前路径已经访问过的点,在进行下一次扩张的时候可以避免访问这些已经在路径中的节点。但是这样所需要的空间复杂度是巨大的,所以需要再次用一些剪枝办法来避免过多的扩展。
一个优化
A*
算法在扩展节点的时候,如果我们能筛除掉更多无用的节点,那么都可以利于减少搜索的空间复杂度和时间复杂度。当 k 取值较小的时候,即当我们并不需要知道所有路径长度和其排序,而只需要知道前 k(假设 k<=10) 段的路径,这里加上一个剪枝会有很大的优化。假设我们事前知道 kth-shortest 的最大值,就能在扩张的时候加入这个限制,避免大部分的无用的节点扩张。
for(int i=0;i<Adj[u].size();i++) {//取 v 节点的临接节点计算评估函数并加入优先队列
int v = Adj[u][i].v;
int eval = len + Dist(u,v) + Dist_T(v);
if(eval > max_dist)
continue;
else
Q.push(Node(v, eval));
}
如何知道 kth-shortest 的最大值这个临界点呢?假设我们知道某条经过点 v 的 S->T 路径的最短长度,即对于所有的点 v1,v2,v3,….vn,有 dist(v1) 为 S->…->v1-> …->路径的长度,一共 n 个 dist,把这 n 个 dist 排序以后,取第 k 小的 dist(v_kth_smallest) 即为 kth-shortest。如何计算出 dist(v),通过 Dijkstra(T) 可以计算出 v 到 T 的最短路径,同样可以通过 Dijkstra(S) 可以计算出 S 到 v 的最短路径 Dist_S(v),这里有如下定理:
对于任意最短路径 S->K 中,假设经过点 v,则必有:min(S->v) 和 min(v->T)。
因此要计算经过 v 的从 S->K 的最短路径可以用:min_dist(v) = Dist_S(v) + Dist_T(v)
因此如果我们用这种方法计算出 Dist(v),那么最后第 k 小的 dist(v_kth_smallest) >= kth-shortest。这对于A*
算法的最后结果没有影响,但是同样可以作为一个条件来删除掉大部分不符合条件的节点,因此得到一个很好的优化方案。这个优化可以用于k<N
时的 kth 最短路径问题,可以预见 k 越小剪枝效果越好。
据我实现在 18600 个节点的图上,这个算法比Yen’s 算法快了很多倍,甚至在我的 PC(3G 内存) 机上,后者在算到 k=3 的时候内存就支持不住了。
算法复杂度分析
假设图 G 有 m 条边和 n 个节点,Dijkstra 算法的复杂度为((m+n)log n)
(二叉树实现的优先队列)。A*
算法的时间复杂度取决于启发函数,事实我还不清楚如何分析这样的算法的时间复杂度和空间复杂度,根据这篇文章来说是O(delta*V^2*(lgV+lg(delta)))
的。
如果哪位知道如何分析 A*算法的复杂度,劳烦请教。