估价函数搜索

yzy4090 · 2023-07-20 10:22:41 · 个人记录

估价函数是一种预估未来代价的函数，只求近似。它可以用在优先队列广度优先搜索和迭代加深的深度优先搜索当中，可以显著提高速度（前提是估价函数设计得好）。
估价函数必须不大于实际的未来代价。

k 短路问题

（注：k 短路可以卡 A^* 算法，所以真要学 k 短路还得学正解。）
在优先队列广度优先搜索中，当一个节点第 k 次从优先队列中取出时，此时的距离就是从起点到本节点的第 k 短路。
考虑估价函数优化：将估价函数 f 定为从一个节点到终点的最短路长度，这样就有 f(x)\le g(x)。代码（有负权边需用队列优化 Bellman-Ford 算法）：

typedef pair<ll,int> P;
typedef tuple<ll,ll,int> R;
void dijkstra(int tmnal){
    priority_queue<P,vector<P>,greater<P> >p;p.push(P{0ll,tmnal});
    memset(dis,0x3f,sizeof dis);dis[tmnal]=0ll;
    while(!p.empty()){P now=p.top();p.pop();
        if(dis[now.second]<now.first)continue;
        for(int i=0;i<(int)cev[now.second].size();i++){
            P nxt=cev[now.second][i];
            if(dis[nxt.second]>dis[now.second]+nxt.first){
                dis[nxt.second]=dis[now.second]+nxt.first;
                p.push(P{dis[nxt.second],nxt.second});
            }
        }
    }
    return;
}
int kk;
void astar(int start){
    priority_queue<R,vector<R>,greater<R> >q;q.push(R{0ll,0ll,start});
    while(!q.empty()){R now=q.top();q.pop();cnt[g(now,2)]++;
        if(g(now,2)==tmnal){
            printf("%lld\n",g(now,1));
            if(!(--kk))return;
        }
        for(int i=0;i<(int)vec[g(now,2)].size();i++){
            P nxt=vec[g(now,2)][i];
            if(cnt[nxt.second]<k)
                q.push(R{g(now,1)+nxt.first+dis[nxt.second],g(now,1)+nxt.first,nxt.second});
        }
    }
    return;
}

其它题目：
P2324 [SCOI2005] 骑士精神
P1379 八数码难题