Алгоритм 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] + w; q.insert({ dist[to], to }); } } } return 1e9; }

int aStar(vector<vector<pair<int, int>>> &graph, int start, int finish) { vector<int> dist(graph.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] + w; 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;
}

Ссылки

• neerc.ifmo.ru/wiki — Алгоритм A*
• Red Blob Games — Introduction to the A* Algorithm
• Red Blob Games — Implementation of A*
• Red Blob Games — Amit’s A* Pages
• Brilliant.org — A* Search
• Princeton COS 226 Assignment — 8 Slider Puzzle