Astar A* 算法路径搜索应用

在求解路径问题时，往往会搜索许多不必要的路径，计算机无法简单地实现人的宏观思维

所以，可以给当前需要搜索的路径增设一个估价函数，令计算机判断当前的最优解，这样可以节省许多不必要的时间开支

估价函数预处理出每个状态到目标状态的所需代价的估计值 $f(x)$，实际值为 $g(x)$，应当满足估计值不大于实际值 $f(x)\le g(x)$ （越接近越准确），这样的带有估价函数的优先队列 BFS 叫做 Astar 算法

在 BFS 过程中，维护一个堆，每次取出堆中 当前代价+未来估价 的最小状态进行扩展

例如求解第 $K$ 短路问题：给定 $n$ 个节点与 $m$ 条边的有向图，求从 $s$ 到 $t$ 的第 $K$ 短路

未来估价函数的计算

设 $f_i$ 表示第 $i$ 个节点到 $t$ 的距离，这里可以通过 Dijkstra 算法，以 $t$ 为起点 $s$ 为终点跑一遍，最后可以计算出精确的 $f_i=g_i$

注意需要额外存一张反向图，这里以 rhe 表示

struct edge{
    long long v,w;
};
vector<edge> rhe[5010];

void dijkstra(void){
    priority_queue<pair<long long,long long>> q;
    memset(f,0x3f,sizeof f);
    f[t]=0;
    q.push({0,t});
    while (q.size()){
        auto t=q.top();
        q.pop();
        if (vis[t.second]) continue;
        vis[t.second]=1;
        for (auto iter:rhe[t.second]){
            if (f[iter.v]>f[t.second]+iter.w){
                f[iter.v]=f[t.second]+iter.w;
                q.push({-f[iter.v],iter.v});
            }
        }
    }
}

Astar的实现

正向跑一边优先队列的 BFS，堆中维护三元组 $\{dis_{s,i}+f_i,i,d\}$，按照 $dis_{s,i}+f_i$ 从小到大排序

分别表示： $s$ 到 $i$ 的距离 + $i$ 到 $t$ 的未来估价函数，$i$ 点编号，$d$ 记录的总路径长度

在过程中，我们只允许每个点最多入队 $K$ 次，当 $t$ 节点第 $K$ 次出队时，对应三元组中的 $d$ 就为所求的第 $K$ 短路

long long astar(void){
    priority_queue<node> q;
    q.push({f[S],S,0});
    while (q.size()){
        auto t=q.top();
        q.pop();
        cnt[t.v]++;
        if (cnt[T]==K)//终点出队k次
            return t.d;
        for (auto iter:he[t.v])
            if (cnt[iter.v]<K)
                q.push({t.d+iter.w+f[iter.v],iter.v,t.d+iter.w});
    }
    return -1;
}

如果需要求严格的第 $K$ 短路，即当路径长度不同时才算为不同的第 $K$ 短路，需要增设一个变量记录上一次的答案

如果这一次得到路径长度与上一次相同，那么就需要令 $K+1$（当前的路径无效）

struct node{
    long long s,v,d;
    bool operator<(const node&x)const{
        return s>x.s;
    }//重载运算符，使优先队列按照s从小到大排列
};

long long mem=-1;

long long astar(void){
    priority_queue<node> q;
    q.push({f[s],s,0});
    while (q.size()){
        auto t=q.top();
        q.pop();
        
        if (t.v==K){
            if (mem==t.d) K++;
            else mem=t.d;
        }
        
        cnt[t.v]++;
        if (cnt[T]==K)
            return t.d
        for (auto iter:he[t.v])//he表示正向图
            if (cnt[iter.v]<K)
                q.push({t.d+iter.w+f[iter.v],iter.v,t.d+iter.w});
    }
    return -1;
}