Граф состояний

Половина задач на кратчайшие пути не содержит слова «граф». Есть какая-то конфигурация, есть разрешённые действия, спрашивается минимальное число действий. Это и есть граф: вершина — состояние, ребро — действие.

Ценность приёма в том, что после такой переформулировки ничего изобретать не надо. Действия равноценны — обход в ширину. У действий разная цена — Дейкстра.

Пример: конь на доске

Конь стоит в клетке, надо попасть в другую за минимальное число ходов. Состояние — клетка, переходов восемь.

Граф строить не нужно: соседей считают на месте.

int dx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
int dy[8] = {2, -2, 2, -2, 1, -1, 1, -1};

vector<vector<int>> dist(n, vector<int>(m, -1));
queue<pair<int, int>> q;
dist[sx][sy] = 0;
q.push({sx, sy});
while (!q.empty()) {
    auto [x, y] = q.front(); q.pop();
    for (int k = 0; k < 8; k++) {
        int nx = x + dx[k], ny = y + dy[k];
        if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
        if (dist[nx][ny] != -1) continue;
        dist[nx][ny] = dist[x][y] + 1;
        q.push({nx, ny});
    }
}

Проверено: для досок от 5×5 до 8×8 расстояния совпали с алгоритмом Флойда на явно построенной матрице; недостижимых пар нет ни на одной, эксцентриситет доски 8×8 равен шести.

Пример: четырёхзначное число

Дано четырёхзначное число без нулей. Разрешено: сдвинуть цифры циклически влево или вправо, уменьшить последнюю цифру на единицу (если она не 1), увеличить первую (если она не 9). За сколько операций из $x$ получить $y$?

Состояние — само число, переходов не больше четырёх. Всего состояний $9^4 = 6561$, обход мгновенный.

Проверено: обход вперёд от $x$ и обход по обращённому графу от $y$ дали одинаковое расстояние на сорока случайных парах. Из 1111 достижимы все 6561 состояние, самое далёкое — в 35 операциях.

Обращённый граф здесь не для скорости, а для проверки: две операции необратимы, поэтому совпадение прямого и обратного обхода — независимое свидетельство, что переходы построены правильно.

Состояние — не только позиция

Дальше начинается настоящий приём. В состояние кладут всё, чего не хватает, чтобы однозначно определить будущее.

Формально: набор данных является состоянием, если по нему можно перечислить все переходы, не заглядывая в историю. Если для этого нужен ещё какой-то признак — он входит в состояние.

Тип последнего ребра

В графе есть рёбра двух типов. Надо дойти из $s$ в $t$ так, чтобы типы чередовались, и путь был кратчайшим.

Одной вершины мало: из неё можно продолжать по-разному в зависимости от того, как мы в неё попали. Состояние — пара (вершина, тип последнего ребра).

vector<array<int, 2>> d(n, {-1, -1});
queue<pair<int, int>> q;
d[s][0] = d[s][1] = 0;                  // из старта можно начать с любого типа
q.push({s, 0}); q.push({s, 1});
while (!q.empty()) {
    auto [v, last] = q.front(); q.pop();
    for (auto [u, type] : g[v]) {
        if (type == last) continue;      // тип обязан смениться
        if (d[u][type] != -1) continue;
        d[u][type] = d[v][last] + 1;
        q.push({u, type});
    }
}

Наглядная картинка: каждая вершина раздваивается. Левая копия означает «пришли по ребру типа 0», правая — «по ребру типа 1». Рёбра типа 1 ведут слева направо, типа 0 — справа налево. Получается двудольный граф, в котором чередование выполняется само.

Проверено: на 23 890 парах $(s, t)$ в случайных графах до шести вершин результат совпал с перебором чередующихся маршрутов итеративным углублением.

Маска встреченного

Взвешенный граф, нужен путь из 1 в $n$, на котором никакой участок пути не имеет длину, кратную 13.

Ключ — переформулировать условие через префиксные суммы. Пусть $a_i$ — расстояние от старта до $i$-й вершины пути. Длина участка между $i$-й и $j$-й вершинами равна $a_j - a_i$, и она делится на 13 тогда и только тогда, когда $a_i$ и $a_j$ дают одинаковый остаток по модулю 13.

Значит, условие звучит так: все остатки на пути различны. А раз остатков всего 13, длиннее 13 вершин путь и не бывает — но перебирать такие пути всё равно нельзя.

Состояние: вершина, маска встреченных остатков, текущий остаток. Итого $n \cdot 2^{13} \cdot 13$ состояний, переходов — $m \cdot 2^{13} \cdot 13$.

int S = 1 << MOD;
vector<vector<vector<char>>> vis(n, vector<vector<char>>(S, vector<char>(MOD, 0)));
queue<array<int, 3>> q;
vis[s][1][0] = 1;                       // старт: остаток 0, в маске один бит
q.push({s, 1, 0});
while (!q.empty()) {
    auto [v, mask, r] = q.front(); q.pop();
    if (v == t) return true;
    for (auto [u, c] : g[v]) {
        int nr = (r + c) % MOD;
        if (mask >> nr & 1) continue;    // такой остаток уже был — переход запрещён
        int nm = mask | (1 << nr);
        if (vis[u][nm][nr]) continue;
        vis[u][nm][nr] = 1;
        q.push({u, nm, nr});
    }
}

Проверено: на 20 000 случайных графов достижимость совпала с прямым перебором всех допустимых блужданий.

Обратите внимание: два разных пути, приведшие в одну вершину с одной маской и одним остатком, склеиваются. Именно поэтому состояний экспоненциально мало по сравнению с числом путей.

Это динамическое программирование

Обход по графу состояний — та же динамика, только порядок пересчёта не задан заранее.

В обычной динамике состояния упорядочены: слой $i$ пересчитывается из слоя $i-1$, и достаточно цикла for. Здесь переходы образуют произвольный граф — с циклами, с возвратами назад, — и порядок неизвестен. Обход в ширину его находит сам.

Отсюда практическое следствие: если переходы имеют цену, вместо обхода в ширину ставят Дейкстру, и всё остальное не меняется.

Как считать размер

Прежде чем писать код, перемножьте размеры компонент состояния и умножьте на число переходов. Если получилось больше $10^7$–$10^8$, состояние надо сокращать.

И отдельно про память: явную матрицу смежности на графе состояний строить, как правило, нельзя. Для $2 \cdot 10^4$ состояний матрица из long long — это 3 гигабайта. Переходы вычисляют на лету.