Алгоритм 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;
}