ДП по маскам: состояние-подмножество и n до двадцати

Если ты умеешь закодировать подмножество числом, помнишь оценку 2^n·n² и границу применимости, листай до «Теперь сам».

Как думаешь, когда подмножество приходится держать в состоянии

Во второй главе мы видели задачу, где подструктуры НЕТ именно из-за общего ресурса: самый длинный простой путь, где нельзя посещать вершину дважды. Тогда же было сказано, что ресурс можно внести в состояние - и что ценой этого становится 2^n.

Прежде чем читать дальше: как вообще уместить «множество посещённых вершин» в индекс массива?

На что это похоже

Отметки в журнале регистрации. Вместо списка фамилий - строка галочек по числу участников: пришёл или нет. Строка из двадцати галочек - это одно число, и по нему мгновенно видно всё состояние зала. Маска и есть такой журнал: компактный, целочисленный и годный в качестве индекса.

Механизм: маска, переход, порядок

КОДИРОВАНИЕ ПОДМНОЖЕСТВА ЧИСЛОМ
элемент i взят ⇔ i-й бит числа равен единице

маска 0  = 00000 = {}            маска 5  = 00101 = {0, 2}
маска 1  = 00001 = {0}           маска 31 = 11111 = {0,1,2,3,4}

всего подмножеств n элементов: 2^n

ОПЕРАЦИИ НАД МАСКОЙ (битовые - и их арифметические двойники)

взят ли элемент i:      mask & (1 << i)      или   mask // 2**i % 2
добавить элемент i:     mask | (1 << i)      или   mask + 2**i   (если не взят)
полное множество:       (1 << n) − 1         или   2**n − 1

ЗАДАЧА КОММИВОЯЖЁРА (TSP) - эталонный пример

состояние: (маска посещённых городов, город, в котором стоим)
    dp[mask][v] = минимальная длина пути, прошедшего ровно города из mask
                  и закончившегося в v

переход: из (mask, v) идём в не посещённый город u
    dp[mask + 2**u][u] = min(..., dp[mask][v] + d[v][u])

база:  dp[1][0] = 0 - стоим в городе 0, посещён только он
ответ: min по v от dp[полная маска][v] + d[v][0]

состояний 2^n·n, переход перебирает n городов ⇒ Θ(2^n · n²)

ПОРЯДОК: маски по ВОЗРАСТАНИЮ числа
переход добавляет элемент, то есть всегда увеличивает число маски -
значит к моменту счёта маски все меньшие уже готовы

Правило

Если в состоянии нужно «какое подмножество использовано», его кодируют числом: бит i показывает, взят ли элемент i. Состояний 2^n, обходят их по ВОЗРАСТАНИЮ числа - переход добавляет элемент и только увеличивает маску. Коммивояжёр: состояние «(маска посещённых, текущий город)», цена Θ(2^n·n²) вместо Θ(n!) у перебора перестановок. Граница применимости жёсткая: при n = 20 это 4·10⁸ операций и 2·10⁷ клеток - на пределе, при n = 25 уже 2·10¹⁰ и гигабайты. Поэтому ДП по маскам - инструмент для n до двадцати с небольшим, и ровно столько же, сколько стоит сама маска, стоит помнить про её арифметические двойники: не во всякой среде есть побитовые операции.

Разбор: коммивояжёр по маскам против перебора

Задача: обойти все n городов, вернуться в начальный, суммарную длину минимизировать.

ПЕРЕБОР ПЕРЕСТАНОВОК     (n−1)! маршрутов
ДП ПО МАСКАМ             2^n·n состояний, переход n

ЗАМЕР НА ДВИЖКЕ КУРСА (один и тот же граф, ответы совпадают)

   n     перебор перестановок      ДП по маскам
   5          4 623 шага              1 656 шагов
   6         31 375                  ...
   7        245 158                  10 706
   8     не уложился                 26 465
   9     не уложился                 64 330
  10     не уложился                153 906

Перебор умирает между 7 и 8 городами, маски доходят до десяти - и это предел уже самого движка (300 тысяч шагов), а не метода. На настоящей машине маски считают до 20-22 городов.

Разберём, почему при таком состоянии подструктура ПОЯВЛЯЕТСЯ. Во второй главе её не было: оптимальный путь q→r нельзя было приклеить к r→t, потому что они делили вершины. Теперь множество использованных вершин стоит В СОСТОЯНИИ - и подзадачи «пройти ровно эти города и оказаться в v» между собой независимы. Общий ресурс перестал быть общим: он стал параметром.

цена этого фокуса видна прямо в формуле
было:  состояний n (только текущая вершина) - но подструктуры нет
стало: состояний 2^n·n - подструктура есть, зато экспонента

ПОЧЕМУ ЭКСПОНЕНТА ВСЁ-ТАКИ ЛУЧШЕ ФАКТОРИАЛА
(маршрутов (n−1)!, потому что начальный город фиксирован)

   n      маршрутов (n−1)!         2^n·n²          выигрыш
  10      362 880                  102 400         в 3.5 раза
  15      8.7·10¹⁰                 7 372 800       в 12 тысяч раз
  20      1.2·10¹⁷                 4.2·10⁸         в 290 миллионов раз
  25      6.2·10²³                 2.1·10¹⁰        в 3·10¹³ раз, но столько
                                                   не считается ни тем, ни этим

Разбор: другие задачи с маской в состоянии

РАЗБИЕНИЕ НА ПАРЫ (идеальное паросочетание минимального веса)
    состояние: маска уже разобранных элементов
    переход: взять младший незанятый элемент и перебрать ему партнёра
    цена Θ(2^n · n) - младший элемент фиксирован, поэтому не n²

ПОКРЫТИЕ МНОЖЕСТВАМИ (точное, в отличие от жадного из раздела 14)
    состояние: маска накрытых элементов
    переход: добавить одно множество
    цена Θ(2^n · число множеств)

РАСКЛАДКА ПО ЯЩИКАМ, РАСКРАСКА, РАСПИСАНИЕ С ЗАПРЕТАМИ
    везде одно и то же: «что уже использовано» не сжимается в число,
    поэтому приходится помнить множество целиком

Важная деталь из первого примера: перебирать партнёра надо для ЗАФИКСИРОВАННОГО элемента (например, младшего свободного), а не для всех пар. Это убирает множитель n и заодно избавляет от дублей - типовой приём в задачах на разбиение.

И общий признак, по которому узнают эти задачи: в условии есть слово «каждый ровно один раз» или «все, без повторов», а число элементов подозрительно маленькое - 15, 18, 20. Маленькое n в условии при NP-трудной формулировке почти всегда означает «решай по маскам».

Что ломается без этого

Первое: обходить маски по убыванию - переход ссылается на меньшие маски, и они окажутся несчитанными. Второе: писать mask + 2**u, не проверив, что элемент ещё не взят: иначе число «переполнится» в чужой бит и состояние поедет. Третье: забыть, что dp[mask][v] имеет смысл только если v входит в mask - половина таблицы останется мусором, и минимум по ней даст неверный ответ. Четвёртое: применять маски при n = 30: это 2^30 ≈ 10⁹ масок и 3·10¹⁰ клеток, и никакая константа не спасёт. Пятое: в задаче на разбиение перебирать все пары вместо фиксации младшего свободного элемента: получится лишний множитель n и дубли. Шестое: считать, что битовые операции обязательны - в среде без них (как в движке этого курса) та же маска читается арифметикой mask // 2**i % 2, и цена вырастает лишь на константу.

Зачем это в работе

ДП по маскам - это инструмент для маленьких точных задач, и такие задачи в работе встречаются чаще, чем кажется. Распределить восемнадцать смен между сотрудниками без нарушений; подобрать набор из двадцати признаков, дающий лучшую модель; найти оптимальный порядок обхода десяти точек для курьера; разложить двадцать деталей по минимальному числу заготовок. Везде одно и то же: формулировка NP-трудна, но размер данных маленький, и точный ответ достижим за секунды - вместо того чтобы брать приближение из раздела 14. Второй практический слой - распознавание: если в задаче n <= 20 и в условии «каждый ровно один раз», это почти наверняка маски. И третий - честность в оценках: у коммивояжёра на двадцати городах состояний 2^20 · 20 ≈ 2·10⁷, то есть 160 мегабайт при восьми байтах на клетку, а при двадцати пяти городах - больше шести гигабайт. Метод упирается не только во время, но и в память, и об этом стоит сказать до того, как код написан.

Теперь сам

Задача: восемь человек надо разбить на четыре пары, у каждой пары своя «стоимость несовместимости». Минимизировать сумму. Какое состояние и какая цена?

переход: берём МЛАДШЕГО свободного человека i (он обязан попасть в какую-то пару)
         и перебираем ему партнёра j из оставшихся:
             dp[mask + 2**i + 2**j] = min(..., dp[mask] + cost[i][j])

состояний 2^8 = 256, переход перебирает не больше 7 партнёров
цена Θ(2^n · n) ≈ 2048 операций