Алгоритм A*
Перейти к навигации
Перейти к поиску
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";
set<pair<int, Board>> q;
map<Board, int> dist, pred;
q.insert({ board.manhattanHeuristic, board });
dist[board] = board.manhattanHeuristic;
pred[board] = -1;
static vector<int> dy = { -1, 0, 1, 0 };
static vector<int> dx = { 0, 1, 0, -1 };
static string dc = "URDL";
while (!q.empty()) {
auto [vDist, v] = *q.begin();
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 > vDist + to.manhattanHeuristic) {
q.erase({ dist[to], to });
dist[to] = vDist + to.manhattanHeuristic;
pred[to] = d;
q.insert({ dist[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";
}
|