Алгоритм 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<vector<int>> dist(size, vector<int>(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<vector<int>> dist(size, vector<int>(size, 1e9)); vector<vector<int>> distH(size, vector<int>(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; } Ссылки 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