A-Star Algorithm: Shortest Path Search Algorithm

双语页面

本页面支持简体中文，点我以跳转至中文站界面。

Thus spoke JustPureH2O, the newbie Crosstalker

(Scene)

Throw away your Dijkstra, let's talk about A*!

I know that one. A* is adjugate to matrix A, a linear algebra concept which means...

Stop your nonsense talking! Why mention linear algebra?

Enumerate its cofactor and then...

Nonono, stop! The A* algorithm here is used to find a shortest path in graphs. Navigators use this algorithm as its core. A* is one of the search algorithms, and the heuristic version is called IDA*...

LOL, I can do this with just simple BFS.

But different. A* is running on test data approximately . BFS will get a TLE. So, did you listen to me carefully? What is A*?

It's adjugate to matrix A.

Damn!

(Scene)

Brief Introduction to A*

As a careful listener, you will know that A* algorithm is categorized under heuristic search algorithms. But why is it named A*? I think you should better ask the one who named it. I don't know the reason.

A* algorithm is like capitalists. For graphs which contains sea of nodes, we need to find the shortest path between given starting and ending node. BFS resembles a perfectionist who failed to deal with distinct weights (0/1 shortest path), and it must scan all the edges to find the shortest one. Dijkstra is better at weights, but failed to manage negative weights (Bellman-Ford should fix this), and it is close to BFS that it also needs to scan large amount of nodes. A* is much more clever, as it uses a evaluation function to decide whether the current solution will pass this node ahead. Given that it has reduced huge inefficient traversals, the elapse will much shorter.

To implement this, we need to give a small change to Dijkstra optimized with heap:

Change distance-first priority queue to evaluated-first.

Others remain almost the same. Enumerating edges stretched out and then pushing them into the queue. When the destination node is popped out, return the shortest path.

How to calculate the value of each node? First get the true distance from local node to departure node as . Second, estimate the remaining distance to destination as . Sum them as our evaluation . Noted that Dijkstra is a special case when because it doesn't take evaluation step.

Notes

Priority queue: Before you push a new node, the keyword used to sort should be . When the departure point is about to be handle, because its true distance is actually .
Evaluation: varies in different cases. In Eight Digits Problem, points to the Manhattan Distance from current state to given state. As for USACO08MAR Cow Jogging G, it refers to the shortest distance to destination. Thus you need to reset to fit requirements.

Instances

Eight Digits Problem

Portal: here

Difficulty：1600-1900

Source：Summer Camp Fujian

On a chessboard lies 8 digits from 1 to 8, along with a spacebar marked as . Digits around the spacebar can move into it. You need to figure out the least-step solution which transforms the initial state given in test datas to the destination state , and output the step count.

Try solving it with BFS. We must list all the states we could make. When the destination is firstly reached, return the result.

Then have a look about A* algorithm, we need to find out a way to evaluate the state. Why not calculating the difference between states so that we can quantify the distance. For detail, we can sum the position difference like current position minus target position.

Final code:

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, string> STATE;
unordered_map<string, int> dist;
priority_queue<STATE, vector<STATE>, greater<>> q;
string st, ed = "123804765";

int f(const string &now) {
    int res = 0;
    for (int i = 0; i < 9; i++) {
        if (now[i] == '0') continue;
        switch (now[i] - '0') {
            case 1:
            case 2:
            case 3:
                res += abs(i / 3) + abs(i % 3 - (now[i] - '1') % 3);
                break;
            case 4:
                res += abs(i / 3 - 1) + abs(i % 3 - 2);
                break;
            case 5:
                res += abs(i / 3 - 2) + abs(i % 3 - 2);
                break;
            case 6:
                res += abs(i / 3 - 2) + abs(i % 3 - 1);
                break;
            case 7:
                res += abs(i / 3 - 2) + abs(i % 3);
                break;
            case 8:
                res += abs(i / 3 - 1) + abs(i % 3);
                break;
        }
    }
    return res;
}

int bfs() {
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    q.push((STATE) {f(st), st});
    dist[st] = 0;
    while (!q.empty()) {
        STATE s = q.top();
        q.pop();
        if (s.second == ed) return dist[s.second];
        int idxx = 0, idxy = 0;
        for (int i = 0; i < 9; i++) {
            if (s.second[i] == '0') {
                idxx = i / 3, idxy = i % 3;
                break;
            }
        }
        string src = s.second;
        string tmp = s.second;
        for (int i = 0; i < 4; i++) {
            int nx = idxx + dx[i], ny = idxy + dy[i];
            if (nx < 0 || nx > 2 || ny < 0 || ny > 2) continue;
            tmp = src;
            swap(tmp[idxx * 3 + idxy], tmp[nx * 3 + ny]);
            if (!dist.count(tmp) || dist[tmp] > dist[src] + 1) {
                dist[tmp] = dist[src] + 1;
                q.push((STATE) {f(tmp) + dist[tmp], tmp});
            }
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> st;
    cout << bfs() << endl;

    return 0;
}

[USACO08MAR] Cow Jogging G

Portal: here

Difficulty: 2000-2300

Source：USACO 2008

Simplified description: You are given a graph, and output the length of the first, second, third to the k-th shortest path from node to node .

Here is a nature concerning this algorithm:

The total length of the path is the k-th shortest when the destination has popped out from the queue for exactly times

Given the rule, we can run the program in a loop in bound of , calculating the length from the shortest to the k-th shortest. Exceptionally, just output when the total combinations of paths is fewer than . We can record the shortest path by running shortest path algorithm on the reversed graph.

Final code:

#include <bits/stdc++.h>

#define N 10010
using namespace std;

typedef long long ll;
typedef pair<ll, int> Point;
typedef pair<ll, Point> Star;

struct Edge {
    int ne, to;
    ll w;
} edges[N << 2];

int h[N], rh[N];
bool st[N];

priority_queue<Point, vector<Point>, greater<>> q;
priority_queue<Star, vector<Star>, greater<>> heap;
int astar_cnt = 0;
ll dist[N];
int idx = 0;
int n, m;

void add(int he[], int u, int v, ll w) {
    idx++;
    edges[idx].to = v;
    edges[idx].ne = he[u];
    edges[idx].w = w;
    he[u] = idx;
}

void dijkstra() {
    q.push((Point) {0, 1});
    dist[1] = 0;
    while (!q.empty()) {
        Point p = q.top();
        q.pop();
        int id = p.second;
        if (st[id]) continue;
        st[id] = true;
        for (int i = rh[id]; ~i; i = edges[i].ne) {
            int j = edges[i].to;
            if (dist[j] > dist[id] + edges[i].w) {
                dist[j] = dist[id] + edges[i].w;
                q.push((Point) {dist[j], j});
            }
        }
    }
}

ll a_star(int k) {
    heap.push((Star) {dist[n], (Point) {0, n}});
    while (!heap.empty()) {
        Star p = heap.top();
        heap.pop();
        if (p.second.second == 1) astar_cnt++;
        if (astar_cnt == k) return p.second.first;
        for (int i = h[p.second.second]; ~i; i = edges[i].ne) {
            int j = edges[i].to;
            heap.push((Star) {dist[j] + edges[i].w + p.second.first, (Point) {p.second.first + edges[i].w, j}});
        }
    }
    return -1;
}

void restore() {
    astar_cnt = 0;
    heap = priority_queue<Star, vector<Star>, greater<>>();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    memset(h, -1, sizeof h);
    memset(rh, -1, sizeof rh);
    memset(dist, 0x3f, sizeof dist);

    int k;
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++) {
        int x, y;
        ll d;
        cin >> x >> y >> d;
        add(h, x, y, d);
        add(rh, y, x, d);
    }

    dijkstra();

    bool flag = false;
    for (int i = 1; i <= k; i++) {
        if (flag) cout << -1 << endl;
        else {
            restore();
            ll res = a_star(i);
            cout << res << endl;
            flag = (res == -1);
        }
    }

    return 0;
}