CatCoding

A*算法解决 kth-shortest 路径问题 (2)

2012-09-18

我之前写过一篇图文并茂的文章来介绍这个算法,有好几次有朋友反馈说对自己有帮助,深感荣幸。这次再次写这个也是因为帮忙于一个朋友解决这类问题,这里再成一篇,稍显罗嗦。

问题描述

无向图 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*算法的复杂度,劳烦请教。

公号同步更新,欢迎关注👻