Алгоритм A*: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 1: Строка 1:
== 15 Puzzle ==
{|
|colspan=2|
'''Board'''
  const int SIDE = 4;
  const int SIDE = 4;
  const int SIZE = SIDE * SIDE;
  const int SIZE = SIDE * SIDE;
Строка 53: Строка 58:
     return in;
     return in;
  }
  }
|-
|width=50%|
'''A*'''
  string aStar(Board &board) {
  string aStar(Board &board) {
     if (board.unsolvable)
     if (board.unsolvable)
Строка 73: Строка 80:
         q.erase(q.begin());
         q.erase(q.begin());
   
   
         if (!v.manhattanHeuristic) {
         if (!v.manhattanHeuristic)
            board = v;
             break;
             break;
        }
   
   
         for (int d = 0; d < 4; d++) {
         for (int d = 0; d < 4; d++) {
Строка 84: Строка 89:
             Board to = v.move(dy[d], dx[d]);
             Board to = v.move(dy[d], dx[d]);
              
              
             if (auto it = dist.find(to); it == dist.end() || it->second > vDist + to.manhattanHeuristic) {
             if (auto it = dist.find(to); it == dist.end() ||
                it->second > vDist + to.manhattanHeuristic) {
                 q.erase({ dist[to], to });
                 q.erase({ dist[to], to });
                 dist[to] = vDist + to.manhattanHeuristic;
                 dist[to] = vDist + to.manhattanHeuristic;
Строка 92: Строка 98:
         }
         }
     }
     }
    for (int i = 0; i < SIZE; i++)
        board.a[i] = (i + 1) % SIZE;
    board.recalculate();
   
   
     string path;
     string path;
Строка 110: Строка 120:
     cout << aStar(board) << "\n";
     cout << aStar(board) << "\n";
  }
  }
|width=50%|
'''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";
}
|}


== Ссылки ==
== Ссылки ==

Версия от 05:31, 30 июня 2021

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";
}


Ссылки

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