[算法学习]A*求第k短路

2021-02-09 16:17

阅读：730

标签：优先 k短路 pop spfa this size 估计 code for

A*是一种搜索算法，一般基于一个估价函数f(x) = g(x) + h(x)，通过这个函数来进行有方向的搜索以提高搜索的效率（而不是bfs、dfs那样的盲目搜索）
其中g(x)指从初始状态到当前状态的花费，h(x)为当前状态到终状态的最小花费，以两者之和来估计起始状态到终状态的总花费f(x)
在A*算法中，通过优先搜索最符合要求的f（x）表示的状态以提升搜索效率

在求第k短路的问题中，g(x)指的是由起点到达当前点的路径长度，h(x)指当前点到达终点的最短路
而此时我们需要优先对估价函数值较小的状态进行搜索
故而可以使用优先队列对数据进行处理

一般对h(x)提前进行预处理，使用Dijkstra/SPFA预先求好最短路
由于A*总能够优先搜索当前所有队列中结点距离终状态最近的结点，所以每次搜索到终点时都是当前最近的路
所以当第k次搜索到终点时的路径长度就是k短路的长度了

A*核心代码：

int cnt;
int Astar(){
    if(st == en) k++;
    if(dis[st] == inf) return -1;

    priority_queue q;
    ptr cur{st, dis[st], 0};

    q.push(cur);
    while(!q.empty()){
        ptr t = q.top();
        q.pop();
        int nt = t.now;

        if(nt == en) cnt++;
        if(cnt == k) return t.g;
        for(int i = 0; i ){
            int path = t.g + edges[nt][i].w;
            int now = edges[nt][i].to;
            q.push(ptr{now, path + dis[now], path});
        }
    }
    return -1;
}

st、en为起点、终点， dis数组为预处理的最短路

ptr结构体的定义：

struct ptr{
    int now, F, g; // 当前点编号， 估价函数F， 当前路径g
    bool operator const ptr& a) const {
        if(this->F == a.F) return this->g > a.g;
        return this->F > a.F;
    }
};

[算法学习]A*求第k短路

标签：优先 k短路 pop spfa this size 估计 code for

原文地址：https://www.cnblogs.com/leafsblogowo/p/12749535.html

上一篇：Java-水仙花数

下一篇：Java 多线程进阶-并发协作控制

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：[算法学习]A*求第k短路
文章链接：http://soscw.com/index.php/essay/53164.html

亲，登录后才可以留言！

[算法学习]A*求第k短路

评论

热门文章

推荐文章

最新文章

置顶文章