Конспект: порядок вычисления, память и ДП по маскам

Понятия

Порядок вычисления - топологический порядок на графе зависимостей состояний; читается из индексов перехода.

Свёртка таблицы - хранить только те строки, на которые ссылается переход.

Маска - подмножество, закодированное числом: бит i равен единице, если элемент взят.

Включение-исключение - Σ по S (−1)^|S| · N(S); гамильтоновы циклы как замкнутые обходы длины n без пропущенных вершин - O(2^n · n³) времени, O(n) памяти.

Оптимизации динамики: монотонное лучшее i - разделяй и властвуй; корень между корнями соседей - Кнут; цена-прямая - выпуклая оболочка прямых. Условие проверяют наивной версией на маленьких входах.

Что унести

ПОРЯДОК ЧИТАЕТСЯ ИЗ ПЕРЕХОДА
dp[i] = f(dp[i−1], dp[i−2])             → i по возрастанию
dp[i][j] = f(dp[i−1][j], dp[i][j−1])    → строки сверху вниз, в строке слева направо
dp[i][c] = f(dp[i−1][...])              → строки по порядку, внутри любой
ссылка на ТУ ЖЕ строку                  → порядок внутри строки КРИТИЧЕН
dp[маска][v] = f(dp[меньшая маска][u])  → маски по возрастанию числа

мемоизации порядок не нужен - он получается сам

Плата за свёртку одна: ответ восстановить нельзя, остаётся только число - обратный проход читает клетки всех строк. Варианты: полная таблица; таблица СТРЕЛОК (по два бита на клетку вместо числа); приём Хиршберга - разрезать первую строку посередине, найти точку разреза второй по сумме двух однострочных расчётов, рекурсивно решить половины: Θ(n·m) времени с удвоенной константой и Θ(n+m) памяти.

СВЁРНУТЫЙ РЮКЗАК - НАПРАВЛЕНИЕ ОБХОДА
назад (от C к весу)  → предмет берётся не больше раза          ВЕРНО
вперёд               → dp[c−вес] уже содержит текущий предмет  РЮКЗАК С ПОВТОРЕНИЯМИ

замер: предметы (10,60), (20,100), (30,120), C = 50
    назад 220   |   вперёд 300   (предмет весом 10 взят пять раз)
НО на двенадцати предметах весом 28-35 при C = 60 оба обхода дают 147:
повтор ВОЗМОЖЕН (28 + 28 = 56), но не выгоден - 130 против 147
⇒ тесты обязаны содержать предмет, которым ВЫГОДНО забить рюкзак

У Флойда-Уоршелла цикл по k обязан быть внешним: k нумерует слои «какие вершины разрешены как промежуточные» - это сэкономленный по памяти параметр состояния. При внутреннем k теряются пути через две пересадки.

ДП ПО МАСКАМ
состояние содержит «какое подмножество использовано», состояний 2^n
обход - по возрастанию числа маски
операции: взят ли i   mask // 2**i % 2    (без побитовых - арифметикой)
          добавить i   mask + 2**i        (только если не взят)

коммивояжёр: dp[маска][v], цена Θ(2^n·n²) против Θ((n−1)!) у перебора
   n=10:  маршрутов 3.6·10⁵   против 1.0·10⁵     в 3.5 раза
   n=15:            8.7·10¹⁰  против 7.4·10⁶     в 12 тысяч раз
   n=20:            1.2·10¹⁷  против 4.2·10⁸     в 290 миллионов раз

Замер на движке (один граф, ответы совпадают): перебор перестановок - 4623 шага при n = 5, 245 158 при n = 7, на n = 8 не уложился; ДП по маскам - 1656, 10 706, 26 465, 64 330 и 153 906 шагов при n от 5 до 10. Граница применимости: n до 20-22 (при n = 20 это 2·10⁷ клеток, то есть 160 МБ; при n = 25 - больше шести гигабайт).

В задачах на разбиение перебирают партнёра для ЗАФИКСИРОВАННОГО младшего свободного элемента: это убирает множитель n и дубли. Признак задачи на маски: «каждый ровно один раз» плюс подозрительно маленькое n.

Тихие ошибки: обход вперёд у свёрнутого рюкзака; циклы Флойда в другом порядке; обход масок по убыванию; dp[mask][v] при v, не входящем в маску (половина таблицы - мусор); свёртка до проверки правильности; попытка восстановить ответ по свёрнутой таблице; маски при n около тридцати.

Куда это ведёт

Следующий урок - конспект раздела: порядок действий «от рекурсии к таблице» целиком, от двух условий применимости до свёртки по памяти. А дальше раздел про перебор и его сокращение: там разбираются задачи, где ни жадность, ни динамика не помогают, и приходится перебирать - но умно, с отсечениями.