A* 解八数码

Luogu P1379 八数码难题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> pq;
unordered_map<string, int> d;
int Astar() {
    d[bg] = 0;
    pq.push(make_pair(0 + Manh(bg), bg));
    while (!pq.empty()) {
        string sta = pq.top().second;
        pq.pop();
        if (sta == ed) {
            return d[sta];
        }
        Trans(sta); // Trans(string sta)函数将sta可转移到的状态存到deal数组里
        int D = d[sta] + 1;
        for (int i = 1; i <= cntdeal; ++i) {
            if (!d.count(deal[i]) || d[deal[i]] > D) {
                d[deal[i]] = D;
                pq.push(make_pair(D + Manh(deal[i]), deal[i]));
                // Manh(string sta)函数求sta到end的总曼哈顿长度，即估价函数
            }
        }
    }
    return -1;
}

A* 解k短路

Acwing 178. 第K短路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int Astar(int s, int t, int kth) {
    if (dis[s] == INF) return -1;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    int times = 0;
    pq.push(make_pair(0 + dis[s], s));
    while (!pq.empty()) {
        int cur = pq.top().second, dist = pq.top().first - dis[cur]; pq.pop();
        if (cur == t) {
            if (++times == kth) {
                return dist;
            }
        }
        for (int i = head[cur]; i; i = nex[i]) {
            pq.push(make_pair(dist + wei[i] + dis[to[i]], to[i]));
        }
    }
    return -1;
}

signed main() {
    // ...
    Dijkstra(t); // 反向边上跑 Dij
    printf("%d\n", Astar(s, t, kth)); // 正向边上跑 A*
}