Алгоритм A*

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску

Общая схема перехода от Дейкстры к A*

  • Дейкстра ищет кратчайшие пути от заданной начальной вершины до всех остальных. A* ищет кратчайший путь от заданной начальной вершины до заданной конечной.
  • Понадобится эвристическая функция h(v), делающая предположение о том, сколько ещё нужно пройти от вершины v до конечной вершины. Функция h() никогда не должна переоценивать это расстояние (но может недооценивать).
  • В Дейкстре мы использовали массив dist[]: dist[v] — кратчайшее расстояние от стартовой вершины до вершины v. Теперь мы дополнительно используем массив distH[]: distH[v] — это оценённая длина пути из стартовой вершины в конечную через вершину v. Очевидно, distH[v] всегда равно dist[v] + h(v).
  • Будем сравнивать непосещённые вершины и определять наиболее перспективного соседа не по dist[], а по distH[].
  • Заметим, что если h() всегда возвращает 0, то A* превращается в алгоритм Дейкстры.
int dijkstra(vector<vector<pair<int, int>>> &graph, int start, int finish) {
    vector<int> dist(graph.size(), 1e9);
    set<pair<int, int>> q;


    dist[start] = 0;
    q.insert({ dist[start], start });


    while (!q.empty()) {
        int v = q.begin()->second;
        q.erase(q.begin());

        if (v == finish)
            return dist[v];

        for (auto &[to, w] : graph[v]) {
            if (dist[to] > dist[v] + w) {
                q.erase({ dist[to], to });
                dist[to] = dist[v] + 1;
                q.insert({ dist[to], to });
            }
        }

    }

    return 1e9;
}

int aStar(vector<vector<pair<int, int>>> &graph, int start, int finish) {
    vector<int> dist(size, 1e9);
    vector<int> distH(graph.size(), 1e9);
    set<pair<int, int>> q;

    dist[start] = 0;
    distH[start] = dist[start] + h(start);
    q.insert({ distH[start], start });

    while (!q.empty()) {
        int v = q.begin()->second;
        q.erase(q.begin());

        if (v == finish)
            return dist[v];

        for (auto &[to, w] : graph[v]) {
            if (dist[to] > dist[v] + w) {
                q.erase({ distH[to], to });
                dist[to] = dist[v] + 1;
                distH[to] = dist[to] + h(to);
                q.insert({ distH[to], to });
            }
        }
    }

    return 1e9;
}

15 Puzzle

Board 

const int SIDE = 4;
const int SIZE = SIDE * SIDE;

struct Board {
    vector<int> a;
    int zy, zx, manhattanHeuristic, unsolvable;

    void recalculate() {
        manhattanHeuristic = 0;
        int inv = 0;
        for (int y = 0; y < SIDE; y++) {
            for (int x = 0; x < SIDE; x++) {
                if (a[y * SIDE + x]) {
                    for (int d = 0; d < y * SIDE + x; d++)
                        inv += a[d] && a[d] > a[y * SIDE + x];
                } else {
                    zy = y;
                    zx = x;
                }
                int tile = (a[y * SIDE + x] + SIZE - 1) % SIZE;
                int ty = tile / SIDE, tx = tile % SIDE;
                manhattanHeuristic += abs(y - ty) + abs(x - tx);
            }
        }
        unsolvable = (inv + zy) % 2 == 0;
    }

    bool operator < (const Board &that) const {
        if (manhattanHeuristic != that.manhattanHeuristic)
            return manhattanHeuristic < that.manhattanHeuristic;
        return a < that.a;
    }

    bool canMove(int dy, int dx) {
        int ty = zy + dy, tx = zx + dx;
        return 0 <= ty && ty < SIDE && 0 <= tx && tx < SIDE;
    }

    Board move(int dy, int dx) {
        Board res = *this;
        int ty = zy + dy, tx = zx + dx;
        swap(res.a[zy * SIDE + zx], res.a[ty * SIDE + tx]);
        res.recalculate();
        return res;
    }
};

istream &operator >> (istream &in, Board &board) {
    board.a.resize(SIZE);
    for (int i = 0; i < SIZE; i++)
        in >> board.a[i];
    board.recalculate();
    return in;
}

A* 

string aStar(Board &board) {
    if (board.unsolvable)
        return "NO SOLUTION";

    map<Board, int> dist, distH, pred;
    set<pair<int, Board>> q;

    dist[board] = 0;
    distH[board] = dist[board] + board.manhattanHeuristic;
    pred[board] = -1;
    q.insert({ distH[board], board });

    static vector<int> dy = { -1, 0, 1, 0 };
    static vector<int> dx = { 0, 1, 0, -1 };
    static string dc = "URDL";

    while (!q.empty()) {
        auto v = *q.begin()->second;
        q.erase(q.begin());

        if (!v.manhattanHeuristic)
            break;

        for (int d = 0; d < 4; d++) {
            if (!v.canMove(dy[d], dx[d]))
                continue;

            Board to = v.move(dy[d], dx[d]);
            
            if (auto it = dist.find(to); it == dist.end() || it->second > dist[v] + 1) {
                q.erase({ distH[to], to });
                dist[to] = dist[v] + 1;
                distH[to] = dist[to] + to.manhattanHeuristic;
                pred[to] = d;
                q.insert({ distH[to], to });
            }
        }
    }

    for (int i = 0; i < SIZE; i++)
        board.a[i] = (i + 1) % SIZE;
    board.recalculate();

    string path;
    while (1) {
        int d = pred[board];
        if (d == -1)
            break;
        path.push_back(dc[d]);
        board = board.move(dy[(d + 2) % 4], dx[(d + 2) % 4]);
    }
    reverse(path.begin(), path.end());
    return path;
}

void solve() {
    Board board;
    cin >> board;
    cout << aStar(board) << "\n";
}

IDA* 

struct Solver {
    map<Board, int> visited, pred;

    static inline vector<int> dy = { -1, 0, 1, 0 };
    static inline vector<int> dx = { 0, 1, 0, -1 };
    static inline string dc = "URDL";

    bool dfs(Board &v, int depth, int limit, int &nextLimit) {
        if (depth + v.manhattanHeuristic > limit) {
            nextLimit = min(nextLimit, depth + v.manhattanHeuristic);
            return 0;
        }

        if (!v.manhattanHeuristic)
            return 1;

        if (auto it = visited.find(v); it != visited.end() && it->second <= depth)
            return 0;
        visited[v] = depth;

        for (int d = 0; d < 4; d++) {
            if (!v.canMove(dy[d], dx[d]))
                continue;

            Board to = v.move(dy[d], dx[d]);

            if (dfs(to, depth + 1, limit, nextLimit)) {
                pred[to] = d;
                return 1;
            }
        }

        return 0;
    }

    string idaStar(Board &board) {
        if (board.unsolvable)
            return "NO SOLUTION";

        int limit = 0;
        while (1) {
            int nextLimit = 1e9;
            visited.clear();
            pred = { { board, -1 } };
   
            if (dfs(board, 0, limit, nextLimit))
                break;

            limit = nextLimit;
        }

        for (int i = 0; i < SIZE; i++)
            board.a[i] = (i + 1) % SIZE;
        board.recalculate();

        string path;
        while (1) {
            int d = pred[board];
            if (d == -1)
                break;
            path.push_back(dc[d]);
            board = board.move(dy[(d + 2) % 4], dx[(d + 2) % 4]);
        }
        reverse(path.begin(), path.end());
        return path;
    }
} solver;

void solve() {
    Board board;
    cin >> board;
    cout << solver.idaStar(board) << "\n";
}

Knight Path

int aStar(int size, int sy, int sx, int fy, int fx) {
    vector<vector<int>> dist(size, vector<int>(size, 1e9));
    vector<vector<int>> distH(size, vector<int>(size, 1e9));
    set<pair<int, pair<int, int>>> q;

    dist[sy][sx] = 0;
    distH[sy][sx] = dist[sy][sx] + (abs(sy - fy) + abs(sx - fx)) / 3;
    q.insert({ distH[sy][sx], { sy, sx } });

    while (!q.empty()) {
        auto [y, x] = q.begin()->second;
        q.erase(q.begin());

        if (y == fy && x == fx)
            return dist[y][x];

        static int dy[] = { -2, -2, -1, 1, 2, 2, 1, -1 };
        static int dx[] = { -1, 1, 2, 2, 1, -1, -2, -2 };

        for (int d = 0; d < 8; d++) {
            int ty = y + dy[d], tx = x + dx[d];
            if (0 <= ty && ty < size && 0 <= tx && tx < size && dist[ty][tx] > dist[y][x] + 1) {
                q.erase({ distH[ty][tx], { ty, tx } });
                dist[ty][tx] = dist[y][x] + 1;
                distH[ty][tx] = dist[ty][tx] + (abs(ty - fy) + abs(tx - fx)) / 3;
                q.insert({ distH[ty][tx], { ty, tx } });
            }
        }
    }

    return 1e9;
}

Ссылки
Источник — https://acm.khpnets.info/w39/index.php?title=Алгоритм_A*&oldid=2745